Pull to refresh

Comments 30

Жаль что нет в виде индийских танцев )))
А вот доказательство того, что расчёска работает за NlogN или хотя бы ссылка на него очень не помешала бы.
Мне тоже не помешало бы такое доказательство. В Интернете строгих выкладок не нашёл, ограничился данными из Википедии, которые, впрочем, запросто могут оказаться дезинформацией.
Как ни странно, на случайных наборах это почти N*log(N). Я проверил до N=10^8, число сравнений в среднем меньше, чем 3*N*log2N. Число обменов — ещё в 5 раз меньше.
Удивительно, что по сравнениям этот алгоритм на 20% быстрее сортировки Шелла, от которой он отличается только тем, что там пузырёк проходит по каждой разности до конца. По обменам они почти одинаковы.
Сложность обоих алгоритмов одинаковая (O(N^2)) пока не стали искать оптимальное число длины промежутков. Седжвик в своей докторской ускорил алгоритм до O(N^4/3). Сейчас вроде предложены и другие способы вычисления длинны, но вот их эффективность — не знаю.
На целых она отстаёт от QSort в 1.5 раза. Для алгоритма из 12 строк совсем неплохо…
Насколько я помню из курса в универе, одна из самых быстрых модификаций метода пузырька для больших объёмов данных является пирамидальная сортировка. Не очень, но странно, что тут она не упомянута.
Пирамидальная сортировка — не относится к классу сортировок обменами, она из семейства сортировок выбором. Самый общий принцип сортировок этого семейства — поиск максимального (минимального) элемента в неотсортированной части и вставка этого элемента на последнее (или первое, смотря в каком направлении сортировать) место в сортируемом подмассиве.

В пирамидальной сортировке этот поиск производится с помощью построения кучи из элементов массива.

Что касается пузырьковой сортировки, то там максимальный элемент на текущем отрезке целенаправленно не ищется. В результате многочисленных обменов максимумы «всплывают» на свои места, но это не есть поиск.
Извиняюсь, пропустил строчку про обмен.
Спасибо за очень интересую статью. Особенно за Рассческу. :)
тоже искал ее, имхо наглядно и очень полезно
Забавно, но я не знал глупой сортировки.
Прочитал пост, не удержался, написал быстренько все на java, с примерными замерами времени (разница System.time.currentTimeMillis() до и после вызова метода сортировки).
Результаты следующие.
«Глупая» сортировка зависает на неопределенное время на размере массива около 3000 элементов. На 2000 показывает время примерно 1600 мс.
«Пузырьковая» ведет себя лучше — около 25 мс на размере 2000 элементов. На 30 000 элементов — 2700 мс, почти три секунды.
«Шейкерная» сортировка — на размере 2000 элементов такие же, даже немного хуже (спишем на статистику) результаты. А вот на 30000 элементов разница в два раза — 1200 мс.
«Гребешковая» сортировка меня удивила. Я ожидал, что будет быстрее, но не на столько же! 2000 элементов — 11 мс. 30 000 элементов — 26 мс. 30 000 000 — 5500 мс.
Для сравнения — Arrays.sort(): 3000 элементов — 14-15 мс, 30000 — 30-40 мс, 30 000 000 — 3400 мс.

Вы заметили, что «гребешковая» сортировка получилась быстрее стандартной джавы? Меня это заинтересовало, и я начал увеличивать размер массива, и сравнивать результаты «гребешка» и Arrays.sort(). Получилось, что до 1 500 000 элементов «гребешок» быстрее, а вот дальше уже стандартная сортировка начинает работать быстрее.

Вот такие вот результаты :) Приятно, что реализация «гребешковой» сортировки тривиальна — можно реально использовать на небольших массивах с реальной пользой.
Кому интересно, привожу «тестовую лабораторию»:

Немного дурно пахнущего кода
package com.webprestige.winter.wallpaper;

import java.util.Random;

public class DesktopStarter {
	
	public static void main(String[] args) {
		int size = 30000000;
		Random r = new Random();
		int[] v = new int[size];
		for (int i = 0; i < size; v[i++] = r.nextInt(10000));
		long time = System.currentTimeMillis();
			coolSort(v);
		long endTime = System.currentTimeMillis();
		System.out.println("Time is " + (endTime - time));
		
//		 for(int i = 0; i < size; i++) {
//		 System.out.print(v[i] + " ");
//		 }
	}

	
private static void stupidSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
					break;
				}
			}
		}
	}

	private static void bulbSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
		}
	}
	
	private static void shakeSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
			
			for (int i = v.length - 1; i > 0; i--) {
				if (v[i] < v[i - 1]) {
					int t = v[i];
					v[i] = v[i - 1];
					v[i - 1] = t;
					end = false;
				}
			}
		}
	}
	
	
	
	

public static void coolSort(int[] v) {
		float loadFactor = 1.247f;
		int step = v.length;
		boolean end = false;
		int t;
		while (!end) {
			end = true;
			step /= loadFactor;
			if (step < 1) {
				step = 1;
			}
			for (int i = 0; i < v.length - 1; i++) {
				if ((i + step) < v.length) {
					if (v[i] > v[i + step]) {
						t = v[i];
						v[i] = v[i + step];
						v[i + step] = t;
						end = false;
					}
				} else {
					end = false;
				}

			}

		}
	}
}
Респект за практический экспресс-тест алгоритмов. Вот ради подобных комментариев и хочется писать статьи про алгоритмы.

Вы, кстати, не упомянули про «чет-нечет».

«Чет-нечет» — да не вопрос :)
private static void oddNotOddSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i += 1) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
			
			for (int i = 1; i < v.length - 1; i += 1) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
		}
	}

Результаты: для 3000 элементов — порядка 40 мс, для 3000 — 2600. По сути, также, как и пузырьковая
У Вас в циклах шаг 1? Нужно 2. Сейчас Ваша сортировка практически и является пузырьковой, поэтому такие близкие результаты.
Посмотрел, код, в целом можно считать, что верно, но местами много лишней работы. Не по нраву что в реализациях пузырька и шейкера внутренние циклы каждый раз проходят весь массив. Дело в том, что при вытеснении к краям максимумов и минимумов неотсортированная часть сужается и можно (и нужно) ограничиться обходом только неё. На десятках тысячах элементов это будет существенная экономия.
По мотивам статьи — не удержался, реализовал тоже :)
Вот исходник:
private static void bogosort(IntArray a) {
		boolean end = false;
		while(!end) {
			a.shuffle();
			end = true;
			for(int i = 0; i < a.size-1; i++) {
				if (a.get(i) > a.get(i+1)) {
					end = false;
					break;
				}
			}
		}
	}

Для справки — IntArray — тонкая обертка над массивом, используется в движке LibGdx. В данном случае то, что массив обернут и это влияет на производительность, думаю, не очень важно — посколько основные операции — перемешивание, а оно реализовано внутри этого класса без всяких оберток (фух, аж сам запутался :) ). Собственно, поэтому и использовал этот класс — лень было писать свою функцию перемешивания.

А вот и результаты:
1-6 элементов — 4 мс
7 — 20-30 мс
8 — 20-50 мс
9 — 150-600 мс
10 — 1000 и больше
11 — 2500 — 5000

На двенадцати элементах мой ноутбук начал гудеть вентилятором, но результат не выдавал никакой. Вывод — более полусотни лет прогресса, а больше десяти элементов отсортировать не можем :))
Отдельное спасибо за великолепные гифки, все сразу понятно даже без описаний.
Это статью просто боги писали, а не человек!
Огромное спасибо!
С начала марта будет мега-серия статей, посвящённая алгоритмам сортировок. Наконец-то в общий доступ выложу программу, с помощью которой подготавливаю эту гиф-анимацию

Следите за эфиром :)

Only those users with full accounts are able to leave comments. Log in, please.