- PVSM.RU - https://www.pvsm.ru -
Сферические алгоритмы в вакууме [1] — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.
Разбор очередного класса сортировок будет завершаться тестами для сортировок класса. Сегодня мы прогоним (не в смысле вышвырнем вон, а в смысле обкатаем на тестах) сортировки обменами. Сортировки других классов будем прогонять потом.
В сегодняшнем забеге участвуют:
Эти алгоритмы ни на что не претендуют ввиду удручающей временной сложности. Тестируем их чисто «для справки».
Придурковатая сортировка
Вялая сортировка
Тупая сортиртировка
Скорее даже интересно не насколько они хороши, а насколько плохи в деле, и кто из них хуже всех.
Тут собрались обменные сортировочки а-ля O(n2). Гномья сортировка (и её оптимизация) + всевозможные вариации пузырьковой сортировки.
Гномья сортировка
Гномья сортировка (оптимизированная)
Пузырьковая сортировка
Коктейльная сортировка
Чётно-нечётная сортировка
Это самая интересная часть сегодняшних замеров. Именно среди представителей основной группы ожидается наиболее упорная борьба.
Одной из разновидностей пузырька — сортировке расчёской — удалось преодолеть барьер O(n2) и выйти по времени на заслуживающие уважение O(n log n). Так что в нашем соревновании у быстрой сортировки есть достойный соперник. Кроме того, испытаем недавно изобретённую k-sort [2], являющуюся разновидностью quick sort.
Сортировка расчёской
Быстрая сортировка
K-сортировка
Сильнейших, кстати, сравним не только друг с другом. Им на некоторых наборах данных основная группа составит серьёзную конкуренцию.
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
//Придурковатая
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 [3], с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.
На Гугл-диске [4] выложены также все массивы в виде JSON.
Вики/Wiki — Придурковатая [5]/Stooge [6], Slow [7], Гномья [8]/Gnome [9], Пузырьковая [10]/Bubble [11], Шейкер [12]/Shaker [13], Чёт-нечет [14]/Odd-Even [15], Расчёска [16]/Comb [17], Быстрая [18]/Quick [19]
Автор: Валерий Макаров
Источник [20]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/284583
Ссылки в тексте:
[1] Сферические алгоритмы в вакууме: https://habr.com/post/414653/
[2] недавно изобретённую k-sort: https://habr.com/post/333710/
[3] Excel-приложение AlgoLab: https://habr.com/post/414447/
[4] Гугл-диске: https://drive.google.com/drive/folders/1Nrf6WrAsaWLcMAToXLkBa-sr0YLRBDts
[5] Придурковатая: https://ru.wikipedia.org/wiki/Stooge_sort
[6] Stooge: https://en.wikipedia.org/wiki/Stooge_sort
[7] Slow: https://en.wikipedia.org/wiki/Slowsort
[8] Гномья: https://ru.wikipedia.org/wiki/%D0%93%D0%BD%D0%BE%D0%BC%D1%8C%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
[9] Gnome: https://en.wikipedia.org/wiki/Gnome_sort
[10] Пузырьковая: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC
[11] Bubble: https://en.wikipedia.org/wiki/Bubble_sort
[12] Шейкер: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D1%88%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC
[13] Shaker: https://en.wikipedia.org/wiki/Cocktail_shaker_sort
[14] Чёт-нечет: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%87%D1%91%D1%82-%D0%BD%D0%B5%D1%87%D0%B5%D1%82
[15] Odd-Even: https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort
[16] Расчёска: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%80%D0%B0%D1%81%D1%87%D1%91%D1%81%D0%BA%D0%BE%D0%B9
[17] Comb: https://en.wikipedia.org/wiki/Comb_sort
[18] Быстрая: https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
[19] Quick: https://en.wikipedia.org/wiki/Quicksort
[20] Источник: https://habr.com/post/415691/?utm_source=habrahabr&utm_medium=rss&utm_campaign=415691
Нажмите здесь для печати.