Kann jemand diesen Array sortieren, also per hand nach Quicksort was dabei rauskommt?
Hi, habe die Frage vorher gestellt, aber vergessen den Piviots anzugeben, hierbei soll das mal z.B die 47 sein. Wie würden die Sortierschritte beim Quicksort aussehen?
{ 67, 9, 2, 67,47 }
könnte den jemand mal per Hand sortieren, also die Sortierschritte nennen?
weil was ich nicht kapiere, wie geht man mit den zwei gleichen Zahlen um, also den zwei 67?
wie würde es nach der Sortierung am ende sein und wie sind die Zwischenschritte, habe mir hunderte Tutorials angeschaut, aber keins hat 2x die gleiche Zahl…
und mur mal als Vergleich hätte man beim Mergesort such ein Problem wegen den zwei gleichen Zahlen?
4 Antworten
Es ist unerheblich bei zwei identischen Elementen, welches der beiden zuerst oder zuletzt einsortiert wird, da sie ja identisch bezüglich des Vergleichskriteriums sind.
Es ist ein bisschen schwierig, hier die Schritte übersichtlich aufzuschreiben, aber ich versuche es mal. Der Quicksort würde in Deinem Fall folgendermaßen ablaufen:
Divide-Phase:
Teilungsschritt 1: 67 9 2 67 47 => Pivot-Element 2
2 67 9 67 47
Teilungsschritt 2 für linke Liste nicht erforderlich
Teilungsschritt 2 für rechte Liste => Pivot Element 67 (Mitte)
9 47 67 67
Teilungsschritt 3 für linke Liste => Pivot Element 9
9 47
Teilungsschritt 3 für rechte Liste => Pivot Element 67
67 67
Weitere Teilungsschritte entfallen, da im Zuge der Auftrennung der Liste "67 67" erkannt wird, dass die Elemente gleich sind. Alternative ist, das Pivotelement keiner Liste zuzuweisen und dann im Merge-Schritt in der Mitte einzufügen.
Merge-Phase:
Aus Teilungsschritt 3 werden die linke Liste 9 47 und die rechte Liste 67 67 zusammengefügt.
Durch Teilungsschritt 2 wird die linke Liste 2 behalten und aus den Listen 9 47 und 67 67 entsteht die rechte Liste 9 47 67 67.
Diese werden zusammengefügt zu 2 9 47 67 67.
weil was ich nicht kapiere, wie geht man mit den zwei gleichen Zahlen um, also den zwei 67?
Man behandelt sie halt als zwei Mal die gleiche Zahl. Sind halt in der sortierten Liste dann direkt nebeneinander.
Wenn es dir um die Aufteilung mit dem Pivot-Element geht: Ist die doppelte Zahl nicht das Pivot-Element, wird eben entsprechend nach größer/kleiner eingeordnet.
Ist die doppelte Zahl das Pivot-Element, darf man sich quasi aussuchen, in welche der neuen Teillisten man die "übrige" gleiche Zahl schiebt ...
Ist doch egal:
Die Allgemeine Abfrage lautet:
If (array[n] < array[n+1]) {
byte temp = array[n];
array[n] = array[n+1];
array[n+1] = temp;
}
Falls es also zum Vergleich von 67 und 67 kommt, ist die Bedienung nicht wahr und die Werte werden nicht vertauscht.
Im Endergebnis liegen diese beiden Zahlen also hintereinander.
Also:
array = {2,9,47,67,67}
Die Antwort ist sehr kurz: es ist egal, du darfst gleiche Zahlen in beliebiger Reihenfolge hintereinander schreiben.
{2,9,47,67,67}
Danke, aber wie würden dann die einzenen Schritte aussehen beim Sortieren? Irgendwie kann ich mir die Sxchrit vom Anfang bis zu 2,9,47,67,67 schwer vorstellen wegen den zwei gleichen Zahlen
Hier Schritt für Schritt: Fett = Abgehakt
Als erstes brauchen wir ein Pivo Element der Einfachheit halber das erste Element also bei {67,9,2,67,47} die erste 67 die schreiben wir in die Mitte da raus ergibt sich dann folgende Struktur {9,2,67,67,47} nun werden alle Zahlen kleiner als unser Pivo nach links und größere nach rechts. Ergibt dann {9,2,47,67,67} nun suchen wir uns zwei neue Pivo Elemente, nämlich das erste Element auf der linken Seite vom letzten Pivo und das erst Element der rechten Seite vom letzten Pivo und setzen sie in die Mitte ein(Anmerkung: da rechts vom letzten Pivo nur noch einer ist können wir den gleich abhaken). Das neue Pivo ist also 9 welches wir in die Mitte der linken Seite schreiben ergibt {2,9,47,67,67}. Da wir nur noch zwei Einzel Elemente haben können wir sie getrost so lassen und beenden.
ich glaube, du verwechselst hier Bubblesort mit Quicksort. Aber ja, es ist im Endeffekt egal