Алгоритмы сортировки

Проблема упорядочивания данных с практической точки зрения: достоинства и недостатки пяти различных методов сортировки.

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

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

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

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

(метод назван также обменной сортировкой с выбором).

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

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

Метод Шелла Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Метод Хoopа Этот метод, называемый также быстрой сортировкой (QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).