Метод пузырька

Сортировка прямым обменом

Сортировка прямым выбором

Сначала выбираем элемент с наименьшим ключом. Затем меняем его местами с первым элементом. Среди оставшихся ищем элемент с наименьшим ключом и меняем его и второй элемент местами. Процесс продолжается, пока не останется один, самый большой элемент.

Число сравнений не зависит от порядка элементов и равно

(n-1)+(n-2)+…+1 = (n2-n)/2 = Ө(n2).

Число обменов будет Ө(n).

Сортировку выбором можно использовать, если сложность обмена значительно больше, чем сложность сравнения.

По-другому называется пузырьковой сортировкой.

Сравниваем между собой два соседних элемента. Если элемент с большим ключом левее, то меняем их местами. В результате прохода по всему массиву наибольший элемент окажется на последнем месте (“всплывет”). На следующем проходе на место встанет второй по величине ключа элемент. Всего для сортировки требуется n-1 проход.

Количество сравнений и обменов в худшем случае равно (n2-n)/2 = Ө(n2).

Все простые алгоритмы сортировки устойчивы.

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

Практически каждый алгоритм сортировки можно разбить на три части:

ü сравнение, определяющее упорядоченность пары элементов;

ü перестановку, меняющую местами пару элементов;

ü собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены.

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

Метод назван также обменной сортировкой с выбором. Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся не отсортированными N-1 элементов (т.е. для тех, которые лежат "ниже" первого). Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.