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

Что будем сортировать, какого типа данные? Сортировать будем целочисленные данные в массиве, используя сравнение и обмен. Т.е. сравниваем 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