
Сферические алгоритмы в вакууме — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.
Разбор очередного класса сортировок будет завершаться тестами для сортировок класса. Сегодня мы прогоним (не в смысле вышвырнем вон, а в смысле обкатаем на тестах) сортировки обменами. Сортировки других классов будем прогонять потом.
В сегодняшнем забеге участвуют:
Слабейшая группа
Эти алгоритмы ни на что не претендуют ввиду удручающей временной сложности. Тестируем их чисто «для справки».



Скорее даже интересно не насколько они хороши, а насколько плохи в деле, и кто из них хуже всех.
Основная группа
Тут собрались обменные сортировочки а-ля O(n2). Гномья сортировка (и её оптимизация) + всевозможные вариации пузырьковой сортировки.





Это самая интересная часть сегодняшних замеров. Именно среди представителей основной группы ожидается наиболее упорная борьба.
Сильнейшая группа
Одной из разновидностей пузырька — сортировке расчёской — удалось преодолеть барьер O(n2) и выйти по времени на заслуживающие уважение O(n log n). Так что в нашем соревновании у быстрой сортировки есть достойный соперник. Кроме того, испытаем недавно изобретённую k-sort, являющуюся разновидностью quick sort.



Сильнейших, кстати, сравним не только друг с другом. Им на некоторых наборах данных основная группа составит серьёзную конкуренцию.
Исходный код
Сортировки обменами на Python
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
//Придурковатая
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);
}
Время
Время везде измеряется в секундах с точностью до микросекунд.
Если алгоритму скармливается сразу пачка массивов (из десяти, ста или даже миллиона штук), то указано общее время.
Железо — мой верный старенький ноутбук, знававший лучшие времена. Так что, вполне возможно, у Вас всё будет работать гораздо быстрее.
Худшие из худших
Сразу разберёмся с аутсайдерами. Для них приготовлены массивы на 40 / 50 / 60 элементов, содержащие случайные числа от 0 до 9.
type=random, unique=False, min=0, max=9, count=1 | ||||||
---|---|---|---|---|---|---|
size | ||||||
40 | 50 | 60 | ||||
Python | PHP | Python | PHP | Python | PHP | |
![]() |
0.004 | 0.001 | 0.005 | 0.003 | 0.007 | 0.004 |
![]() |
0.007 | 0.009 | 0.018 | 0.009 | 0.018 | 0.023 |
![]() |
0.02 | 8.26647 | 0.053 | 20.8722 | 0.12901 | 45.9786 |
Туповатая сортировка на порядок быстрее чем придурковатая, а придурковатая на порядок быстрее чем вялая. Больше тут нечего смотреть.
Середнячки
Чтобы проверить середнячков, сгенерированы пачки из ста массивов по 100 элементов каждом (уникальные числа от 100 до 999), а также пачки из десяти массивов по 1000 элементов в каждом (уникальные числа от 1000 до 9999).
Подготовлены рандомные массивы, почти отсортированные массивы и реверсно упорядоченные массивы.
Середнячки: Рандом
type=random, unique=True | ||||
---|---|---|---|---|
size(от min до max) × count | ||||
100(от 100 до 999) × 100 | 1000(от 1000 до 9999) × 10 | |||
Python | PHP | Python | PHP | |
![]() |
0.14101 | 0.18901 | 1.59109 | 1.7251 |
![]() |
0.20601 | 0.22301 | 2.33013 | 2.09712 |
![]() |
0.15301 | 0.22901 | 1.6711 | 2.23613 |
![]() |
0.21601 | 0.26402 | 2.55515 | 2.73116 |
![]() |
0.16701 | 0.33402 | 1.7251 | 3.13218 |
Примерно одинаковые результаты у всех. Реализации на Питоне работают чуть быстрее чем на PHP.
Середнячки: Почти отсортировано
type=almost, unique=True | ||||
---|---|---|---|---|
size(от min до max) × count | ||||
100(от 100 до 999) × 100 | 1000(от 1000 до 9999) × 10 | |||
Python | PHP | Python | PHP | |
![]() |
0.009 | 0.005 | 0.009 | 0.005 |
![]() |
0.009 | 0.014 | 0.01 | 0.014 |
![]() |
0.01 | 0.01 | 0.011 | 0.008 |
![]() |
0.011 | 0.008 | 0.013 | 0.008 |
![]() |
0.011 | 0.017 | 0.013 | 0.017 |
Тоже одинаковые результаты у всех, плюс-минус. Из интересного: частичная упорядоченность данных в десятки раз улучшает показатели всех алгоритмов.
Середнячки: Реверс
type=reverse, unique=True | ||||
---|---|---|---|---|
size(от min до max) × count | ||||
100(от 100 до 999) × 100 | 1000(от 1000 до 9999) × 10 | |||
Python | PHP | Python | PHP | |
![]() |
0.26801 | 0.35902 | 3.10018 | 3.4292 |
![]() |
0.39602 | 0.45303 | 4.49726 | 4.19524 |
![]() |
0.22701 | 0.38402 | 2.48114 | 3.64421 |
![]() |
0.30202 | 0.42603 | 3.34419 | 4.17524 |
![]() |
0.30402 | 0.64404 | 3.36519 | 6.22036 |
Тут интересный вывод — обратная упорядоченность не так уж сильно влияет на скорость, которая упала всего в 2 раза по сравнению с рандомом.
Середнячки: Бинарник
type=random, unique=False, min=0, max=1 | ||||
---|---|---|---|---|
size × count | ||||
100 × 100 | 1000 × 10 | |||
Python | PHP | Python | PHP | |
![]() |
0.073 | 0.094 | 0.81105 | 0.86905 |
![]() |
0.10401 | 0.11301 | 1.16307 | 1.06606 |
![]() |
0.08801 | 0.12901 | 0.86405 | 1.18207 |
![]() |
0.11501 | 0.15001 | 1.30107 | 1.41608 |
![]() |
0.11401 | 0.25801 | 1.31908 | 2.46314 |
Из более-менее интересного: если вместо чисел от 100 до 9999 сортировать нули и единицы, то показатели скорости вырастут не сильно.
Чемпионы
Тут основная интрига в том, смогут ли сортировка расчёской и k-сортировка потеснить быструю с пьедестала?
Чемпионы: Рандом
Чтобы это выяснить, сформируем пакеты рандомных массивов: 10 штук по 10 тысяч элементов и 10 штук по 100 тысяч элементов. Хотел алгоритмам на вход дать и миллионники, но ноутбук не потянул. То оперативной памяти не хватает, то глубина рекурсии слишком велика.
type=random, unique=False, count=10 | ||||
---|---|---|---|---|
size(от min до max) | ||||
10000(от 10000 до 99999) | 100000(от 100000 до 999999) | |||
Python | PHP | Python | PHP | |
![]() |
0.80205 | 0.63104 | 10.4506 | 8.24647 |
![]() |
0.47703 | 1.64009 | 6.65138 | 26.5435 |
![]() |
0.90005 | 2.18613 | 15.8089 | 29.4867 |
K-сортировка на Питоне работает медленнее, а на PHP быстрее чем quick sort.
Сортировка расчёской по сравнению с быстрой выглядит солидно, хотя и уступает ей на всех тестах (и на этих и последующих) при любых наборах данных.
Однако есть у расчёски и важное неоспоримое преимущество. У неё нет рекурсии и поэтому в отличие от своих коллег она успешно обработывает массивы, состоящие из миллионов элементов.
Особые случаи
Хотя чемпионы скоростнее середнячков в сотни раз, на некоторых специфических наборах данных сортировки попроще показывают, что и они не лыком шиты.
Особые случаи: Почти отсортировано
Попробуем почти отсортированные массивы, только возьмём большего размера, чем те, что тестировали для середнячков.
Пакет из 10 массивов по 10 тысяч и пакет из 10 массивов по 100 тысяч элементов.
type=almost, unique=False | ||||
---|---|---|---|---|
size(от min до max) × count | ||||
10000(от 10000 до 99999) × 10 | 100000(от 100000 до 999999) × 10 | |||
Python | PHP | Python | PHP | |
![]() |
0.43202 | 0.058 | 0.81705 | 0.58003 |
![]() |
0.084 | 0.062 | 0.85805 | 0.54003 |
![]() |
0.11601 | 0.12401 | 1.41908 | 1.36008 |
![]() |
0.14001 | 0.11901 | 1.83411 | 1.41708 |
![]() |
0.13801 | 0.23101 | 1.6491 | 2.56915 |
![]() |
? | 122.088 | ? | ? |
![]() |
0.71504 | 1.58909 | 9.78356 | 19.4731 |
Быстрая сортировка тут вообще не присутствует — не хватило оперативной памяти. При этом рандомные массивы на 10/100 тысяч элементов quicksort обрабатывает на ура. k-sort столкнулась с аналогичными проблемами, потянула только 10-титысячники на PHP. Большие почти отсортированные массивы — это вырожденный случай для быстрой сортировки и её модификаций. Из-за такого расположения элементов рекурсия делит массив на части практически для каждый пары рядом стоящих элементов, что приводит к максимально возможному количеству вызовов рекурсии.
Кстати, аналогичная ситуация и с крупными реверсно упорядоченными массивам. Возникает та же проблема что и с почти упорядоченными — алгортитму приходится для каждой пары рядом стоящих элементов вызывать самого себя.
Сортировка расчёской хоть и работает в полтора-два раза медленнее чем quick или k (в общем случае), но при этом не имеет вышеозначенных переполнений памяти. Нет рекурсии — нет проблемы.
Ну и отметим, что все середнячки дружно обогнали чемпионов на крупных почти отсортированных массивах. Тут сработал принцип: «Тише едешь — дальше будешь».
Особые случаи: Миллион алых роз малых массивов
Малые массивы — стихия середнячков. Если нужно обрабатывать огромное количество небольших наборов чисел, то можно получить выигрыш по времени взяв «примитивную» пузырьковую или гномью сортировку. А быструю сортировку и иже с ней использовать для более масштабных задач.
type=random, unique=True | ||||
---|---|---|---|---|
size(от min до max) × count | ||||
5(от 10 до 99) × 1000000 | 10(от 10 до 99) × 1000000 | |||
Python | PHP | Python | PHP | |
![]() |
11.77267 | 17.888 | 24.29039 | 33.6659 |
![]() |
12.51872 | 18.165 | 29.33268 | 35.202 |
![]() |
15.44188 | 17.861 | 30.06672 | 36.7911 |
![]() |
14.18681 | 19.7831 | 31.65981 | 39.3533 |
![]() |
13.63978 | 24.3374 | 28.41662 | 52.864 |
![]() |
14.21881 | 21.1452 | 25.80548 | 32.5419 |
![]() |
14.58683 | 28.5016 | 24.85942 | 50.3139 |
![]() |
18.53806 | 30.7238 | 29.6647 | 58.2493 |
С обмеными сортировками всё понятно. Теперь приступим к действительно интересному — сортировкам вставками.
Ссылки
Excel-приложение AlgoLab, с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.
На Гугл-диске выложены также все массивы в виде JSON.
Вики/Wiki —