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