Способы сортировки массива по возрастанию

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

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

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

Сортировка пузырьком / 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:

Источник

Читайте также:  Способ блокировки экрана нет