О сортировках (пузырьковой, быстрой, расческой...)

Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.

Что будем сортировать, какого типа данные? Сортировать будем целочисленные данные в массиве, используя сравнение и обмен. Т.е. сравниваем m[i] и m[j] (i<j) элементы массива и если j-й «меньше» i-го, то меняем их местами. В результате массив будет отсортирован по возрастанию.
Замечание: сравнивать будем так m[j]/10<m[i]/10. Это сделано для того, чтобы увидеть, как сортируются элементы с одинаковыми ключами. При таком сравнении 30<40, но 30=31=32… Устойчивая (или стабильная сортировка) не меняет порядок элементов, имеющих одинаковые ключи сравнения (в нашем примере ключ сравнения — это целая часть от значения элемента/10)

Вот начальный (неотсортированный) массив:
50 32 40 31 20 30 10
а вот отсортированный:
10 20 32 30 31 40 50
Обратите внимание: порядок элементов 32,31,30 изменился, т.е. сортировка не устойчивая (не стабильная).

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

Простая сортировка

Проход перебирает все элементы массива и в цикле сравнивает текущий элемент со всеми последующими.
void sorto(int *m,int n)  // обычная, простая, примитивная... сортировка
{	int tmp; 
	for (int i=0;i<n-1;++i) { // проход
		for (int j=i+1; j<n;++j) { // цикл
			if (m[j]/10<m[i]/10) { // j-й меньше, его надо поменять с i-м 
				tmp=m[i];
				m[i]=m[j];
				m[j]=tmp; 	
			}
		}
	}
}
Результат работы
10 20 32 31 30 40 50
Плюсы простой сортировки — они простая в реализации и устойчивая.
Минусы — она очень медленная, т.к. происходит очень много операций сравнения. Каждый из n элементов сравнивается со всеми последующими, поэтому количество сравнений ~n*n/2. Если n=100000, то сравнений 5 миллиардов. Правда, если n=1000, то сравнений «только» 500 тыс и современный компьютер может это сделать менее чем за секунду, так что при небольшом количествах это сортировка годится.Ели один важный минус — если данные почти отсортированы (из 100тыс элементов только 10 стоят не на своих местах), то все равно время работы изменится мало, т.к. операций сравнения будет столько же.Попробуем улучшить алгоритм и перейдем к

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

Она же «Bubble» она же «пузырёк.» Внутренний цикл снова и снова пробегает по массиву и сравнивает текущий элемент с предыдущим (поэтому пробег начинается с 1) и если текущий меньше, переставляет его с предыдущим. Место перестановки запоминается в переменной k, и в конце прохода в k находится индекс, начиная с которого массив отсортирован.
void sortb(int *m,int n) 
{	int tmp,k;
	while(n>1) { // проход проверят, не пора ли заканчивать 
		k=0; // нет перестановок
		for (int i=1; i<n;++i) {
			if(m[i]/10<m[i-1]/10) {
				tmp=m[i-1];
				m[i-1]=m[i];
				m[i]=tmp; 	
				k=i; // в к будет последний переставленный элемент
			}
		}
		n=k; // с k все отсортировано
	}
}
В самом худшем случае (когда исходный массив отсортирован в обратном порядке, получается те же n*n/2 сравнений. А в лучшем или в хорошем"? Лучший случай — это когда массив полностью отсоротирован. Тогда на первом проходе ничего переставляться не будет, в конце прохода n присвоится 0 (k=0) и второго прохода не будет. Вместо 100тыс проходов — всего 1! Замечательно, но что, если массив отсортирован, но не совсем. Например переставим в отсортированном массиве минимальный и максимальный элементы и будем сортировать этот «проблемный» массив (помним, что 30-32 имеют одинаковый ключ):
50 20 32 31 30 40 10
На первом шаге 1 прохода «20» сравнивается с «50» и происходит обмен. На следующем шаге «32» сравнивается снова с «50» (он ведь теперь занял место «20». В результате в конце первого прохода «50» займет место в конце, а все остальные сдвинутся на 1 позицию к началу массива. А что произойдет с «10», который был в конце? Он тоже передвинется на 1 позицию к началу. Если представить, что начальные позиции вверху, а конечные внизу, «на дне», то в результате прохода самый тяжелый окажется на дне, а самый легкий «всплывет» на одну позицию. В одной из статей тяжелые элементы называют «зайцам», а легкие — «черепахами». Во время прохода «заяц» быстро бежит в конец (или тонет), пока не встретит более весомого зайца (который примет эстафету и побежит дальше) или пока не займет свое место. А легкие элементы всплывают на одну позицию. Если самый легкий занимает n-ю позицию, то нужно n проходов, чтобы ему добраться до своего места. Самый тяжелый («дробинка») за один проход быстро тонет, а самый легкий («пузырек») -медленно всплывает. Тот пузырек, которому всплывать дольше всех и определяет общее число необходимых проходов. Если самый легкий в конце массива, надо столько проходов, сколько элементов в массиве.

Что же делать с «черепахами», чтобы они не мешали так сильно. На помощь приходит

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

Почему в пузырьковой сортировке тяжелые элементы быстро тонут, а легкие — медленно всплывают? Потому что цикл сравнения продвигается от начала массива к концу и «тащит» с собой тяжелые элементы. А если двигаться от конца к началу, то легкие станут быстро всплывать, а тяжелые медленно тонуть. Самый легкий за один проход переместится из конца в начало. Шейкерная сортировка на четных проходах двигается из начала в конец, а на нечетных наборот и наш проблемный массив отсортирует за 3 прохода. Для почти отсортированного массива шейкерная сортировка может оказаться намного быстрее «пузырька», но для случайно отсортированного исходного массива выигрыш обычно не сильно велик.

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

Или гребёнкой. Снова спросим почему пузырек медленно всплывает? Потому что за проход он перемещается на 1 позицию. А почему он перемещается только на 1 позицию? Потому, что сравниваются и переставляются соседние элементы. Так давайте сравнивать не соседние элементы, а находящиеся на расстоянии s (постепенно уменьшая s с каждым проходом). Реализуя эту идею на практике, приходим к сортировке расческой.
void sortc(int *m,int n) 
{	int tmp,k;
	int s=n; // готовим начальный шаг
	long long cnt=0;
	while(n>1) {
		s/=1.247f; // шаг на этом проходе.  На первом проходе получается примерно 80% от размера массива,
                                        // и легкие элементы в хвосте переносятся в первые 20% 
		if (s<1) s=1; // 0 быть не может, присвоим 1
		k=0; // нет перестановок
		for (int i=0; i+s<n;++i) { // двигаемся, пока сравниваемый элемент (на s от текущего) в массиве
			if(m[i]/10>m[i+s]/10) {
				tmp=m[i];
				m[i]=m[i+s];
				m[i+s]=tmp; 	
				k=i;
			}
			++cnt;
		}
		if (s==1) // шаг 1, как в обычном пузырьке. Включаем контроль	
			n=k+1; 
	}
}
Идея вроде простая и алгоритм не сложный, но результат впечатляет. Сортировка расческой оказывается намного быстрее, чем пузырек/шейкер, она даже может обогнать «быструю» сортировку qsort. Но есть и минус — она не устойчивая (что интуитивно понятно).

Быстрая сортировка qsort

Функция быстрой сортировки нашего массива очень простая:
// компаратор для qsort
int fcomp(const void *i, const void *j) 
{	return (*(int *)i)/10 - (*(int *)j)/10;
}
void sortq(int *m,int n) 
{
	qsort(m,n,sizeof(int),&fcomp);  
}
Простая оно потому, что использует стандартную быструю сортировку qsort. Посмотрим снова на приведенные алгоритмы. Во всех выбираются и сравниваются пары элементов m[i] и m[j]. Но что такое m[i]? Это i-й элемент в массиве целых чисел m или «элемент, расположенный по адресу Ai=m+i*<sizeof(int)>». Соответственно, j-й элемент расположен по адресу Aj=m+j*<sizeof(int)>. Итак, мы сравниваем элементы по адресами Ai и Aj и переставляем их, если Aj<Ai (меньше в смысле некоторой операции сравнения, которую мы применяем). Так вот, функция qsort — это некий «сортировочный комбайн», который выбирает, сравнивает и переставляет элементы из нашего массива (который мы ей передаем первым параметром). Естественно, надо знать количество элементов в массиве и оно передается вторым параметром. А как qsort определит, где находится i-й элемент? Очень просто — прибавив к адресу массива i*<размер элемента в байтах>. Этот <размер в байтах> передается третьим параметром. Хорошо, но как qsort сравнит элементы, ведь у нас хитрый способ сравнения? Она не сравнивает сама, она использует нашу функцию сравнения fcomp, адрес которой передается в 4 параметре. Когда qsort по своему внутреннему алгоритму решит, что надо сравнить i и j-й элементы, она передаст их адреса в качестве 1 и 2 параметров функции fcomp, которая возвращает результат сравнения <0, =0, >0 в зависимости от того, меньше первый параметр второго, равен ему или больше. Если qsort видит, что i<j но fcomp(&m[i],&m[j])>0 она просто переставит элементы в массиве (размер элемента она знает, а содержимое ей не важно).

Время сортировки 100001 элемента

Измерим время сортировки для массива, содержащего 100001 элемент на компьютере с процессором Intel i5 (3.3Ггц).Время указано в сек, через дробь указано количество проходов (для быстрой сортировки оно неизвестно).Как и ожидалось, шейкерная сортировка на проблемном массиве (который полностью упорядочен, только первый и последний элементы переставлены) абсолютный лидер. Она идеально «заточена» под эти данные. Но на случайных данных сортировки расческой и qsort не оставляют соперницам шанса. Пузырьковая сортировка на проблемном массиве показывает двукратное увеличение скорости по сравнению с случайным просто потому, что количество операций перестановки на порядки меньше.
Сортировка Простая Пузырьковая Шейкерная Расчёской Быстрая (qsort)
Стабильная + + + - -
Случайный 23.1/100000 29.1/99585 19.8/50074 0.020/49 0.055
Проблемный 11.5/100000 12.9/100000 0.002/3 0.015/48 0.035
Обратный 18.3/100000 21.1/100000 21.1/100001 0.026/48 0.037


А теперь вернемся к истокам, к пузырьковой сортировке и воочию посмотрим на процесс сортировки. Видите, как на первом проходе тяжелый элемент (50) переносится в конец?

Сравниваемые элементы показаны в зеленых рамках, а переставленные — в красных

Дополнение после публикации

Я ни коей мере не считаю qsort плохой или медленной — она достаточно быстра, функциональна и при возможности следует пользоваться именно ею. Да, ей приходится тратить время на вызов функции сравнения и она уступила «расческе», которая сравнивает «по месту». Это отставание несущественно (сравните с отставанием пузырька от qsort, которое будет увеличиваться при росте массива). Пусть теперь надо сравнивать не числа, а какую-то сложную структуру по определенному полю и пусть эта структура состоит из 1000 байтов. Поместим 100тыс элементов в массив (100мб — это кое-что) и вызовем qsort. Функция fcomp (функция-компаратор) сравнит нужные поля и в результате получится отсортированный массив. При этом при перестановке элементов qsort придется 3 раза копировать фрагменты по 1000 байтов. А теперь «маленькая хитрость» — создадим массив из 100тыс ссылок на исходные элементы и передадим в qsort начало этого массива ссылок. Поскольку ссылка занимает 4 байта (в 64 битных 8), а не 1000, то при обмене ссылок qsort надо поменять эти 4/8 байтов. Разумеется, нужно будет изменить fcomp, поскольку в качестве параметров она теперь получит не адреса элементов, а адреса адресов элементов (но это несложное изменение). Зато теперь можно сделать несколько функций сортировки (каждая сортирует по своему полю структуры). И даже, при необходимости, можно сделать несколько массивов ссылок. Вот сколько возможностей дает qsort!

Кстати: использование ссылок на объекты вместо самих объектов может быть полезно не только при вызове qsort, но и при применении таких контейнеров как vector, set или map.

Количество сравнений и обменов

В следующей таблице показывается количество операций сравнения/количество обменов для каждой сортировки. Для qsort количество обменов неизвестно, поэтому показано только количество сравнений. Видно, что для случайного массива количество сравнений минимально у qsort.
Сортировка Простая Пузырьковая Шейкерная Расчёской Быстрая (qsort)
Случайный 5'000'050'000/1'131'715'503 4'999'702'086/2'507'142'238 3'341'739'679/2'507'142'238 4'489'129/714'533 1'915'414
Проблемный 5'000'050'000/199'999 5'000'050'000/199'999 299'997/199'999 4'395'305/91'829 1'588'741
Обратный 5'000'050'000/5'000'050'000 5'000'050'000/5'000'050'000 5'000'050'000/5'000'050'000 4'395'305/233'210 1'588'741


Комментарии 13

    +7
    Визуализация 15 алгоритмов сортировки

    www.youtube.com/watch?v=rQtereWDc24&feature=youtu.be

    1. Selection Sort
    2. Insertion Sort
    3. Quick Sort (LR pointers)
    4. Merge Sort
    5. Heap Sort
    6. Radix Sort ( LSD )
    7. Radix Sort ( MSD )
    8. std::sort (gcc)
    9. std::stable_sort (gcc)
    10. shell sort
    11. bubble sort
    12. Cocktail Shaker Sort
    13. Gnome Sort
    14. Bitonic sort
    15. Bogo Sort
      +1
      Назвать «сортировку выбором» (реже «простым выбором») «простой сортировкой»… Спасибо, посмеялся.

      Ещё более смешно то, что для большинства сортировок написан код с прямым сравнением элементов непосредственно в этом коде, а для быстрой сортировки используется стандартная функция, реализующая сравнение через вызов функции, что в разы увеличивает время выполнения алгоритма. Разумеется, в столь заведомо неравных условиях быстрая сортировка проигрывает. Хотите, чтобы над Вашими результатами не смеялись — публикуйте результаты сравнения при использовании этой функции во ВСЕХ алгоритмах.
        –1
        Насчет сортировки выбором соглашусь. Хотя у меня почему-то такое название ассоциируется с другим алгоритмом. Если статья Вам не интересна, это не значит, что она не интересна или бесполезна другим. Я писал для начинающих, для тех, кто в 1001 раз задает на форумах вопросы «сортировка не работает», «надо сделать сортировкау пузырьком, как?» и т.п.

        Что касается быстрой сортировки. Задачи реализовывать самому этот алгоритм не стояло. В статье показано, что можно использовать стандартный (если он доступен) и он дает весьма хороший результат (обгоняя пузырек и шейкер в 1000 раз на массиве в 100тыс элементов).

        Минусов наставили, желание писать дальше для новичков отбили. Пишите тогда сами, а я посмотрю, что у Вас получится и найду недостатки (это гораздо проще, чем заметить достоинства).
          –1
          Если над моими статьями будут смеяться те, кто сам ничего написать не может, то пусть смеются. Я считаю, что поставленную задачу — дать новичкам практическое понимание сортировки и руководство к действию выполнил. Показал, почему пузырьковая сортировка работает медленно, на каких данных. Показал, как пользоваться стандартной qsort (с этим у новичков бывают проблемы).

          Посмотреть на видео с сортировками, конечно, интересно, но для новичков практической пользы немного, имхо. Он пишет «помогите сделать/исправить сортировку, она не работает», а я ему ссылку на видео дам? В общем, осталось дождаться мнений начинающих программистов и, исходя из них, решать — стоит ли заниматься этим дальше или нет.
          0
          Большой плюс статьи — объяснение принципов работы и указание на недостатки реализаций для конкретных случаев. То есть позволяет задуматься над поставленной задачей, а не решать ее в лоб каким-нибудь привычным способом.
            +1
            Забавно, что гифка с сортировкой, характеризует и статью в целом. Выполнена небрежно и с ошибка. Отмазки в стиле «для новичков» не канают, потому что подобных статей вагон и маленькая тележка, и большинство из них выполнены на гораздо более высоком уровне, и можно было бы понять если бы данная статья была написана ради инвайта, но это не первая ваша статья. И почему эта статья находится на гике а не на хабре?
              0
              Так приведите ссылку на более хорошую статью, все только спасибо скажут. И где ошибки в гифке?
                +2
                вот http://habrahabr.ru/post/104697/ или вот http://habrahabr.ru/post/133996/ достаточно вбить в поиск.
                Ошибка на гифке 32 не меняется с 31, а 31 не меняется с 30 в конце массив не отсортирован.
                И да зачем в простой сортировке вы сравниваете значения так? if (m[j]/10<m[i]/10) при том, что ваш массив типа int он будет работать некорректно, это специально сделано чтобы новички искали ошибку? И судя по всему вы гифку делали с таким же сравнением.

              0
              Я специально сделал сравнение по ключу, который есть число/10 и отметил это в статье, чтобы у 30,31,32 был одинаковый ключ. А сделал для того, чтобы увидеть, как сортировки поступают со значениями, имеющими одинаковый ключ (т.е. устойчивые они или нет), И это тоже в статье написано. Выходит, Вы пробежались по ней не читая и сразу стали высказывать свое «фи». Печально.
                0
                В коде сортировки пузырьком нет деления на 10, так что выглядит это как баг.
                  0
                  Упс — это действительно мой косяк (копипаст подвел). Спасибо, исправил
                0
                Еще одна страница, где наглядно показана работа различных сортировок [url]https://www.toptal.com/developers/sorting-algorithms [/url]

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

                Самое читаемое