Рефетека.ру / Математика

Доклад: Алгоритмы сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод Шелла

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

Метод Хoopа

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

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта  http://www.ed.vseved.ru/


Похожие работы:

  1. • Алгоритмы сортировки, поиска длиннейшего пути во ...
  2. • Сортировка данных в массиве
  3. • Алгоритмы сортировки, поиска кратчайшего пути в ...
  4. • Элементарные методы сортировки
  5. • Анализ методов сортировки одномерного массива
  6. •  ... эффективности методов сортировки Флойда и Шелла
  7. • Быстрые алгоритмы сортировки
  8. • Методы сортировки. Их сравнительный анализ
  9. • VB, MS Access, VC++, Delphi, Builder C++ принципы(технология ...
  10. • Методы внутренней сортировки. Обменная сортировка ...
  11. • Основы дискретной математики
  12. • Моделирование информацийных потоков
  13. • Информационная система начальника жилищно ...
  14. • Программирование различных типов задач
  15. • Сортировка массивов методом вставок
  16. • Информатика. Текстовый редактор
  17. • Алгоритмы обработки больших массивов. Алгоритмы ...
  18. • Анализ алгоритмов нечисленной обработки данных
  19. •  ... поиск, удаление, сортировка, все, что надо написанная на С+ ...
Рефетека ру refoteka@gmail.com