Пользователь
0,1
рейтинг
3 декабря 2013 в 04:37

Разработка → Пузырьковая сортировка и все-все-все


Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги.

image: пузырьки



Сегодня поговорим о простейших сортировках обменами.

Если кому интересно, скажу, что есть и другие классы – сортировки выбором, сортировки вставками, сортировки слиянием, сортировки распределением, гибридные сортировки и параллельные сортировки. Есть, кстати, ещё эзотерические сортировки. Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.

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

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O(n2). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте, в Википедии или где-нибудь ещё.

Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

Глупая сортировка


Сортировка и впрямь глупейшая. Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы встретим пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся на круги своя, то бишь в самое начало. Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё сызнова. Продолжаем до тех пор пока массив потихоньку-полегоньку не отсортируется.



«Так любой дурак сортировать умеет» — скажете Вы и будете абсолютно правы. Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ. Сейчас у него временная сложность O(n3), произведя одну коррекцию, мы уже доведём до O(n2), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O(n log n) – и это будет вовсе не «Быстрая сортировка»!

Внесём в глупую сортировку одно-единственное улучшение. Обнаружив при проходе два соседних неотсортированных элемента и поменяв их местами, не станем откатываться в начало массива, а невозмутимо продолжим его обход до самого конца.

В этом случае перед нами не что иное как всем известная…

Пузырьковая сортировка


Или сортировка простыми обменами. Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.



Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Шейкерная сортировка


Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 1800 и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.



Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

Как видите, если к процессу перебора подойти творчески, то выталкивание тяжёлых (лёгких) элементов к концам массива происходит быстрее. Поэтому умельцы предложили для обхода списка ещё одну нестандартную «дорожную карту».

Чётно-нечётная сортировка


На сей раз мы не будем сновать по массиву взад-вперёд, а снова вернёмся к идее планомерного обхода слева-направо, но только сделаем шире шаг. На первом проходе элементы с нечётным ключом сравниваем с соседями, зиждущимися на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5-й с 6-м и так далее). Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.



В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.

Разберём последнее покращення* для Сортування бульбашкою** — Сортування гребінцем***. Этот способ упорядочивает весьма шустро, O(n2) – его наихудшая сложность. В среднем по времени имеем O(n log n), а лучшая даже, не поверите, O(n). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии. Впрочем, я обещал, что в крейсерские скорости мы сегодня углубляться не станем, засим умолкаю и перехожу непосредственно к алгоритму.


Во всём виноваты черепашки


Небольшая предыстория. В 1980 году Влодзимеж Добосиевич пояснил почему пузырьковая и производные от неё сортировки работают так медленно. Это всё из-за черепашек. «Черепахи» — небольшие по значению элементы, которые находятся в конце списка. Как Вы, возможно, заметили пузырьковые сортировки ориентированы на «кроликов» (не путать с «кроликами» Бабушкина) – больших по значению элементов в начале списка. Они весьма резво перемещаются к финишу. А вот медлительные пресмыкающиеся на старт ползут неохотно. Подгонять «тортилл» можно с помощью расчёски.

image: виноватая черепашка

Сортировка расчёской


В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.



Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения:



Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.

Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.

— Примечания

* покращення (укр.) – улучшение
** Сортування бульбашкою (укр.) – Сортировка пузырьком
*** Сортування гребінцем (укр.) – Сортировка расчёской
Какие алгоритмы из этой статьи Вы уже знали?
57%
(772)
Глупая сортировка
91%
(1234)
Пузырьковая сортировка
40%
(538)
Шейкерная сортировка
15%
(209)
Чётно-нечётная сортировка
17%
(231)
Сортировка расчёской

Проголосовало 1352 человека. Воздержалось 283 человека.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (27)

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

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

      Что касается пузырьковой сортировки, то там максимальный элемент на текущем отрезке целенаправленно не ищется. В результате многочисленных обменов максимумы «всплывают» на свои места, но это не есть поиск.
      • +1
        Извиняюсь, пропустил строчку про обмен.
  • +1
    Bogosort наше всё
  • +2
    Спасибо за очень интересую статью. Особенно за Рассческу. :)
  • +2
    Может кому будет полезно… Реализация наиболее известных сортировок на Котлине: github.com/vania-pooh/kotlin-algorithms
  • 0
    Поделюсь ссылкой.
    • 0
      тоже искал ее, имхо наглядно и очень полезно
  • +1
    Забавно, но я не знал глупой сортировки.
  • +5
    Прочитал пост, не удержался, написал быстренько все на 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;
    				}
    
    			}
    
    		}
    	}
    }
    
    • +1
      Респект за практический экспресс-тест алгоритмов. Вот ради подобных комментариев и хочется писать статьи про алгоритмы.

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

      • +1
        «Чет-нечет» — да не вопрос :)
        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. По сути, также, как и пузырьковая
        • 0
          У Вас в циклах шаг 1? Нужно 2. Сейчас Ваша сортировка практически и является пузырьковой, поэтому такие близкие результаты.
    • 0
      Посмотрел, код, в целом можно считать, что верно, но местами много лишней работы. Не по нраву что в реализациях пузырька и шейкера внутренние циклы каждый раз проходят весь массив. Дело в том, что при вытеснении к краям максимумов и минимумов неотсортированная часть сужается и можно (и нужно) ограничиться обходом только неё. На десятках тысячах элементов это будет существенная экономия.
  • +1
    По мотивам статьи — не удержался, реализовал тоже :)
    Вот исходник:
    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

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.