ronl

Реферат: Алгоритмы сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

  Идея этого методаотражена в его названии. Самые легкие элементы массива «всплывают»наверх, самые «тяжелые» — тонут. Алгоритмически это можно реализоватьследующим образом. Мы будем просматривать весь массив «снизу вверх» именять стоящие рядом элементы в там случае, если «нижний» элементменьше, чем «верхний». Таким образом, мы вытолкнем наверх самый«легкий” элемент всего массива. Теперь повторим всю опернодля оставшихся неотсортироваными N-1 элементов (т.е.для тех, которые лежат „ниже“ первого. Как видно, алгоритм достаточнопрост, но, как иногда замечают, он является непревзойденным в своейнеэффективности. Немного более эффективным, но таким наглядным является второйметод.

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

  На этот раз припросмотре мaccива мы будем искать наименьший элемент,Сравнивая его с первым. Если такой элемент найден, поменяем его местами спервым. Затем повторим эту операцию, но начнем не с первого элемента, а совторого. И будем продолжать подобным образом, пока не рассортируем весь массив.

Метод Шелла

Этот метод был предложен автором DonaldLewis Shеll в 1959 г.Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далекостоящие друг от друга элементы. Как видно, интервал между сравниваемымиэлементами (gap) постепенно уменьшается до единицы.Это означает, что на поздних стадиях сортировка сводится просто к перестановкамсоседних элементов (если, конечно, такие перестановки являются необходимыми).

Метод Хoopа

  Этот метод,называемый также быстрой сортировкой(QuickSort), былРазработан в 1962 г. (его разработал Charles Antony Richard Hoare).

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

еще рефераты
Еще работы по программированию, базе данных