Mergesort einmal anders.

[MacGuyver]

Moin auch!

Ich habe mir den Eintrag "Wie kann ich Mergesort einsetzten?" angetan. Dabei ist mir aufgefallen, daß das Teil rekursiv arbeitet. Unterm Strich ist das doch voll Quatsch, braucht doch nur Zeit. Im letzten Verschmelzungsvorgang benötigt man noch einmal genauso viel Speicher wie für die zu sortierenden Daten.

Hat jemand sich damit auseinander gesetzt? Kann man noch schneller sortieren?
Ich habe ein XMS-Object geschrieben, das vorher den Quicksort verwendete. Ich habe gestaunt, daß Mergesort nur 80% der Zeit benötigte.


Stefan



Also, ganz einfach: Man holt sich den erwähnten Speicher, doppelt so viel wie die zu sortierenden Daten. Jetzt braucht man nur noch eine Schleife zu durchlaufen und schon ist alles sortiert. Ok, das war zu schnell. Im ersten Durchgang nimmt man immer nur ein Zeichen, links und rechts. Das wären die Positionen 0 und 1. Die beiden verschmilzt man und fährt mit 2 und 3 fort. Das nun komplett durch. Als nächster Durchgang wird das mit jeweils 2 Zeichen und dann mit 4 etc. gemacht. Wenn er mehr oder gleich viel Zeichen wie die Gesamtmenge verschmilzen will, ist der vorgang zu Ende.

Verschmilzen:
Es sind immer zwei sortierte Listen die miteinander verschmilzt werden. Hier findet auch die eigentliche Sortierung statt. Nehmen wir den dritten Durchgang des Beispiels unten vor:

Code:

   1  0
   2  5 
   3  7
  15  9

Es werden beide Spalten abwechselnd durchlaufen, je nach Daten. Erst die 0 von rechts, die ist kleiner als die 1 von links. Dann die 1 von links, die 5 rechts ist größer.
Problematisch werden dann die Sonderfälle, daß die eine Seite keine oder weniger Daten hat.
Das Ergebnis beim Verschmelzen kommt dann vom ersten in den zweiten Speicher. Beim nächsten
Durchgang wird dann wieder vom zweiten Speicher in den ersten Speicher verschmolzen. Wenn der Algo rekursiv läuft, muß man immer wieder die Daten zurück kopieren, was unnötig Zeit benötigt. Ist am Ende nur zu prüfen, wo das Ergebnis gerade ist.

Code:

#     15  2    3  1    5  0    7  9    8 11   12 14   13  4    6 10 
#     -----   -----   -----   -----   -----   -----   -----   -----
#      2 15    1  3    0  5    7  9    8 11   12 14    4 13    6 10 
#      -----------     -----------     -----------     ----------- 
#       1  2  3 15      0  5  7  9      8 11 12 14      4  6 10 13
#        -----------------------         -----------------------
#         0  1  2  3  5  7  9 15          4  6  8 10 11 12 13 14
#            -----------------------------------------------
#             0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

Nach vier Durchgängen ist der Datenpool sortiert. Es dauert immer gleich lange. So kann man beim Mergesort auch einen Progressbar mitlaufen lassen.

[dizzy]

Zitat von MacGuyver:

Nach vier Durchgängen ist der Datenpool sortiert. Es dauert immer gleich lange. So kann man beim Mergesort auch einen Progressbar mitlaufen lassen.

Soweit ich weiss ist Mergesort der Ordnung: O(n)=[log2(n)] // ( "[]"=Gaußklammer, ist gleich trunc() )

...meine ich zumindest...

[mytar]

Ich glaube Mergsort hat eine Zeitkomplexität von O(n·log(n)).

greetz
mytar

[MacGuyver]

Oh Gott, oh Gott!

Gaußklammer, Zeitkomplexität, Bahnhof, Bratkartoffeln?
Man nehme die Menge und teile so lange durch 2, bis 0 ist. Dabei mitzählen und gut. Einfach Shr 1 benutzen. In anbetracht der Sortierzeit fällt das ins gewicht wie eine Fliege im Jumbojet.
Viel interessanter ist doch, daß man anzeigen kann, wie weit er sortiert hat.

Stefan