Как стать автором
Обновить

Сравнение сортировок обменами

Время на прочтение 9 мин
Количество просмотров 7.5K


Сферические алгоритмы в вакууме — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.

Разбор очередного класса сортировок будет завершаться тестами для сортировок класса. Сегодня мы прогоним (не в смысле вышвырнем вон, а в смысле обкатаем на тестах) сортировки обменами. Сортировки других классов будем прогонять потом.

В сегодняшнем забеге участвуют:

Слабейшая группа


Эти алгоритмы ни на что не претендуют ввиду удручающей временной сложности. Тестируем их чисто «для справки».

Придурковатая сортировка
Вялая сортировка
Тупая сортиртировка

Скорее даже интересно не насколько они хороши, а насколько плохи в деле, и кто из них хуже всех.

Основная группа


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

Гномья сортировка
Гномья сортировка (оптимизированная)
Пузырьковая сортировка
Коктейльная сортировка
Чётно-нечётная сортировка

Это самая интересная часть сегодняшних замеров. Именно среди представителей основной группы ожидается наиболее упорная борьба.

Сильнейшая группа


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

Сортировка расчёской
Быстрая сортировка
K-сортировка

Сильнейших, кстати, сравним не только друг с другом. Им на некоторых наборах данных основная группа составит серьёзную конкуренцию.

Исходный код


Сортировки обменами на 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Придурковатая/Stooge, Slow, Гномья/Gnome, Пузырьковая/Bubble, Шейкер/Shaker, Чёт-нечет/Odd-Even, Расчёска/Comb, Быстрая/Quick

Статьи серии


Теги:
Хабы:
Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку
+7
Комментарии 14
Комментарии Комментарии 14

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн