Сортировка перестановкой c доклад

Обновлено: 02.07.2024

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

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

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

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

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

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

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

Нужна помощь в написании доклада?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

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

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

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

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

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

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

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

Нужна помощь в написании доклада?

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

Метод Шелла

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

Метод Хoopа

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

А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?

Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.

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

С этой сортировкой нужно быть предельно осторожным. Неосмотрительно угодив в трясину, рискуете сгинуть навсегда.

Принцип прост как плесень. Перетряхиваем массив до тех пор пока он внезапно не отсортируется. Процесс может счастливо завершиться сразу, а может длиться до тепловой смерти Вселенной. Это уж как повезёт.

Средняя сложность по времени: O(n x n!). Есть также и лучшая: Ω(n). Что интересно, худшая временная сложность этого алгоритма науке неизвестна.

Где BogoSort, там и BozoSort. Метод сортировки детского клоуна Бозо легко объяснить даже трёхлетнему ребёнку. Выбираем наугад два элемента, меняем местами, проверяем не привело ли это к успеху. Если нет, то повторяем те же действия – и так до до победного конца.

Может показаться, что BozoSort — это то же что и BogoSort, но это только на первый взгляд. Клоун Бозо сортирует со средней временной сложностью O(n x n!) и это же является и верхней границей по времени.

Также отмечу, что тем не менее BozoSort в среднем всё равно будет сортировать быстрее чем BogoSort. Просто потому, что после каждого обмена массив проверяется на упорядоченность. В BogoSort часты случаи, когда массив находится в упорядоченном состоянии, однако если в этот момент не произвести проверку, а перемешивать далее, то вожделенное состояние осортированности на время утрачивается.

Взглянем на задачу сортировки сквозь призму комбинаторики. Любой массив – обычное конечное множество из n элементов, для которого существует n! перестановок. Некоторые из них – массив в упорядоченном состоянии. Составив алгоритм для перебора всех перестановок, мы неизбежно найдём ту самую.

Худшая сложность по времени как и у клоуна Бозо – O(n х n!). А вот с лучшей дела обстоят получше – О(n).

Развесёлая троица специализировалась на фарсе и эксцентрике. Также ведёт себя и сортировка: подобно карикатурному персонажу она безумно мечется по массиву; как и положено в буффонаде – после нелепых приключений с главным героем всё хорошо. Массив отсортирован, happy end.

Берём отрезок массива (вначале это весь массив) и сравниваем элементы на концах отрезка. Если слева больше чем справа, то, естественно, меняем местами.
Затем, если в отрезке не менее трёх элементов, то тогда:
1) вызываем Stooge sort для первых 2/3 отрезка;
2) вызываем Stooge sort для последних 2/3 отрезка;
3) снова вызываем Stooge sort для первых 2/3 отрезка.

Сложность алгоритма подсчитана подкупающе точно: O(n log 3 / log 1.5 ). Это не какие-то там мутные O(n).

Сам Бабушкин непосредственно не является автором метода, однако именно глубокие идеи Алексея легли в основу алгоритма.

Алексей Бабушкин, программист из Барнаула, предприниматель, инноватор. Студент 4-го курса АлтГТУ.

По приглашению компании Microsoft принимал непосредственное участие в тестировании бета-версии Windows 8.

Алгоритм архивации таков: любой файл представляет собой HEX-последовательность символов, переводим этот HEX в DEC, получаем неебически-большое число, дописываем перед этим число 0, — получаем число в диапазоне от 0 до 1 с огромным числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Беда в подборе чисел, которое может идти и 2 часа, а может идти и 2 недели. Есть опытные образцы и работающая программа, и всё это работает.

Пусть дан массив из n элементов. Последовательность перемещений элементов на свои места представима в виде ряда n-ричных одноразрядных чисел. Эту последовательность также можно считать многоразрядным n-ричным числом (назовём его числом Бабушкина). Каждый разряд этого числа – индекс позиции массива, в которую нужно вставить очередной элемент. Как получить такое число? Если число Бабушкина представить в 10-чном виде, получим большое (или не очень, зависит от размера массива) число, дописываем перед этим число 0, — получаем дробное число в диапазоне от 0 до 1, с некоторым числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Найдём 2 числа частное которых даёт число Бабушкина – автоматически получаем последовательность перестановок, упорядочивающую массив.

Кому-то что-то не ясно? Сортировка Бабушкина пошагово:

1) Допустим, нужно отсортировать массив из n элементов (индексация начинается с 0, индекс последнего элемента n — 1).
2) Специально подбираем два взаимно простых десятичных числа, x и y (x

Подробное объяснение десяти алгоритмов сортировки и реализации на C ++

Десять лучших алгоритмов сортировки можно разделить на две категории:

Сравнительная сортировка: определение относительного порядка элементов путем сравнения друг с другом. Поскольку временная сложность не может превышать O (nlogn), ее также называют нелинейной временной сортировкой;
Несравнительная сортировка: относительный порядок элементов не определяется сравнением. Он может преодолевать нижнюю границу времени на основе сравнительной сортировки и выполняться за линейное время, поэтому ее также называют несравнительной сортировкой линейного времени.

Связанные понятия

стабильный: Если a изначально стоит перед b, а a = b, то после сортировки по-прежнему перед b.
Нестабильный: Если a изначально находилось перед b, а a = b, то после сортировки может появиться после b.
временная сложность: Общее количество операций с отсортированными данными. Задумайтесь, какой закон показывает количество операций при изменении n.
Космическая сложность:Он относится к измерению объема памяти, необходимого при выполнении алгоритма на компьютере, а также является функцией размера данных n. Чтобы

1. Пузырьковая сортировка

1.1 Описание алгоритма

Сравните соседние элементы. Если первый больше второго, поменяйте их местами;
Проделайте ту же работу для каждой пары смежных элементов, от первой пары в начале до последней пары в конце, так чтобы последний элемент был наибольшим числом;
Повторите вышеуказанные шаги для всех элементов, кроме последнего;
Повторяйте шаги 1 ~ 3, пока сортировка не будет завершена.

1.2 Демонстрация анимации

1.3 Реализация кода

2. Выберите "Сортировать".

Выбор-сортировка (Selection-sort) - простой и понятный алгоритм сортировки. Его принцип работы: сначала найдите самый маленький (большой) элемент в несортированной последовательности, сохраните его в начале отсортированной последовательности, а затем продолжите поиск самого маленького (большого) элемента из оставшихся несортированных элементов, а затем поместите его в отсортированную последовательность В конце. И так до тех пор, пока все элементы не будут отсортированы. Чтобы

2.1 Описание алгоритма

Прямой выбор и сортировка n записей могут быть напрямую выбраны и отсортированы n-1 раз для получения упорядоченного результата. Конкретный алгоритм описывается следующим образом:

Исходное состояние: неупорядоченная область R [1..n], а упорядоченная область пуста;
Когда начинается i-я сортировка (i = 1,2,3 . n-1), текущая упорядоченная область и неупорядоченная область равны R [1..i-1] и R (i..n) соответственно. Эта сортировочная поездка состоит в том, чтобы выбрать запись R [k] с наименьшим ключом из текущей неупорядоченной области и обменять ее с первой записью R неупорядоченной области, чтобы получить R [1..i] и R [i + 1 ..n) Стать новой упорядоченной областью с увеличением количества записей на одну и новой неупорядоченной областью с уменьшением количества записей на одну;
В конце n-1 прохода массив упорядочивается.

2.2 Демонстрация движущегося изображения

2.3 Реализация кода

2.4 Анализ алгоритма

Один из самых стабильных алгоритмов сортировки, потому что независимо от того, какие данные вводятся, его временная сложность составляет O (n2), поэтому при его использовании чем меньше размер данных, тем лучше. Единственное преимущество может заключаться в том, что он не занимает дополнительного места в памяти. Теоретически выборочная сортировка также может быть методом сортировки, о котором думает большинство людей.

3. Сортировка по холму

Шелл изобрел в 1959 году первый алгоритм сортировки для разрыва O (n2), который представляет собой улучшенную версию простой сортировки вставкой. Разница между этим методом и сортировкой вставкой в том, что он сначала сравнивает более удаленные элементы. Сорт Хилла еще называютУменьшить инкрементную сортировку。

3.1 Описание алгоритма

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

Выберите инкрементную последовательность t1, t2, . tk, где ti> tj, tk = 1;
Сортировать последовательность k раз по количеству k последовательностей приращения;
В каждом проходе сортировки в соответствии с соответствующим приращением ti сортируемая последовательность делится на несколько подпоследовательностей длиной m, и каждая подтаблица непосредственно вставляется и сортируется. Только когда коэффициент приращения равен 1, вся последовательность рассматривается как таблица, а длина таблицы - это длина всей последовательности.

3.2 Демонстрация кинофильмов

3.3 Реализация кода

3.4 Анализ алгоритмов

4. Сортировка кучи

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

4.1 Описание алгоритма

Постройте начальную последовательность ключевых слов, которые нужно отсортировать (R1, R2 . Rn) в большую верхнюю стопку, которая является начальной неупорядоченной областью;
Замените верхний элемент R [1] последним элементом R [n] и получите новую неупорядоченную область (R1, R2, . Rn-1) и новую упорядоченную область (Rn) и выполните R [1,2 . n-1]

5. Сортировка вставкой

Описание алгоритма Insertion-Sort - это простой и интуитивно понятный алгоритм сортировки. Его принцип работы заключается в построении упорядоченной последовательности.Для несортированных данных просканируйте отсортированную последовательность от начала до конца, найдите соответствующую позицию и вставьте.

5.1 Описание алгоритма

Вообще говоря, сортировка вставкой реализуется в массивах с использованием на месте. Конкретный алгоритм описывается следующим образом:

Начиная с первого элемента, элемент можно считать отсортированным;
Выньте следующий элемент и просматривайте отсортированную последовательность элементов от начала до конца;
Если элемент (отсортированный) больше, чем новый элемент, переместите элемент в следующую позицию;
Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу;
После вставки нового элемента в эту позицию;
Повторите шаги 2 ~ 5.

5.2 Демонстрация кинофильмов

5.3 Реализация кода

5.4 Анализ алгоритмов

Сортировка вставкой обычно реализуется с помощью сортировки по месту (то есть сортировки, для которой требуется только O (1) дополнительного места) .Поэтому в процессе сканирования назад вперед необходимо многократно сдвигать отсортированные элементы назад. , Чтобы предоставить место для вставки последних элементов.

6. Сортировка слиянием

Сортировка слиянием - это эффективный алгоритм сортировки, основанный на операциях слияния. Этот алгоритм является очень типичным приложением Divide and Conquer. Объедините существующие упорядоченные подпоследовательности, чтобы получить полностью упорядоченную последовательность; то есть сначала сделайте каждую подпоследовательность по порядку, а затем сделайте подпоследовательности по порядку. Если два упорядоченных списка объединяются в один упорядоченный список, это называется двухсторонним объединением. Чтобы

6.1 Описание алгоритма

Разделите входную последовательность длины n на две подпоследовательности длины n / 2;
Объедините и отсортируйте эти две подпоследовательности соответственно;
Две отсортированные подпоследовательности объединяются в окончательную отсортированную последовательность.

6.2 Демонстрация кинофильмов

6.3 Реализация кода

6.4 Анализ алгоритмов

Сортировка слиянием - это стабильный метод сортировки. Как и сортировка по выбору, производительность сортировки слиянием не зависит от входных данных, но она работает намного лучше, чем сортировка по выбору, поскольку она всегда имеет временную сложность O (nlogn). Цена - потребность в дополнительном пространстве памяти.

7. Сортировка по мощности

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

7.1 Описание алгоритма

Получите наибольшее число в массиве и получите количество цифр;
arr - исходный массив, и каждый бит берется из младшего бита для формирования массива счисления;
Подсчет и сортировка по основанию (с использованием характеристик подсчета и сортировки для чисел с малым диапазоном);

7.2 Демонстрация кинофильмов

7.3 Реализация кода

8. Посчитать сортировку

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

8.1 Описание алгоритма

Найдите самый большой и самый маленький элементы в массиве для сортировки;
Подсчитайте количество появлений каждого элемента со значением i в массиве и сохраните его в i-м элементе массива C;
Накопить все подсчеты (начиная с первого элемента в C, каждый элемент добавляется к предыдущему элементу);
Заполните целевой массив: поместите каждый элемент i в элемент C (i) нового массива и вычтите 1 из C (i) для каждого элемента.

8.2 Демонстрация кинофильмов

8.3 Реализация кода

8.4 Анализ алгоритма

Сортировка по счетчику - это стабильный алгоритм сортировки. Когда входные элементы представляют собой n целых чисел от 0 до k, временная сложность равна O (n + k), а пространственная сложность также составляет O (n + k), а его скорость сортировки выше, чем у любого алгоритма сортировки сравнения. Когда k не очень велико и последовательность относительно сконцентрирована, сортировка с подсчетом является очень эффективным алгоритмом сортировки.

9. Ковшовая сортировка

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

9.1 Описание алгоритма

Установите количественный массив как пустое ведро;
Просмотрите входные данные и поместите данные один за другим в соответствующую корзину;
Отсортируйте каждое ведро, которое не пусто;
Объедините отсортированные данные из сегментов, которые никогда не бывают пустыми. Чтобы

9.2 Демонстрация изображения

9.3 Реализация кода

9.4 Анализ алгоритма

Лучшим случаем для сортировки сегментов является линейное время O (n). Временная сложность сортировки сегментов зависит от временной сложности сортировки данных между каждым сегментом, поскольку временная сложность других частей равна O (n). Очевидно, что чем меньше сегменты разделены, тем меньше данных между каждым сегментом и тем меньше времени требуется на сортировку. Но соответствующее потребление места увеличится.

10. Быстрая сортировка

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

10.1 Описание алгоритма

10.2 Демонстрация фильма

10.3 Реализация кода

10.4 Анализ алгоритма

Сортировка по мощности основана на раздельной сортировке и раздельном сборе, поэтому она стабильна. Однако производительность поразрядной сортировки немного хуже, чем у сегментной сортировки.Каждое сегментное назначение ключа требует временной сложности O (n), а получение новой ключевой последовательности после назначения требует O (n) временной сложности. Если сортируемые данные можно разделить на d ключевых слов, временная сложность поразрядной сортировки будет O (d * 2n). Конечно, d намного меньше n, поэтому в основном это линейно. Сложность поразрядной сортировки по пространству составляет O (n + k), где k - количество сегментов. Вообще говоря, n >> k, поэтому дополнительного места нужно около n.

Изучение алгоритмов и разновидности методов сортировки в программировании. Характеристика ее видов: сортировка пузырьком, перемешиванием, методом вставок, подсчётом, слиянием, цифровая, поразрядная, методом выбора, методом Шелла, пирамидальная и быстрая.

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	20.11.2014
Размер файла	32,1 K

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

Федеральное агентство железнодорожного транспорта

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

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

2. Разновидности методов сортировки

2.1 Сортировка пузырьком

2.2 Сортировка перемешиванием

2.3 Сортировка методом вставок

2.4 Сортировка подсчётом

2.5 Сортировка слиянием

2.6 Цифровая сортировка

2.7 Поразрядная сортировка

2.8 Сортировка методом выбора

2.9 Сортировка методом Шелла

2.10 Пирамидальная сортировка

2.11 Быстрая сортировка

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

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

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

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

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

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

Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти. Согласно этим требованиям, простые алгоритмы сортировки (такие, как сортировка выбором и сортировки включением) не являются очень эффективными.

Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно не изменяются) и не использует вспомогательной памяти, но занимает много времени. Даже, если внутренний цикл не содержит ни одной перестановки, то действия будут повторяться до тех пор, пока не завершится внешний цикл.

Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.

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

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

Оценка алгоритма сортировки. Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.

Время сортировки -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение -- это O(n log n) и плохое поведение -- это Щ(nІ). Идеальное поведение для сортировки -- O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Щ(n log n) сравнениях в среднем;

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

Устойчивость (stability) -- устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

Естественность поведения -- эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объём данных не позволяет им разместиться в ОЗУ

Список алгоритмов сортировки

В этой таблице n -- это количество записей, которые необходимо отсортировать, а k -- это количество уникальных ключей.

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

Сортировка пузырьком (англ. Bubble sort ) -- сложность алгоритма: Q(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку

Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) -- Сложность алгоритма: O(n2)

Сортировка методом вставок (Insertion sort) -- Сложность алгоритма: O(n2); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда

Блочная сортировка (Корзинная сортировка, Bucket sort) -- Сложность алгоритма: O(n); требуется O(k) дополнительной памяти

Сортировка подсчетом (Counting sort) -- Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти

Сортировка слиянием (Merge sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем -- сливаем отсортированные списки

In-place merge sort -- Сложность алгоритма: O(n2)

Двоичное древо сортировки (Binary tree sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти

Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) -- Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти

Поразрядная сортировка (Radix sort) -- Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти сортирует строки буква за буквой

Гномья сортировка (Gnome sort) -- Сложность алгоритма: O(n2)

Алгоритмы неустойчивой сортировки

Сортировка методом выбора (Selection sort) -- Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка

Сортировка методом Шелла (Shell sort) -- Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками

Сортировка расчёской (Comb sort) -- Сложность алгоритма: O(n log n)

Пирамидальная сортировка (Сортировка кучи, Heapsort) -- Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка

Плавная сортировка (Smoothsort) -- Сложность алгоритма: O(n log n)

Быстрая сортировка (Quicksort) -- Сложность алгоритма: O(n log n) -- среднее время, O(n2) -- худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине

Introsort -- Сложность алгоритма: O(n log n)

Patience sorting -- Сложность алгоритма: O(n log n + k) -- наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность

Непрактичные алгоритмы сортировки

Сортировка Акульшина (Akulshin sort) -- O(n Ч n!) -- худшее время. Генерируем всевозможные перестановки исходного массива и для каждой осуществдяем проверку верной отсортированности.

Глупая сортировка (Stupid sort) -- O(n3); рекурсивная версия требует дополнительно O(n2) памяти

Bead Sort -- O(n) or O(vn), требуется специализированное железо

Блинная сортировка (Pancake sorting) -- O(n), требуется специализированное железо

2. Разновидности методов сортировки

2.1 Сортировка пузырьком

Сортировка методом пузырька имеет сложность O(n2). Для понимания и реализации это -- простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.

Пример реализации алгоритма (язык Pascal):

for i := n - 1 downto 1 do

for j := 1 to i do

if a[j] > a[j+1] then

2.2 Сортировка перемешиванием

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

Лучший случай для этой сортировки -- отсортированный массив (О(n)), худший -- отсортированный в обратном порядке (O(nІ)).

2.3 Сортировка методом вставок

Сортировка методом вставок (англ. insertion sort) -- простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации

эффективен на небольших наборах данных

эффективен на наборах данных, которые уже частично отсортированы

это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

может сортировать список по мере его получения

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

2.4 Сортировка подсчётом

Сортировка подсчётом -- алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

2.5 Сортировка слиянием

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Двоичное дерево (структура данных)

Двоичное дерево -- абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data -- некоторые данные привязанные к узлу, l, r -- ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r -- правым.

2.6 Цифровая сортировка

Алгоритм цифровой сортировки действует следующим образом:

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

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

Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.

Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).

2.7 Поразрядная сортировка

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

2.8 Сортировка методом выбора

Сортировка методом выбора (англ. selection sort) -- алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае И(n2), предполагая, что сравнения делаются за постоянное время.

находим минимальное значение в текущем списке

производим обмен этого значения со значением на первой позиции

теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент

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

Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.

2.9 Сортировка методом Шелла

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

Анализ алгоритма сортировки Шелла

Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости n2, которой подчиняется большинство простых алгоритмов сортировки.

Читайте также: