blatt 1 beispiel 9 [Archive] - Informatik-Forum.at

gonzo69

22-10-2008, 23:12

(313,214,12,1,111,111,213)

also das ganze mal sortieren "Partitionierungsphase" mit der hinteren zahl (üblicher weise von hinten nach vorn)

1 2 3 4
--------------------------
001 012 313 214
111 213
111

man braucht 4 fächer

nach der sammelphase (alle daten aus dem niedrigsten fach, dann alle aus dem nächsten, usw.) siehts dann so aus:
(001,111,111,012,313,213,214)

dann weder Partitionierungsphase diesmal mit der mittleren zahl

0 1
------------
001 111
111
012
313
213
214

diesmal braucht man nur 2 fächer

erneute sammelphase:
(001,111,111,012,313,213,214)

und die letzte Partitionierungsphase mit der ersten zahl:

0 1 2 3
-----------------------
001 111 213 313
012 111 214

mann braucht wieder 4 fächer

letzte sammelphase:
(1,12,111,111,213,214,313)

und die zahlen sind geordnet :) man braucht insgesamt 10 fächer
hoffe das war einigermasen verständlich und ich hoffe ich bin nicht total ma holzweg :verycool:

was sie allerdings mit der letzten frage "ist es beim sortieren durch fachverteilung möglich, dass die reihenfolge der elemente mit gleichem schlüssel vor und nach dem sortiervorgang nicht erhalten bleibt? begründen sie ihre antwort" meinen, ist mir nicht ganz klar :( weiß da vl wer weiter?

davide

23-10-2008, 01:25

was sie allerdings mit der letzten frage "ist es beim sortieren durch fachverteilung möglich, dass die reihenfolge der elemente mit gleichem schlüssel vor und nach dem sortiervorgang nicht erhalten bleibt? begründen sie ihre antwort" meinen, ist mir nicht ganz klar :( weiß da vl wer weiter?

gemeint ist sowas wie im geposteten beispiel, dass du zwei- oder mehrmal den gleichen wert hast, wie hier 111

bins jetzt nicht durchgegangen, aber wenn du dir beide markierst, also zb 111* und 111' draus machst, erkennst du ob am ende immer noch 111* vor 111' in der liste ist

du findest sicher auch ein beispiel mit wenigen elementen mit dem du zeigen kannst dass die reihenfolge nicht unbedingt beibehalten wird

stichwort: http://de.wikipedia.org/wiki/Stabil_(Sortierverfahren (http://de.wikipedia.org/wiki/Stabil_%28Sortierverfahren))

noch ein tipp: überleg dir wie dus angehen musst um mit fachverteilung ABsteigend zu sortieren :)

gonzo69

23-10-2008, 10:46

nochmals danke, davide :)

noch ein tipp: überleg dir wie dus angehen musst um mit fachverteilung ABsteigend zu sortieren :)

ja absteigend, einfach in die gleichen fächer sortieren, nur beim fach mit dem größten wert von unten hinauf übernehmen, dann zum zweit größten fach, usw .... mal ganz banal dahin gedacht, oder?

aber in der übung is ja aufsteigend gefragt, oder wirddie frage gern von tutoren gestellt?

EDIT: alles klar, jetzt weiß ich was du meinst

babs80

26-10-2008, 10:04

(313,214,12,1,111,111,213)

1 2 3 4
--------------------------
001 012 313 214
111 213
111

nur eine kleine anmerkung: du hast 213 in dein 2er fach geworfen - aber ich denke das ist nur ein tippfehler, weil beim sammeln passt die reihenfolge wieder...

frage mich gerade, ob die antwort wieviele fächer man braucht nicht fünf ist

dh fach 0 bis fach 4

im skriptum hat man ja bei jeder verteilungsphase auch alle fächer zur verfügung - die nicht benötigten werden halt einfach nicht befüllt

gonzo69

27-10-2008, 22:37

nur eine kleine anmerkung: du hast 213 in dein 2er fach geworfen - aber ich denke das ist nur ein tippfehler, weil beim sammeln passt die reihenfolge wieder...

frage mich gerade, ob die antwort wieviele fächer man braucht nicht fünf ist

dh fach 0 bis fach 4

im skriptum hat man ja bei jeder verteilungsphase auch alle fächer zur verfügung - die nicht benötigten werden halt einfach nicht befüllt

ja hab mich verschrieben im post, sry... glaub das mit den 5 fächern hast du auch recht, also 0-4

thx

sanssecours

29-10-2008, 18:03

gemeint ist sowas wie im geposteten beispiel, dass du zwei- oder mehrmal den gleichen wert hast, wie hier 111

bins jetzt nicht durchgegangen, aber wenn du dir beide markierst, also zb 111* und 111' draus machst, erkennst du ob am ende immer noch 111* vor 111' in der liste ist

du findest sicher auch ein beispiel mit wenigen elementen mit dem du zeigen kannst dass die reihenfolge nicht unbedingt beibehalten wird

stichwort: http://de.wikipedia.org/wiki/Stabil_(Sortierverfahren (http://de.wikipedia.org/wiki/Stabil_%28Sortierverfahren))

noch ein tipp: überleg dir wie dus angehen musst um mit fachverteilung ABsteigend zu sortieren :)

Aloha Davide

Also bei Fachverteilung sollte die Reihenfolge von Elementen mit gleichem Schlüssel schon erhalten bleiben. Die Quelle dafür ist z.B. der von dir zitierte Wikipedia Artikel (http://de.wikipedia.org/wiki/Stabil_%28Sortierverfahren%29), in dem unter den stabilen Sortieralgorithmen Radixsort (= Sortieren mittels Fachverteilung) eingeordnet wurde. Viellicht verstehe ich deine Aussage du findest sicher auch ein beispiel mit wenigen elementen mit dem du zeigen kannst dass die reihenfolge nicht unbedingt beibehalten wirdaber auch falsch. Wenn ja, dann bitte ich das hier Geschriebene einfach zu ignorieren.

lg rene

gonzo69

29-10-2008, 19:20

sanssecours

29-10-2008, 20:07

"Ein stabiles Sortierverfahren ist ein Sortieralgorithmus (http://de.wikipedia.org/wiki/Sortierverfahren), der die Reihenfolge der Datensätze (http://de.wikipedia.org/wiki/Datensatz), deren Sortierschlüssel (http://de.wikipedia.org/wiki/Schl%C3%BCssel_%28Datenorganisation%29) gleich sind, bewahrt." -wikipedia

stimmt ... reicht das als begründung? weil es steht mal soll seine antwort begründen

Naja Wikipedia reicht wohl nicht als Begründung. Ich hätte, für den Fall, dass mein Tutor zum meinem Übungstermin heute erschienen wäre wohl etwas wie folgt gesagt:

Erst mal kann man logischerweise 2 Phasen unterscheiden: Verteilungsphase und Sammelphase.

Einen Tausch der Elemente kann es eigentlich ja nur in der Verteilungsphase geben, da in der Sammelphase die Elemente einfach der Reihe nach von der Verteilungsphase notiert werden. Die Reihenfolge bleibt also gleich wie bei der Verteilungsphase. Auch bei Elementen mit gleichem Schlüssel, die ja im gleichen Fach stehen, wird die Reihenfolge nicht vertauscht, da wir die Elemente zeilenweise von vorne nach hinten anschreiben.

Zur Verteilungspahse: Hier werden die Elemente der Reihe nach genommen und eingeordnet. Sagen wir haben jetzt ein paar Elemente mit dem selben Schlüssel A. Kommt jetzt das erste Element mit dem Schlüssel A wird es in sein Fach eingeordnet. Ein weiteres Element, dass später kommt und den gleichen Schlüssel hat wird immer auf einem Platz hinter dem ersten Element mit Schlüssel A gelegt. Im Endeffekt wird also auch hier an der Reihenfolge nichts geändert. Steht ein Element mit Schlüssel A in der vorhergehenden Sammelphase nach einem Element mit dem gleichen Schlüssel A wird es auch in der Verteilphase wieder nach diesem Element eingeordnet.

lg rene

davide

29-10-2008, 20:29

Aloha Davide...

ja da hab ich mich leider vertan :(
sorry für die verwirrung