Алгоритмы сортировки
Алгоритмы сортировки
Алгоритмы сортировки
Проблема упорядочивания данных с практической
точки зрения:
достоинства и недостатки пяти различных
методов сортировки.
Сортировка применяется во всех без исключения
областях программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно
разбить на три части:
- сравнение, определяющее упорядоченность пары
элементов;
- перестановку, меняющую местами пару
элементов;
- собственно сортирующий алгоритм, который
осуществляет сравнение и перестановку элементов до тех пор, сока все элементы
множества не будут упорядочены.
Подобными свойствами обладают и те пять
алгоритмов сортировки, которые
рассмотрены ниже. Они отобраны из множества
алгоритмов, потому что,
во-первых, наиболее часто используются, а
во-вторых, потому что большинство остальных алгоритмов является различными
модификациями описанных здесь.
Метод пузырька.
( метод назван также обменной сортировкой с
выбором) .
Идея этого метода отражена в его названии.
Самые легкие элементы массива "всплывают" наверх, самые
"тяжелые" - тонут. Алгоритмически это можно реализовать следующим
образом. Мы будем просматривать весь массив "снизу вверх" и менять
стоящие рядом элементы в там случае, если "нижний" элемент меньше,
чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий”
элемент всего массива. Теперь повторим всю оперно для оставшихся
неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже"
первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он
является непревзойденным в своей неэффективности. Немного более эффективным, но
таким наглядным является второй метод.
Сортировка выбором
На этот раз при просмотре мaccива мы будем
искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем
его местами с первым. Затем повторим эту операцию, но начнем не с первого
элемента, а со второго. И будем продолжать подобным образом, пока не
рассортируем весь массив.
Метод Шелла
Этот метод был предложен автором Donald Lewis
Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале
ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга
элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно
уменьшается до единицы. Это означает, что на поздних стадиях сортировка
сводится просто к перестановкам соседних элементов (если, конечно, такие
перестановки являются необходимыми).
Метод Хoopа
Этот метод, называемый также быстрой
сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony
Richard Hoare).
Суть метода заключается в том, чтобы найти
такой элемент множества, подлежащего сортировке, который разобьет его на два
подмножества: те элементы, что меньше делящего элемента, и те, что не меньше
его. Эту идею можно реализовать многими способами.
|