Geekly articles weekly

Comparaison de tri Exchange



Les algorithmes sphériques dans le vide sont excellents. Descendons cependant du ciel à la terre pécheresse et voyons comment toute cette beauté théorique se révélera en pratique.

L'analyse de la prochaine classe de tris se terminera par des tests pour les tris de classe. Aujourd'hui, nous allons exécuter (non pas dans le sens de jeter, mais dans le sens de lancer des tests) des échanges de tri. Des classes d'autres classes seront exécutées plus tard.

Dans la course d'aujourd'hui impliquée:

Groupe le plus faible


Ces algorithmes ne revendiquent rien en raison de la complexité temporelle déprimante. Nous les testons uniquement à titre de référence.

Sort idiot
Tri lent
Tri muet

C’est encore plus intéressant non seulement de savoir à quel point ils sont bons, mais à quel point ils sont mauvais en affaires, et lequel est le pire.

Groupe principal


Ici se sont réunis des triages d'échange à la O ( n 2 ). Tri nain (et son optimisation) + toutes sortes de variantes de tri à bulles.

Tri nain
Tri nain (optimisé)
Tri des bulles
Tri des cocktails
Tri pair-impair

C'est la partie la plus intéressante des mesures d'aujourd'hui. C'est parmi les représentants du groupe principal que la lutte la plus tenace est attendue.

Groupe le plus fort


Une des variétés de la bulle - triée par un peigne - a réussi à franchir la barrière O ( n 2 ) et à atteindre le O séculaire ( n log n ). Donc, dans notre compétition, le tri rapide a un rival digne. Essayez également le k-sort nouvellement inventé , qui est une variante du tri rapide.

Trier la brosse à cheveux
Tri rapide
Tri K

Soit dit en passant, les plus forts ne sont pas seulement comparables entre eux. Sur certains ensembles de données, le groupe principal sera en forte concurrence.

Code source


Python Exchange Sorts
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); }

Le temps


Le temps est mesuré partout en secondes avec une précision aux microsecondes.

Si un paquet de tableaux (sur dix, cent ou même un million de pièces) est immédiatement appliqué à l'algorithme, alors le temps total est indiqué.

Le fer est mon vieil ordinateur portable fidèle qui a connu des temps meilleurs. Donc, très probablement, tout fonctionnera pour vous beaucoup plus rapidement.

Le pire du pire


Traitez immédiatement avec des étrangers. Des tableaux pour les éléments 40/50/60 contenant des nombres aléatoires de 0 à 9 sont préparés pour eux.
type = aléatoire, unique = Faux, min = 0, max = 9, nombre = 1
taille
405060
PythonPhpPythonPhpPythonPhp
0,0040,0010,0050,0030,0070,004
0,0070,0090,0180,0090,0180,023
0,028.266470,05320.87220,1290145,9786

Le tri stupide est un ordre de grandeur plus rapide que le tri stupide, et le tri stupide est un ordre de grandeur plus rapide que lent. Il n'y a plus rien à regarder.

Paysans moyens


Pour vérifier la moyenne, des packs de cent tableaux de 100 éléments chacun (numéros uniques de 100 à 999), ainsi que des packs de dix tableaux de 1000 éléments chacun (numéros uniques de 1000 à 9999) ont été générés.

Des tableaux aléatoires, des tableaux presque triés et des tableaux en ordre inverse sont préparés.

Poids moyen: aléatoire


type = aléatoire, unique = Vrai
taille (min à max) × nombre
100 (100 à 999) × 1001000 (1000 à 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

Autour des mêmes résultats pour tous. Les implémentations Python fonctionnent un peu plus rapidement que PHP.

Middles: Presque triés


type = presque, unique = True
taille (min à max) × nombre
100 (100 à 999) × 1001000 (1000 à 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

Tous ont les mêmes résultats, plus ou moins. De l'intéressant: la commande de données partielles des dizaines de fois améliore les performances de tous les algorithmes.

Milieu: marche arrière


type = inverse, unique = Vrai
taille (min à max) × nombre
100 (100 à 999) × 1001000 (1000 à 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

Il y a une conclusion intéressante - l'ordre inverse n'affecte pas tellement la vitesse, qui n'a chuté que 2 fois par rapport au nombre aléatoire.

Milieu: binaire


type = aléatoire, unique = Faux, min = 0, max = 1
taille × nombre
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

De plus ou moins intéressant: si au lieu des nombres de 100 à 9999 vous triez les zéros et les uns, les indicateurs de vitesse n'augmenteront pas beaucoup.

Champions


La principale intrigue ici est de savoir si le tri avec un peigne et le tri par k peuvent presser le jeûne du piédestal?

Champions: aléatoire


Pour le savoir, formons des paquets de tableaux aléatoires: 10 morceaux de 10 mille éléments et 10 morceaux de 100 mille éléments. Je voulais donner des millionnaires aux algorithmes d'entrée, mais l'ordinateur portable n'a pas tiré. Soit il n'y a pas assez de RAM, alors la profondeur de récursivité est trop grande.
type = aléatoire, unique = Faux, nombre = 10
taille (min à max)
10000 (de 10000 à 99999)100000 (de 100000 à 999999)
PythonPhpPythonPhp
0.802050,6310410.45068.24647
0,477031,640096.6513826,5435
0,900052.1861315.808929.4867

Le tri Python K est plus lent et PHP est plus rapide que le tri rapide.
Le tri du peigne par rapport au rapide semble solide, bien qu'il soit inférieur à lui dans tous les tests (et sur ceux-ci et les suivants) pour tous les ensembles de données.

Cependant, il existe des peignes et un avantage incontestable important. Il n'a pas de récursivité et donc, contrairement à ses collègues, il traite avec succès des tableaux de millions d'éléments.

Cas particuliers


Bien que les champions soient des centaines de fois plus rapides que les paysans moyens, sur certains ensembles de données spécifiques, les tris montrent plus simplement qu'ils ne sont pas faciles à coudre.

Cas particuliers: presque triés


Essayons des tableaux presque triés, prenons simplement une taille plus grande que celles qui ont été testées pour les paysans moyens.

Un package de 10 tableaux de 10 000 chacun et un package de 10 tableaux de 100 000 éléments chacun.
type = presque, unique = Faux
taille (min à max) × nombre
10000 (de 10000 à 99999) × 10100000 (de 100000 à 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

Le tri rapide n'est pas présent du tout - il n'y avait pas assez de RAM. Dans le même temps, les tableaux aléatoires avec 10/100 mille éléments sont traités par tri rapide avec un bang. k-sort a rencontré des problèmes similaires, n'a tiré que 10 millièmes en PHP. Les grands tableaux presque triés sont un cas dégénéré pour un tri rapide et ses modifications. En raison de cette disposition des éléments, la récursion divise le tableau en parties pour presque chaque paire d'éléments adjacents, ce qui conduit au nombre maximal possible d'appels de récursivité.

Soit dit en passant, la situation est similaire avec de grands tableaux en ordre inverse. Le même problème se pose que pour les éléments presque ordonnés - l'algorithme doit s'appeler pour chaque paire d'éléments adjacents.

Tri par un peigne, bien que cela fonctionne une fois et demie à deux fois plus lentement que rapide ou k (en général), mais il n'a pas les débordements de mémoire susmentionnés. Pas de récursivité - pas de problème.

Eh bien, nous notons que tous les paysans moyens ont dépassé ensemble les champions dans de grands tableaux presque triés. Puis le principe a fonctionné: "Aller tranquillement - vous allez continuer."

Cas particuliers: millions de roses écarlates de petits réseaux


Petits tableaux - l'élément des paysans moyens. Si vous avez besoin de traiter un grand nombre de petits ensembles de nombres, vous pouvez gagner du temps en prenant une sorte de bulle ou de gnome «primitif». Et utilisez le tri rapide et d'autres comme celui-ci pour les tâches plus importantes.
type = aléatoire, unique = Vrai
taille (min à max) × nombre
5 (10 à 99) × 1 000 00010 (10 à 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


Avec les tris d'échange, tout est clair. Maintenant, pour la partie vraiment intéressante - le tri par insertions.

Les références


Application Excel AlgoLab , avec laquelle vous pouvez visualiser étape par étape la visualisation de ces (et pas seulement de ces) sortes.

Tous les tableaux sous forme de JSON sont également disposés sur le disque Google .

Wiki / Stupide / Stooge , Lent , Nain / Gnome , Bulle / Bulle , Shaker / Shaker , Impair / Pair , Peigne / Peigne , Rapide / Rapide

Articles de la série


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

More articles:


All Articles