Все об алгоритмах сортировки
Мотивация
Алгоритмы сортировки — одна из самых важных тем на собеседованиях по кодированию. В этой статье представлен краткий обзор популярных алгоритмов.
Самый быстрый алгоритм сортировки на основе сравнения всегда будет принимать O(nlogn)
Если мы посмотрим на верхнюю границу наихудшего случая для всех алгоритмов сортировки, Сортировка по основанию и Сортировка подсчетом выглядят оптимальными с O(nk) и >O(n+k). Однако Сортировка по основанию и Сортировка подсчетом не считаются алгоритмом сортировки на основе сравнения (сравнивает два числа A[i] и A[j], чтобы получить порядок сортировки на выходе). Среди этих алгоритмов, основанных на сравнении, сортировка слиянием, сортировка кучей и сортировка по Тиму являются оптимальными, поскольку эти алгоритмы соответствуют нижней границе сортировки.
Нижняя граница для любого алгоритма сортировки на основе сравнения составляет O(nlogn).
Очевидно, что независимо от того, какой это алгоритм, если алгоритм использует метод сравнения (A[i] › A[j] или A[i] ≤A[j]) для определения порядка A[i] и A[j ] во время сортировки этот оптимальный алгоритм всегда будет иметь временную сложность O(nlogn).
В основном это происходит по 4 причинам:
- Мы можем рассматривать алгоритмы сортировки на основе сравнения как дерево решений. Каждый узел отвечает да/нет на вопрос: A[i] ≤ A[j]?
2. Для заданного массива A[1..n] алгоритмы сортировки выдают одно из n! перестановка A[1..n].
3. Высота дерева, представляющая собой самый длинный путь от корня до любого из его листьев, представляет собой наибольшее количество сравнений, которые должны выполнять алгоритмы сортировки.
4. Мы знаем, что для любого бинарного дерева высоты h существует не более 2^h листьев.
=> n! ≤ 2^h => h ≥ log(n!) log(n!) = log(1) + log(2) + ...+ log(n/2) + ... + log(n) ≥ log(n/2) + ... + log(n) ≥ log(n/2) + ... + log(n/2) ≥ n/2log(n/2) = n/2log(n) - n/2 => h = Ω(nlogn)
Пузырьковая сортировка
Основная идея состоит в том, чтобы сравнить соседние элементы и поменять их местами, если они расположены в неправильном порядке.
BubbleSort(array){
for i -> 0 to arrayLength
for j -> 0 to (arrayLength - i - 1)
if arr[j] > arr[j + 1]
swap(arr[j], arr[j + 1])
}
Существует вложенный цикл, поэтому пузырьковая сортировка занимает O(n) в временной сложности. Сложность пространства составляет O(1), так как мы не создаем дополнительное пространство.
Сортировка выбором
Основная идея состоит в том, чтобы многократно выбирать следующий наименьший элемент и перемещать его вперед.
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64
Пример Источник: Википедия
Опять же, мы видим вложенный цикл и замену на месте в сортировке выбором. Таким образом, временная сложность составляет O(n²), а пространственная сложность составляет O(1).
Сортировка вставками
Основная идея сортировки вставками заключается в сортировке по одному элементу за раз. Это похоже на то, как вы играете в карты. Вы просто пытаетесь найти позицию, чтобы вставить карту.
Для сортировки вставками по-прежнему требуется вложенный цикл, поэтому временная сложность составляет O(n²), а пространственная сложность составляет O(1). > так как мы не создаем дополнительное пространство для хранения вывода.
Сортировка слиянием
Сортировка слиянием — это алгоритм разделяй и властвуй. Сначала алгоритм делит массив пополам на каждом шаге, пока не достигнет базового случая одного элемента. Затем алгоритм объединяет и сравнивает элементы на каждом этапе, чтобы разместить их в отсортированном порядке.
MergeSort(arr[], l, r) If r > l middle m = l + (r – l)/2 //Find middle to split array mergeSort(arr, l, m) //Recursively sort left half mergeSort(arr, m + 1, r) //Recursively sort right half merge(arr, l, m, r) //Merge two halves for the final sorted output
Поскольку мы продолжаем разделять ввод n на 2 равные половины на каждом шаге, сортировка слиянием может быть выражена в виде следующего рекуррентного соотношения
T(n) = 2T(n/2) + θ(n)
Решением рекуррентного соотношения является O(nlogn), что соответствует времени сложности сортировки слиянием. При сортировке слиянием все элементы копируются во вспомогательный массив, поэтому пространственная сложность для сортировки слиянием составляет O(n).
Быстрая сортировка
Подобно сортировке слиянием, быстрая сортировка представляет собой алгоритм разделяй и властвуй. Однако вместо разделения массива на две равные части, как при сортировке слиянием, быстрая сортировка выбирает последний элемент в качестве опорного и разделяет массив вокруг этого поворотного элемента.
В среднем случае время сложность для быстрой сортировки составляет O(nlogn). В лучшем случае быстрая сортировка выберет средний элемент в качестве опорного, что приведет к следующему повторению:
T(n) = 2T(n/2) + O(n)
Рекуррентное отношение похоже на сортировку слиянием, поэтому временная сложность составляет O(nlogn).
Однако в наихудшем случае быстрая сортировка всегда будет выбирать самый маленький/самый большой элемент в качестве опорного, что приводит в следующем повторении:
T(n) = T(n-1) + O(n)
Это повторение имеет решение O (n²). Таким образом, в наихудшем случае быстрая сортировка занимает O(n²) в временной сложности.
Сортировка кучей
Сортировка кучей — это метод сортировки, основанный на структуре данных двоичной кучи. Двоичная куча поддерживает порядок с помощью операции «heapify».
Example of a Max Heap:
30(0)
/ \
70(1) 50(2)
Child (70(1)) is greater than the parent (30(0))
Swap Child (70(1)) with the parent (30(0))
70(0)
/ \
30(1) 50(2)
Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. Largest item is at the root. Replace it with the last item of the heap. Reduce heap size by 1
3. Heapify the root of the tree.
4. Repeat step 2 while heap size > 1
Illustration:
Input data: {4, 10, 3, 5, 1}
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
The numbers in bracket represent the indices in the array representation of data.
Applying heapify procedure to index 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Applying heapify procedure to index 0:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
The heapify procedure calls itself recursively to build heap in top down manner.
Время heapify равно O(logn), а время создания кучи равно O(n), поэтому общая временная сложность составляет O(nlogn).
Сортировка подсчетом
Сортировка подсчетом сортирует элементы массива, подсчитывая количество вхождений каждого уникального элемента в массиве. Счетчик хранится во вспомогательном массиве, а сортировка выполняется путем отображения счетчика как индекса вспомогательного массива. Сортировка подсчетом — это несравнительный алгоритм сортировки.
function CountingSort(input, k)
count ← array of k + 1 zeros
output ← array of same length as input
for i = 0 to length(input) - 1 do
j = key(input[i])
count[j] += 1
for i = 1 to k do
count[i] += count[i - 1]
for i = length(input) - 1 down to 0 do
j = key(input[i])
count[j] -= 1
output[count[j]] = input[i]
return output
Источник: Википедия
Есть два последовательных цикла: один от 0 до n-1 и другой от 1 до k. Следовательно, временная сложность O(n+k). Алгоритм использует массивы длины k+1 и n, поэтому пространственная сложность составляет O(n+k).
Сортировка по основанию
Поразрядная сортировка — это несравнительный алгоритм сортировки. Он позволяет избежать сравнения, создавая и распределяя элементы по корзинам в соответствии с их основанием.
radixSort(array)
d <- maximum number of digits in the largest element
create d buckets of size 0-9
for i <- 0 to d
sort the elements according to ith place digits using countingSort
countingSort(array, d)
max <- find largest element among dth place elements
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique digit in dth place of elements and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1Тим Сорт
Сортировка по Тиму — это гибридный алгоритм стабильной сортировки, созданный на основе сортировки слиянием и сортировки вставками и предназначенный для эффективной работы со многими типами реальных данных. Известно, что Tim Sort используется в функциях Java.sort() и Python sort().
Основная идея заключается в том, что массив разделен на блоки, известные как Run. Мы сортируем эти прогоны, используя сортировку вставками, один за другим, а затем объединяем эти прогоны, используя функцию объединения, используемую при сортировке слиянием.
Заключение
Сортировка — неотъемлемая часть программирования. Один из ключевых выводов заключается в том, что любой алгоритм, основанный на сравнении, имеет нижнюю границу временной сложности O(nlogn). Обратите внимание, что сортировка по счету и сортировка по основанию не сравнивают элементы для получения окончательного результата.
Я надеюсь, что вы найдете эту статью полезной и теперь будете чувствовать себя уверенно в алгоритмах сортировки :)
