Загрузка...
Учебная работа. Доклад: Алгоритмы сортировки
Сортировка применяется во всех без исключения областях программирования, будь то базы данных либо математические программки.
Фактически любой метод сортировки можно разбить на три части:
— сопоставление, определяющее упорядоченность пары частей;
— перестановку, меняющую местами пару частей;
— фактически сортирующий метод, который производит сопоставление и перестановку частей до того времени, сока все элементы огромного количества не будут упорядочены.
Схожими качествами владеют и те 5 алгоритмов сортировки, которые
рассмотрены ниже. Они отобраны из огромного количества алгоритмов, поэтому что,
во-1-х, более нередко употребляются, а во-2-х, поэтому что большая часть других алгоритмов является разными модификациями обрисованных тут.
Способ пузырька.
( способ назван также обменной сортировкой с выбором) .
Мысль этого способа отражена в его заглавии. Самые легкие элементы массива «всплывают» наверх, самые «томные» — утопают. Алгоритмически это можно воплотить последующим образом. Мы будем просматривать весь массив «снизу ввысь» и поменять стоящие элементы в там случае, если «нижний» элемент меньше, чем «верхний». Таковым образом, мы вытолкнем наверх самый «легкий” элемент всего массива. сейчас повторим всю оперно для оставшихся неотсортироваными N-1 частей (т.е. для тех, которые лежат «ниже» первого. Как видно, метод довольно прост, но, как время от времени замечают, он является непревзойденным в собственной неэффективности. Мало наиболее действенным, но таковым приятным является 2-ой способ.
Сортировка выбором
сейчас во время просмотра мaccива мы будем находить меньший элемент, Сравнивая его с первым. Если таковой элемент найден, поменяем его местами с первым. Потом повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать схожим образом, пока не рассортируем весь массив.
способ Шелла
Этот способ был предложен создателем Donald Lewis Shеll в 1959 г. Основная мысль этого метода состоит в том, чтоб сначала ycтpанить массовый кавардак в массиве, сравнивая далековато стоящие друг от друга элементы. Как видно, интервал меж сравниваемыми элементами (gap) равномерно миниатюризируется до единицы. Это значит, что на поздних стадиях сортировка сводится просто к перестановкам примыкающих частей (если, естественно, такие перестановки являются необходимыми).
способ Хoopа
Этот способ, именуемый также резвой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).
Сущность способа состоит в том, чтоб отыскать таковой элемент огромного количества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно воплотить почти всеми методами.
]]>