Math
Wettlauf der Sortierverfahren
Drei Verfahren laufen über dasselbe Feld, gleich schnell in VERGLEICHEN, und zuerst ist fertig, wer weniger gefragt hat. Entscheidend ist die Unordnung, nicht die Größe: auf sortierter Eingabe braucht Einfügen 63 Vergleiche, Quicksort 2016.
Was passiert
Drei Bahnen, ein Array und ein gemeinsames Arbeitsbudget: Alle drei Sortierverfahren rücken um gleich viele Vergleiche vor - oder Verschiebungen, wenn Sie die Einheit umschalten -, also ist zuerst fertig, wer am wenigsten von dieser Einheit brauchte, nicht wer schneller gezeichnet wird. Jede Bahn spricht dieselbe Sprache: Die beiden verglichenen Schlüssel sind golden umrandet, ein gerade geschriebener Schlüssel blinkt grün, ein Pivot trägt eine rote Marke, der bearbeitete Abschnitt ist eingeklammert, Elemente an ihrem endgültigen Platz bekommen einen grünen Fuß, und der Schlüssel, den Insertion Sort hält, schwebt über der Lücke, in die er fällt. Sagen Sie den Sieger vor »Los« voraus oder gehen Sie das Rennen Einheit für Einheit durch. Probieren Sie die Eingaben: Auf einem sortierten Array ist Insertion fast sofort fertig, während Quicksort mit dem letzten Element als Pivot seinen schlechtesten Fall trifft; umgekehrt ist der schlechteste Fall von Insertion; bei wiederholten Schlüsseln ist die Farbe die Position in der Eingabe, und Merge hält gleiche Schlüssel in Ordnung, Quicksort mischt sie. Jede Bahn zeigt auch die echte Laufzeit auf diesem Rechner - eine dritte Größe, nie die Einheit des Rennens.
Gleichungen des Moduls
Gleichungen n Elemente, und das Rennen wird in VERGLEICHEN gelaufen - der Größe, von der die Formeln handeln Insertionsort BEWEGT ein Element genau so oft, wie das Feld Inversionen hat: eine Identität auf JEDER Permutation, geprüft über alle n! für n <= 8 Vergleiche beim Einfügen = Inversionen + (n − 1) − (Präfixminima bei i >= 1); Mittelwert = n(n−1)/4 + n − H_n EXAKT: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 Quicksort (Lomuto, letztes Element als Pivot) Mittelwert = 2(n+1)H_n − 4n EXAKT: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 Mergesort im schlimmsten Fall = n·ceil(lg n) − 2^ceil(lg n) + 1 - eine Formel, keine Schranke: 321 bei n = 64, gegenüber ceil(lg n!) = 296, der Untergrenze JEDES Vergleichssortierverfahrens beide sind gleich für n <= 4 und laufen danach auseinander; Mergesort schreibt außerdem n·lg n Elemente, was auch immer die Eingabe ist - 384 bei n = 64 64 Elemente, jede Stelle durchmischt: 1001 Inversionen; Insertionsort 1057 Vergleiche / 1001 Bewegungen, Mergesort 307 / 384, Quicksort 352 / 306 64 Elemente, sortierte Eingabe: Insertionsort 63, Mergesort 192, Quicksort 2016 - und 2016 ist n(n−1)/2, der SCHLIMMSTE Fall von Quicksort Mergesort überholt Insertionsort bei 15 durchmischten Stellen von 64 (269 gegenüber 246): die Schwelle ist die Unordnung, nicht die Größe - bei zufälliger Eingabe liegt Mergesort ab n = 4 vorn gleiche Schlüssel, 64 Elemente über 8 Werte: in umgekehrter Reihenfolge verbliebene Paare - Insertionsort 0, Mergesort 0, Quicksort 77
