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