Реферат: Алгоритмы сортировки Реферат: Алгоритмы сортировки
Реферат: Алгоритмы сортировки РЕФЕРАТЫ РЕКОМЕНДУЕМ  
 
Тема
 • Главная
 • Авиация
 • Астрономия
 • Безопасность жизнедеятельности
 • Биографии
 • Бухгалтерия и аудит
 • География
 • Геология
 • Животные
 • Иностранный язык
 • Искусство
 • История
 • Кулинария
 • Культурология
 • Лингвистика
 • Литература
 • Логистика
 • Математика
 • Машиностроение
 • Медицина
 • Менеджмент
 • Металлургия
 • Музыка
 • Педагогика
 • Политология
 • Право
 • Программирование
 • Психология
 • Реклама
 • Социология
 • Страноведение
 • Транспорт
 • Физика
 • Философия
 • Химия
 • Ценные бумаги
 • Экономика
 • Естествознание




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод Шелла

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

Метод Хoopа

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

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



      ©2010