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

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

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

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

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

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

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

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

- собственно сортирующий алгоритм, который осуществляет сравнение и

перестановку элементов до тех пор, сока все элементы множества не будут

упорядочены.

Подобными свойствами обладают и те пять алгоритмов сортировки, которые

рассмотрены ниже. Они отобраны из множества алгоритмов, потому что,

во-первых, наиболее часто используются, а во-вторых, потому что большинство

остальных алгоритмов является различными модификациями описанных здесь.

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

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

Идея этого метода отражена в его названии. Самые легкие элементы массива

"всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно

реализовать следующим образом. Мы будем просматривать весь массив "снизу

вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент

меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий”

элемент всего массива. Теперь повторим всю оперно для оставшихся

неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже"

первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он

является непревзойденным в своей неэффективности. Немного более

эффективным, но таким наглядным является второй метод.

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

На этот раз при просмотре мaccива мы будем искать наименьший элемент,

Сравнивая его с первым. Если такой элемент найден, поменяем его местами с

первым. Затем повторим эту операцию, но начнем не с первого элемента, а со

второго. И будем продолжать подобным образом, пока не рассортируем весь

массив.

Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея

этого алгоритма заключается в том, чтобы в начале ycтpанить массовый

беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как

видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается

до единицы. Это означает, что на поздних стадиях сортировка сводится просто

к перестановкам соседних элементов (если, конечно, такие перестановки

являются необходимыми).

Метод Хoopа

Этот метод, называемый также быстрой сортировкой(QuickSort), был

Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

Суть метода заключается в том, чтобы найти такой элемент множества,

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

элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею

можно реализовать многими способами.