Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 
У нас есть несколько работ на данную тему. Вы можете создать свою уникальную работу объединив фрагменты из уже существующих:
  1. Алгоритмы сортировки 2.9 Кб.
  2. Быстрые алгоритмы сортировки 31.4 Кб.

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

Работа из раздела: «Программирование и комп-ры»


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

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

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

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

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

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


ref.by 2006—2022
contextus@mail.ru