Простые алгоритмы сортировки

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

Алгоритм пузырька (BubbleSort)

Идея алгоритма заключается в следующем. Сравним элементы массива с индексами 1 и 2. Если первый больше второго, то поменяем эти элементы местами. Затем таким же образом сравним (и, если нужно, переставим) элементы с индексами 2 и 3, потом 3 и 4 и т.д. После сравнения элементов (n–1) и n первый проход алгоритма завершается. Можно гарантировать, что после этого прохода максимальный элемент массива находится на последнем месте (т.е. имеет индекс n). На втором проходе сравниваем пары 1 и 2, 2 и 3,... (n–2) и (n–1). Далее аналогично. После n–1 прохода все элементы займут свои законные места.

У многих программистов появляется желание сократить число проходов, отмечая с помощью специального флажка, были ли сделаны какие-либо перестановки на очередном проходе. Если ни одной перестановки за весь проход не было, то массив, очевидно, уже отсортирован и работу алгоритма можно завершить досрочно. Однако такое усовершенствование редко дает заметный выигрыш. Нетрудно показать, что для массива, заполненного случайным образом, с вероятностью 75 % все равно будут выполнены все проходы алгоритма.

Алгоритм выбора (SelectionSort)

Идея этого алгоритма еще проще. Найдем минимальный элемент массива и поменяем его местами с первым элементом. Затем повторим ту же процедуру, начиная со второго элемента массива, затем начиная с третьего и т.д. После n–1 проходов все элементы станут на места.