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

в 12:02, , рубрики: php, python, Алгоритмы, алгоритмы сортировки, Программирование, Тестирование IT-систем

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

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

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

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

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

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

Сравнение сортировок обменами - 2 Придурковатая сортировка
Сравнение сортировок обменами - 3 Вялая сортировка
Сравнение сортировок обменами - 4 Тупая сортиртировка

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

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

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

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

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

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

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

Сравнение сортировок обменами - 10 Сортировка расчёской
Сравнение сортировок обменами - 11 Быстрая сортировка
Сравнение сортировок обменами - 12 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
Сравнение сортировок обменами - 13 0.004 0.001 0.005 0.003 0.007 0.004
Сравнение сортировок обменами - 14 0.007 0.009 0.018 0.009 0.018 0.023
Сравнение сортировок обменами - 15 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
Сравнение сортировок обменами - 16 0.14101 0.18901 1.59109 1.7251
Сравнение сортировок обменами - 17 0.20601 0.22301 2.33013 2.09712
Сравнение сортировок обменами - 18 0.15301 0.22901 1.6711 2.23613
Сравнение сортировок обменами - 19 0.21601 0.26402 2.55515 2.73116
Сравнение сортировок обменами - 20 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
Сравнение сортировок обменами - 21 0.009 0.005 0.009 0.005
Сравнение сортировок обменами - 22 0.009 0.014 0.01 0.014
Сравнение сортировок обменами - 23 0.01 0.01 0.011 0.008
Сравнение сортировок обменами - 24 0.011 0.008 0.013 0.008
Сравнение сортировок обменами - 25 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
Сравнение сортировок обменами - 26 0.26801 0.35902 3.10018 3.4292
Сравнение сортировок обменами - 27 0.39602 0.45303 4.49726 4.19524
Сравнение сортировок обменами - 28 0.22701 0.38402 2.48114 3.64421
Сравнение сортировок обменами - 29 0.30202 0.42603 3.34419 4.17524
Сравнение сортировок обменами - 30 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
Сравнение сортировок обменами - 31 0.073 0.094 0.81105 0.86905
Сравнение сортировок обменами - 32 0.10401 0.11301 1.16307 1.06606
Сравнение сортировок обменами - 33 0.08801 0.12901 0.86405 1.18207
Сравнение сортировок обменами - 34 0.11501 0.15001 1.30107 1.41608
Сравнение сортировок обменами - 35 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
Сравнение сортировок обменами - 36 0.80205 0.63104 10.4506 8.24647
Сравнение сортировок обменами - 37 0.47703 1.64009 6.65138 26.5435
Сравнение сортировок обменами - 38 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
Сравнение сортировок обменами - 39 0.43202 0.058 0.81705 0.58003
Сравнение сортировок обменами - 40 0.084 0.062 0.85805 0.54003
Сравнение сортировок обменами - 41 0.11601 0.12401 1.41908 1.36008
Сравнение сортировок обменами - 42 0.14001 0.11901 1.83411 1.41708
Сравнение сортировок обменами - 43 0.13801 0.23101 1.6491 2.56915
Сравнение сортировок обменами - 44 ? 122.088 ? ?
Сравнение сортировок обменами - 45 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
Сравнение сортировок обменами - 46 11.77267 17.888 24.29039 33.6659
Сравнение сортировок обменами - 47 12.51872 18.165 29.33268 35.202
Сравнение сортировок обменами - 48 15.44188 17.861 30.06672 36.7911
Сравнение сортировок обменами - 49 14.18681 19.7831 31.65981 39.3533
Сравнение сортировок обменами - 50 13.63978 24.3374 28.41662 52.864
Сравнение сортировок обменами - 51 14.21881 21.1452 25.80548 32.5419
Сравнение сортировок обменами - 52 14.58683 28.5016 24.85942 50.3139
Сравнение сортировок обменами - 53 18.53806 30.7238 29.6647 58.2493

С обмеными сортировками всё понятно. Теперь приступим к действительно интересному — сортировкам вставками.

Ссылки

Excel-приложение AlgoLab, с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.

На Гугл-диске выложены также все массивы в виде JSON.

Вики/WikiПридурковатая/Stooge, Slow, Гномья/Gnome, Пузырьковая/Bubble, Шейкер/Shaker, Чёт-нечет/Odd-Even, Расчёска/Comb, Быстрая/Quick

Автор: Валерий Макаров

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js