Сортировка виды сортировки способы сортировки

Сортировки

Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.

Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.

Также есть алгоритмы параллельной сортировки данных (т.н. Сортирующие сети), время работы которых в лучшем случае $O(\log n)$.

Содержание

Классификация сортировок [ править ]

Время работы [ править ]

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.

Память [ править ]

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

Устойчивость [ править ]

Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.

Количество обменов [ править ]

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

Детерминированность [ править ]

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

Сравнение сортировок [ править ]

Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.

Источник

Основные виды сортировок и примеры их реализации

Памятка для тех, кто готовится к собеседованию на позицию разработчика

На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.

Пузырьковая сортировка и её улучшения

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

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

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

Сортировка перемешиванием (шейкерная сортировка)

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

Сортировка расчёской

Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

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

Простые сортировки

Сортировка вставками

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

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

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

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

Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.

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

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

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

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

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

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

Источник

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

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

Виды алгоритмов сортировки

Сортировка пузырьком / Bubble sort

Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.

Плюсы и минусы

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

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n)	O(n 2 )	O(n 2 )
Память			O(1)

Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort

Также известна как шейкерная или коктейльная сортировка.

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

Общая идея алгоритма:

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

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n)	O(n 2 )	O(n 2 )
Память			O(1)

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

Сортировка расчёской / Comb sort

Сортировка расчёской — еще одна разновидность сортировки пузырьком. Данная сортировка улучшает сортировку пузырьком за счет устранения маленьких значений в конце списка (черепах).

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

Оптимальное значение фактора уменьшения — 1,247.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n log n)	Ω(n 2 /2 p ), где p — количество инкрементов	O(n 2 )
Память			O(1)

Сортировка вставками / Insertion sort

Сортировка вставками — алгоритм, при котором каждый последующий элемент массива сравнивается с предыдущими элементами (отсортированными) и вставляется в нужную позицию.

Общая идея алгоритма:

• Сравниваем второй элемент с первым элементом массива и при необходимости меняем их местами. Условно эти элементы (первый и второй) будут являться отсортированным массивом, остальные элементы — неотсортированным.
• Сравниваем следующий элемент из неотсортированного массива с элементами отсортированного и вставляем в нужную позицию.
• Повторям шаг 2 до тех пор, пока в неотсортированном массиве не останется элементов.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n)	O(n 2 )	O(n 2 )
Память			O(1)

Сортировка Шелла / Shell sort

Сортировка Шелла — усовершенствованная разновидность сортировки вставками.

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

Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:

• первая итерация — d₁ = N/2, где N — размер массива;
• последующие итерации — d_i = d_i-1/2;
• последняя итерация — d_k = 1

Существуют и другие последовательности.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n log n)	зависит от выбранных шагов (d)	O(n 2 ) или O(n log 2 n) (зависит от выбранных шагов)
Память			O(1)

Сортировка выбором / Selection Sort

Сортировка выбором — это алгоритм, при котором многократно осуществляется поиск минимального элемента в неотсортированной части массива и его помещение в конец отсортированной части массива.

Общая идея алгоритма:

• Данный алгоритм условно делит массив на две части:
  • подмассив, который уже отсортирован (находится в левой части массива),
  • подмассив, который нужно отсортировать (находится в правой части массива).
• Поиск минимального значения в неотсортированном массиве. Найденное значение меняем местами с первым элементом в неотсортированном массиве.
• Повторяем предыдущий шаг до тех пор, пока массив не будет отсортирован.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n 2 )	O(n 2 )	O(n 2 )
Память			O(1)

Быстрая сортировка / Quick Sort

Быстрая сортировка — это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:

• Выбрать из массива элемент, который обычно называют опорным. Это может быть любой элемент из массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
• Рекурсивно применить первые два шага к отрезкам, содержащим «меньшие» и «большие» значения. Не применять к массиву, в котором только один элемент или отсутствуют элементы.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n)	O(n log n)	O(n 2 )
Память			O(n)

Сортировка слиянием / Merge sort

Сортировка слиянием — это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:

• Массив разбивается на две части примерно одинакового размера. Разбиение получившихся массивов повторяется до тех пор, пока размер каждого массива не достигнет единицы.
• Каждая из получившихся частей сортируется отдельно, после чего происходит слияние двух массивов следующим образом:
  • На каждом шаге сравниваем первые элементы массивов, берём наименьшее значение и записываем в результирующий массив.
  • Когда один из массив закончился, добавляем оставшиеся элементы второго массива в результирующий массив.
• Слияние подмассивов продолжается до тех пор, пока не получим один, отсортированный массив.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(n log n)	O(n log n)	O(n log n)
Память			O(n)

Пирамидальная сортировка / Heap sort

Пирамидальная сортировка — это улучшенная сортировка выбором.

Для сортировки используется бинарное сортирующее дерево — дерево, у которого выполнены условия:

• Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
• Значение в любой вершине не меньше значения её потомков.

Общая идея алгоритма:

Выстраиваем массив в виде сортирующего дерева:
Array[i] >= Array[2i + 1]
Array[i] >= Array[2i + 2]
при 0

Сложность	Лучшее	Среднее	Худшее
Время	O(n log n)	O(n log n)	O(n log n) или O(n) (при одинаковых ключах)
Память			O(1)

Сортировка подсчётом / Counting sort

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

Общая идея алгоритма (простой вариант):

• Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями.
• Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C — это значения массива A, а значение в массиве C — это то, сколько раз это число повторяется в массиве A.
• Проходим по массиву C и переносим значения в массив A.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	Ω(n+k)	θ(n+k)	O(n + k)
Память			O(k)

• n — размер отсортированного массива, а k — размер вспомогательного массива

Блочная (карманная, корзинная) сортировка / Bucket sort

Блочная сортировка — это алгоритм, основанный на разделении входного массива на несколько частей — блоки/сегменты — и использовании другого алгоритма для их сортировки.

Общая идея алгоритма:

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

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	Ω(n+k)	θ(n+k)	O(n 2 )
Память			O(1)

Поразрядная (цифровая) сортировка / Radix sort

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

Перед началом сортировки необходимо знать:

• length — максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове);
• rang количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).

Общая идея алгоритма:

• Создаём пустые массивы, количество которых равно rang.
• Распределяем исходные значения по этим массивам. Распределение осуществляется по значению младшего (крайнего) разряда.
• Соединяем значения в той последовательности, в которой они находятся после распределения по спискам.
• Повторяем шаги 1-2 для оставшихся разрядов.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	Ω(n+w)	θ(nk)	O(w * n)
Память			O(n + w)

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

Битонная сортировка / Bitonic sort

Битонная сортировка — алгоритм, основанный на понятии битонных последовательностей и операций над ними.

Битонная последовательность — последовательность, которая сначала возрастает, а потом убывает.

Общая идея алгоритма:

• Создаём битонную последовательность. В результате получаем два массива: первый отсортирован в порядке возрастания, второй — в порядке убывания.
• Последовательно сравниваем элементы первого и второго массивов (сначала первые элементы, потом вторые и т.д.). Если какой либо элемент из второго массива окажется меньше, то меняем его местами с элементом из первого массива. В результате в первом массиве окажутся наименьшие элементы из обоих массивов, а во втором — наибольшие. При этом каждый из массивов будет являться битонной последовательностью.
• Рекурсивно применяем второй шаг к отсортированным массивам, после чего массивы можно склеить.



Чтобы превратить произвольную последовательность в битонную, нужно:

• разделить последовательность пополам;
• первую часть отсортировать по возрастанию;
• вторую часть отсортировать по убыванию.

Пример реализации на Kotlin:

Сложность	Лучшее	Среднее	Худшее
Время	O(log 2 (n)	O(log 2 (n)	O(log 2 (n)
Память			O(log 2 (n)

Timsort

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

Общая идея алгоритма:

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

Пример реализации на Kotlin:

Источник

Читайте также:  Образовать от глагола существительное бессуффиксным способом