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

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

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

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

Немного более эффективным, нотаким наглядным является второй метод.Сортировка выбором На этот раз припросмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым.Если такой элемент найден, поменяем его местами с первым. Затем повторим этуоперацию, но начнем не с первого элемента, а со второго.И будем продолжать подобнымобразом, пока не рассортируем весь массив.Метод ШеллаЭтот метод был предложен автором Donald Lewis Shеll в 1959г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанитьмассовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы.

Как видно, интервал между сравниваемыми элементами gap постепенно уменьшаетсядо единицы.Это означает, что на поздних стадиях сортировка сводится просто кперестановкам соседних элементов если, конечно, такие перестановки являютсянеобходимыми .Метод Хoopа Этот метод,называемый также быстрой сортировкой QuickSort , был Разработан в 1962 г. егоразработал Charles Antony Richard Hoare . Суть методазаключается в том, чтобы найти такой элемент множества, подлежащего сортировке,который разобьет его на два подмножества те элементы, что меньше делящегоэлемента, и те, что не меньше его. Эту идею можно реализовать многимиспособами.