Geekly articles weekly

Vergleich der Austauschsortierung



Sphärische Algorithmen im Vakuum sind großartig. Gehen wir jedoch vom Himmel auf die sündige Erde hinunter und sehen, wie sich all diese theoretische Schönheit in der Praxis bewähren wird.

Die Analyse der nächsten Klassenklasse endet mit Tests für Klassensorten. Heute werden wir Sortierbörsen (nicht im Sinne des Wegwerfens, sondern im Sinne des Testens) sortieren. Sorten anderer Klassen werden später ausgeführt.

Im heutigen Rennen:

Schwächste Gruppe


Diese Algorithmen beanspruchen aufgrund der drückenden Zeitkomplexität nichts. Wir testen sie nur als Referenz.

Dumme Sorte
Träge Sortierung
Dumme Sortierung

Noch interessanter ist nicht nur, wie gut sie sind, sondern auch, wie schlecht sie im Geschäft sind und welcher von ihnen der schlechteste ist.

Hauptgruppe


Hier versammelten sich Austauschsortierungen a la O ( n 2 ). Zwergsortierung (und ihre Optimierung) + alle Arten von Variationen der Blasensortierung.

Zwergsort
Zwergsortierung (optimiert)
Blasensortierung
Cocktailsortierung
Seltsam-gerade Sortierung

Dies ist der interessanteste Teil der heutigen Messungen. Unter den Vertretern der Hauptgruppe wird der hartnäckigste Kampf erwartet.

Stärkste Gruppe


Einer der Sorten der Blase - Sortierung nach einem Kamm - gelang es, die O ( n 2 ) -Sperre zu überwinden und mit der Zeit das respektable O ( n log n ) zu erreichen. In unserer Konkurrenz hat das schnelle Sortieren einen würdigen Rivalen. Probieren Sie auch die neu erfundene k-Sortierung aus , eine Variation der schnellen Sortierung.

Haarbürste sortieren
Schnelle Sortierung
K Sortierung

Die Stärksten sind übrigens nicht nur miteinander vergleichbar. Bei einigen Datensätzen wird die Hauptgruppe in einem ernsthaften Wettbewerb stehen.

Quellcode


Python Exchange-Sortierungen
def stooge_rec(data, i = 0, j = None): if j is None: j = len(data) - 1 if data[j] < data[i]: data[i], data[j] = data[j], data[i] if j - i > 1: t = (j - i + 1) // 3 stooge_rec(data, i, j - t) stooge_rec(data, i + t, j) stooge_rec(data, i, j - t) return data def stooge(data): return stooge_rec(data, 0, len(data) - 1) def slow_rec(data, i, j): if i >= j: return data m = (i + j) // 2 slow_rec(data, i, m) slow_rec(data, m + 1, j) if data[m] > data[j]: data[m], data[j] = data[j], data[m] slow_rec(data, i, j - 1) return data def slow(data): return slow_rec(data, 0, len(data) - 1) def stupid(data): i, size = 1, len(data) while i < size: if data[i - 1] > data[i]: data[i - 1], data[i] = data[i], data[i - 1] i = 1 else: i += 1 return data def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data def bubble(data): changed = True while changed: changed = False for i in range(len(data) - 1): if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] changed = True return data def shaker(data): up = range(len(data) - 1) while True: for indices in (up, reversed(up)): swapped = False for i in indices: if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] swapped = True if not swapped: return data def odd_even(data): n = len(data) isSorted = 0 while isSorted == 0: isSorted = 1 for i in range(1, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 for i in range(0, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 return data def comb(data): gap = len(data) swaps = True while gap > 1 or swaps: gap = max(1, int(gap / 1.25)) # minimum gap is 1 swaps = False for i in range(len(data) - gap): j = i + gap if data[i] > data[j]: data[i], data[j] = data[j], data[i] swaps = True return data def quick(data): less = [] pivotList = [] more = [] if len(data) <= 1: return data else: pivot = data[0] for i in data: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quick(less) more = quick(more) return less + pivotList + more def k(data): return k_rec(data, 0, len(data) - 1) def k_rec(data, left, right): key = data[left] i = left j = right + 1 k = left + 1 p = left + 1 temp = False while j - i >= 2: if key <= data[p]: if p != j and j != right + 1: data[j] = data[p] elif j == right + 1: temp = data[p] j -= 1 p = j else: data[i] = data[p] i += 1 k += 1 p = k data[i] = key if temp: data[i + 1] = temp if left < i - 1: k_rec(data, left, i - 1) if right > i + 1: k_rec(data, i + 1, right) return data

PHP Exchange Sorts
  // function StoogeSort(&$arr, $i, $j) { if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]); if(($j - $i) > 1) { $t = ($j - $i + 1) / 3; StoogeSort($arr, $i, $j - $t); StoogeSort($arr, $i + $t, $j); StoogeSort($arr, $i, $j - $t); } return $arr; } // function SlowSort(&$arr, $i, $j) { if($i >= $j) return $arr; $m = ($i + $j) / 2; SlowSort($arr, $i, $m); SlowSort($arr, $m + 1, $j); if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]); SlowSort($arr, $i, $j - 1); return $arr; } // function StupidSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); $i = 1; } } return $arr; } // function GnomeSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if($i > 1) --$i; } } return $arr; } // () function GnomeSort_opt($arr) { $i = 1; $j = 2; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ $i = $j; ++$j; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if(--$i == 0){ $i = $j; $j++; } } } return $arr; } // function BubbleSort($arr) { $c = count($arr) - 1; do { $swapped = false; for ($i = 0; $i < $c; ++$i) { if ($arr[$i] > $arr[$i + 1]) { list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]); $swapped = true; } } } while($swapped); return $arr; } // function ShakerSort($arr){ do{ $swapped = false; for($i = 0; $i < count($arr); $i++){ if(isset($arr[$i + 1])) { if($arr[$i] > $arr[$i+1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $swapped = true; } } } if ($swapped == false) break; $swapped = false; for($i = count($arr) - 1; $i >= 0; $i--){ if(isset($arr[$i - 1])){ if($arr[$i] < $arr[$i - 1]) { list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]); $swapped = true; } } } } while($swapped); return $arr; } //- function OddEvenSort($arr){ $n = count($arr); $sorted = false; while(!$sorted) { $sorted = true; for($i = 1; $i < $n - 2; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } for($i = 0; $i < $n - 1; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } } } // function CombSort($arr){ $gap = count($arr); $swap = true; while($gap > 1 || $swap){ if($gap > 1) $gap /= 1.25; $swap = false; $i = 0; while($i + $gap < count($arr)){ if($arr[$i] > $arr[$i + $gap]){ list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]); $swap = true; } ++$i; } } return $arr; } // function QuickSort($arr) { $loe = $gt = array(); if(count($arr) < 2) { return $arr; } $pivot_key = key($arr); $pivot = array_shift($arr); foreach($arr as $val){ if($val <= $pivot){ $loe[] = $val; }elseif ($val > $pivot){ $gt[] = $val; } } return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt)); } //k- function K_Sort($arr) { K_Sort_rec($arr, 0, count($arr) - 1); return $arr; } function K_Sort_rec(&$arr, $left, $right) { $key = $arr[$left]; $i = $left; $j = $right + 1; $k = $p = $left + 1; $temp = false; while($j - $i >= 2) { if($key <= $arr[$p]) { if(($p != $j) && ($j != ($right + 1))) { $arr[$j] = $arr[$p]; } elseif($j == ($right + 1)) { $temp = $arr[$p]; } --$j; $p = $j; } else { $arr[$i] = $arr[$p]; ++$i; ++$k; $p = $k; } } $arr[$i] = $key; if($temp) $arr[$i + 1] = $temp; if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1); if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right); }

Zeit


Die Zeit wird überall in Sekunden gemessen, die auf Mikrosekunden genau sind.

Wenn eine Packung Arrays (von zehn, hundert oder sogar einer Million Stück) sofort dem Algorithmus zugeführt wird, wird die Gesamtzeit angezeigt.

Eisen ist mein treuer alter Laptop, der bessere Zeiten kannte. Möglicherweise funktioniert also alles viel schneller für Sie.

Das Schlimmste vom Schlimmsten


Sofort mit Außenstehenden umgehen. Für sie werden Arrays für 40/50/60 Elemente mit Zufallszahlen von 0 bis 9 vorbereitet.
Typ = zufällig, eindeutig = falsch, min = 0, max = 9, Anzahl = 1
Größe
405060
PythonPhpPythonPhpPythonPhp
0,0040,0010,0050,0030,0070,004
0,0070,0090,0180,0090,0180,023
0,028.266470,05320.87220,1290145,9786

Dumme Sortierung ist eine Größenordnung schneller als alberne Sortierung, und dumme Sortierung ist eine Größenordnung schneller als träge. Es gibt nichts mehr zu sehen.

Mittlerer Bauer


Um den Durchschnitt zu überprüfen, wurden Packungen mit einhundert Arrays mit jeweils 100 Elementen (eindeutige Nummern von 100 bis 999) sowie Packungen mit zehn Arrays mit jeweils 1000 Elementen (eindeutige Nummern von 1000 bis 9999) generiert.

Es werden zufällige Arrays, fast sortierte Arrays und Arrays in umgekehrter Reihenfolge vorbereitet.

Mittelgewicht: Zufällig


Typ = zufällig, eindeutig = Wahr
Größe (min bis max) × Anzahl
100 (100 bis 999) × 1001000 (1000 bis 9999) × 10
PythonPhpPythonPhp
0,141010,189011,591091,7251
0,206010,223012.330132,09712
0,153010,229011,67112.23613
0,216010,264022,555152,73116
0,167010,334021,72513.13218

Etwa die gleichen Ergebnisse für alle. Python-Implementierungen arbeiten etwas schneller als PHP.

Middles: Fast sortiert


Typ = fast, eindeutig = Wahr
Größe (min bis max) × Anzahl
100 (100 bis 999) × 1001000 (1000 bis 9999) × 10
PythonPhpPythonPhp
0,0090,0050,0090,005
0,0090,0140,010,014
0,010,010,0110,008
0,0110,0080,0130,008
0,0110,0170,0130,017

Alle haben die gleichen Ergebnisse, plus oder minus. Aus dem Interessanten: Teilweise Datenbestellungen verbessern die Leistung aller Algorithmen dutzende Male.

Mitte: Rückseite


Typ = umgekehrt, eindeutig = wahr
Größe (min bis max) × Anzahl
100 (100 bis 999) × 1001000 (1000 bis 9999) × 10
PythonPhpPythonPhp
0,268010,359023.100183.4292
0,396020,453034.497264.19524
0,227010,384022.481143.64421
0,302020,426033.344194,17524
0,304020,644043,365196.22036

Es gibt eine interessante Schlussfolgerung: Die umgekehrte Reihenfolge wirkt sich nicht so stark auf die Geschwindigkeit aus, die im Vergleich zur Zufallszahl nur zweimal gesunken ist.

Mitte: Binär


Typ = zufällig, eindeutig = falsch, min = 0, max = 1
Größe × Anzahl
100 × 1001000 × 10
PythonPhpPythonPhp
0,0730,0940,811050,86905
0,104010,113011.163071,06606
0,088010,129010,864051.18207
0,115010,150011.301071.41608
0,114010,258011.319082.46314

Von mehr oder weniger interessant: Wenn Sie anstelle von Zahlen von 100 bis 9999 Nullen und Einsen sortieren, werden die Geschwindigkeitsanzeigen nicht viel wachsen.

Champions


Die Hauptintrige dabei ist, ob das Sortieren mit einem Kamm und das K-Sortieren das Fasten vom Sockel drücken können.

Champions: Zufällig


Um dies herauszufinden, bilden wir Pakete mit zufälligen Arrays: 10 Teile mit 10.000 Elementen und 10 Teile mit 100.000 Elementen. Ich wollte den Eingabealgorithmen Millionäre geben, aber der Laptop zog nicht. Entweder ist nicht genügend RAM vorhanden, dann ist die Rekursionstiefe zu groß.
Typ = zufällig, eindeutig = falsch, Anzahl = 10
Größe (min bis max)
10000 (von 10000 bis 99999)100000 (von 100000 bis 999999)
PythonPhpPythonPhp
0,802050,6310410.45068.24647
0,477031.640096.6513826.5435
0,900052.1861315.808929.4867

Die Python K-Sortierung ist langsamer und PHP ist schneller als die schnelle Sortierung.
Das Sortieren des Kamms im Vergleich zum schnellen sieht solide aus, obwohl es in allen Tests (und in diesen und den folgenden) für alle Datensätze schlechter ist.

Es gibt jedoch Kämme und einen wichtigen unbestreitbaren Vorteil. Es hat keine Rekursion und verarbeitet daher im Gegensatz zu seinen Kollegen erfolgreich Arrays von Millionen von Elementen.

Sonderfälle


Obwohl Champions hunderte Male schneller sind als durchschnittliche Bauern, zeigen die Sortierungen bei bestimmten Datensätzen einfacher, dass sie nicht leicht zu nähen sind.

Sonderfälle: Fast sortiert


Versuchen wir es mit fast sortierten Arrays. Nehmen Sie einfach eine größere Größe als die, die für die durchschnittlichen Bauern getestet wurden.

Ein Paket von 10 Arrays mit jeweils 10 Tausend und ein Paket von 10 Arrays mit jeweils 100 Tausend Elementen.
Typ = fast, eindeutig = Falsch
Größe (min bis max) × Anzahl
10000 (von 10000 bis 99999) × 10100000 (von 100000 bis 999999) × 10
PythonPhpPythonPhp
0,432020,0580,817050,58003
0,0840,0620,858050,54003
0,116010,124011.419081.36008
0,140010,119011,834111.41708
0,138010,231011,64912,56915
?122.088??
0,715041,589099,7835619.4731

Eine schnelle Sortierung ist hier überhaupt nicht vorhanden - es war nicht genügend RAM vorhanden. Gleichzeitig werden zufällige Arrays mit 10/100 Tausend Elementen von Quicksort mit einem Knall verarbeitet. k-sort stieß auf ähnliche Probleme und zog in PHP nur 10 Tausendstel. Große, fast sortierte Arrays sind ein entarteter Fall für eine schnelle Sortierung und deren Modifikationen. Aufgrund dieser Anordnung von Elementen teilt die Rekursion das Array für fast jedes Paar benachbarter Elemente in Teile, was zu der maximal möglichen Anzahl von Rekursionsaufrufen führt.

Bei großen Arrays in umgekehrter Reihenfolge ist die Situation übrigens ähnlich. Es tritt das gleiche Problem auf wie bei fast geordneten - der Algorithmus muss sich für jedes Paar benachbarter Elemente selbst aufrufen.

Sortieren nach einem Kamm, obwohl es eineinhalb bis zweimal langsamer als schnell oder k (im Allgemeinen) arbeitet, aber es hat nicht die oben genannten Speicherüberläufe. Keine Rekursion - kein Problem.

Nun, wir stellen fest, dass alle Mittelbauern zusammen die Champions in großen, fast sortierten Reihen überholten. Dann funktionierte das Prinzip: "Leise gehen - du wirst weitermachen."

Sonderfälle: Millionen scharlachrote Rosen kleiner Arrays


Kleine Arrays - das Element der Mittelbauern. Wenn Sie eine große Anzahl kleiner Zahlenmengen verarbeiten müssen, können Sie einen Zeitgewinn erzielen, indem Sie eine „primitive“ Blasen- oder Gnomensorte verwenden. Und verwenden Sie die schnelle Sortierung und ähnliche für größere Aufgaben.
Typ = zufällig, eindeutig = Wahr
Größe (min bis max) × Anzahl
5 (10 bis 99) × 1.000.00010 (10 bis 99) × 1.000.000
PythonPhpPythonPhp
11.7726717.88824.2903933.6659
12.5187218.16529.3326835.202
15.4418817.86130.0667236,7911
14.1868119.783131.6598139.3533
13.6397824.337428.4166252.864
14.2188121.145225.8054832,5419
14.5868328.501624.8594250,3139
18.5380630.723829.664758.2493


Bei Austauschsortierungen ist alles klar. Nun zum wirklich interessanten Teil - Sortieren nach Beilagen.

Referenzen


Excel-Anwendung AlgoLab , mit der Sie Schritt für Schritt die Visualisierung dieser (und nicht nur dieser) Sorten anzeigen können.

Alle Arrays in Form von JSON sind auch auf der Google-Festplatte angeordnet .

Wiki - Dumm / Handlanger , Langsam , Zwerg / Gnom , Blase / Blase , Shaker / Shaker , Ungerade / Gerade , Kamm / Kamm , Schnell / Schnell

Serienartikel


Source: https://habr.com/ru/post/de415691/

More articles:


All Articles