N
Hi Leute!
Ich habe die Aufgabe den Bubblesort algorithmus aufzuschreiben und dann dieser Modifizierte form zu machen und dann das Laufzeitverhalten etc. mit einander zu vergleichen. Bubblesort algorithmus zu schrieben ist kein Problem. Aber ich werde einfach nicht schlau draus welche vorteile dieser Modifikation bringen soll. Vllt kann mir jmd nen tipp geben. Vllt hat dieser Modifikation sogar einen Namen und wird als algorithmus verwendet.
Erstmal die Beschreibung des Bubblesort:
Wir betrachten den Bubble-Sort Algorithmus. Seien a1, · · · , an, n Zahlen, die in einem Array
A[1, ·, n] gespeichert sind (A[i] enthält ai). Ein elementarer Schritt im Bubble-Sort Algorith-
mus ist der sogenannte Copare-Exchange Schritt (C/E). Für 1 = i < j = n hat C/E(i, j) die
Wirkung: 'Falls A[i] > A[j], dann vertausche A[i] und A[j].' Wir nennen das Auftreten von
A[i] > A[j] mit 1 = i < j = n eine Inversion. Um ein sortiertes Array A[1, · · · , n] zu erhalten,
müssen all Inversionen beseitigt werden. Dazu führt der Bubble-Sort Algorithmus C/E(i, i+1)
Schritte, also Compare-Exchange Operationen auf benachbarten Array-Positionen, aus.
Und jetzt die Modikation:
Es wird nun folgende Modikation des Bubble-Sort Algorithmus vorgenomme: Falls in Runde i die letzte vorgenommene Vertauschung (n - j, n - j + 1) war mit j > i, dann werden die
Runden i + 1, · · · , j übersprungen, und erst mit Runde j + 1 weitergemacht.
Hier der Programmcode für Bubblesort in Pseudocode:
prozedur bubbleSort( A : Liste sortierbarer Elemente )
n := Länge( A )
wiederhole
vertauscht := falsch
für jedes i von 1 bis n - 1 wiederhole
j:=i+1;
falls A[ i ] > A[ j ] dann
vertausche( A[ i ], A[ j ] )
vertauscht := wahr
falls ende
für ende
solange vertauscht==true
prozedur ende
Und jetzt der Modifizierte Code wie ich es mir denke:
prozedur bubbleSort( A : Liste sortierbarer Elemente )
n := Länge( A )
wiederhole
vertauscht := falsch
für jedes i von 1 bis n - 1 wiederhole
j:=i+1;
falls (zuletztgetauschte_i==n-j) UND (zuletztgetauschte_j==n-j+1)
i:=j+1;
falls ende
sonst
falls A[ i ] > A[ j ] dann
vertausche( A[ i ], A[ j ] )
vertauscht := wahr
zuletztgetauschte_i:=i
zuletztgetauschte_j:=j
falls ende
sonst ENDE
für ende
solange vertauscht==true
prozedur ende
Oder mache ich irgendwo nen großen denkfehler?
Viele Grüße und danke im voraus
NightWalker