14 KiB
В данной статье я рассмотрю алгоритмы сортировки, которые способны быть быстрее O(n x log), или другими словами быстрее всем известного quicksort.
Сортировка подсчётом (Сounting sort)
Этот метод подходит для случаев, когда у вас большое количество целых чисел в каком-то числовом диапазоне.
Сложность сортировки по времени:
- Худшая O(n + k)
- Средняя O(n + k)
- Лучшая O(n)
def counting_sort(alist, largest):
c = [0]*(largest + 1)
for i in range(len(alist)):
c[alist[i]] = c[alist[i]] + 1
c[0] = c[0] - 1
for i in range(1, largest + 1):
c[i] = c[i] + c[i - 1]
result = [None]*len(alist)
for x in reversed(alist):
result[c[x]] = x
c[x] = c[x] - 1
return result
Основной смысл алгоритма заключается в подсчёте количества различных чисел встречающихся в неотсортированном массиве и последующее выставление их в том количестве, в котором они встречаются в исходном массиве.
Блочная/Карманная сортировка (bucket sort)
Этот алгоритм эффективен при малом количестве или при сильно отличных данных.
Сложность сортировки по времени:
- Худшая O(n2)
- Средняя O(n)
- Лучшая O(n+k)
def bucket_sort(input_list, largest):
size = largest/len(input_list)
buckets_list= []
for x in range(len(input_list)):
buckets_list.append([])
for i in range(len(input_list)):
j = int (input_list[i] / size)
if j != len (input_list):
buckets_list[j].append(input_list[i])
else:
buckets_list[len(input_list) - 1].append(input_list[i])
for z in range(len(input_list)):
# insertion sort
for i in range (1, len(buckets_list[z])):
var = buckets_list[z][i]
j = i - 1
while (j >= 0 and var < buckets_list[z][j]):
buckets_list[z][j + 1] = buckets_list[z][j]
j = j - 1
buckets_list[z][j + 1] = var
final_output = []
for x in range(len (input_list)):
final_output = final_output + buckets_list[x]
return final_output
Данный алгоритм основан на предположении о равномерном распределении входных данных. Так же существует рекурсивный вариант.
Timsort
Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Сложность сортировки по времени:
-
Худшая O(nlogn)
-
Средняя O(n)
-
Лучшая O(n)
-
По специальному алгоритму разделяем входной массив на подмассивы
-
Сортируем каждый подмассив обычной сортировкой вставками
-
Собираем тсортированные подмассивы в единый массив с помощью модифицированной сортировки слиянием.
MINIMUM = 32
def find_minrun(n):
r = 0
while n >= MINIMUM:
r |= n & 1
n >>= 1
return n + r
def insertion_sort(array, left, right):
for i in range(left+1,right+1):
element = array[i]
j = i-1
while element<array[j] and j>=left :
array[j+1] = array[j]
j -= 1
array[j+1] = element
return array
def merge(array, l, m, r):
array_length1 = m - l + 1
array_length2 = r - m
left = []
right = []
for i in range(0, array_length1):
left.append(array[l + i])
for i in range(0, array_length2):
right.append(array[m + 1 + i])
i = 0
j = 0
k = l
while j < array_length2 and i < array_length1:
if left[i] <= right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
k += 1
while i < array_length1:
array[k] = left[i]
k += 1
i += 1
while j < array_length2:
array[k] = right[j]
k += 1
j += 1
def tim_sort(array):
n = len(array)
minrun = find_minrun(n)
for start in range(0, n, minrun):
end = min(start + minrun - 1, n - 1)
insertion_sort(array, start, end)
size = minrun
while size < n:
for left in range(0, n, 2 * size):
mid = min(n - 1, left + size - 1)
right = min((left + 2 * size - 1), (n - 1))
merge(array, left, mid, right)
size = 2 * size
По сути алгоритм представляет собой комбинацию нескольких других алгоритмов, в том числе блочную сортировку и сортировку слиянием. Python description of timsort
Сортировка с помощью двоичного дерева
Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).
Сложность сортировки по времени:
- Худшая O(n2)
- Средняя O(nlogn)
- Лучшая O(nlogn)
Сортировка в целом несложная:
- На основании массива строим бинарное дерево поиска. Первый элемент массива кладём в корень, остальные элементы сравниваем сначала с корнем, затем, в зависимости от сравнения, движемся вниз по левым или правым веткам.
- Обходим построенное бинарное дерево поиска от минимума к максимуму.
Сортировка выворачиванием(Splay sort)
Данный алгоритм решает проблему предыдущего, с помощью операций, называемые Zig, ZigZig и ZigZag. Они позволяют вывернуть дерево поиска так, что новый узел, вставленный в дерево, становится корнем.
Сложность сортировки по времени:
- Худшая O(nlogn)
- Средняя O(nlogn)
- Лучшая O(nlogn)
Плавная сортировка(Smoothsort)
Это алгоритм является усорвешенствоной версией другого алгоритма - heapsort.
Сложность сортировки по времени:
- Худшая O(nlogn)
- Средняя O(nlogn)
- Лучшая O(nlogn)
алгоритм: Создаём из массива кучу леонардовых куч(леонардовая куча - несбалансированное бинарное дерево, которая построена на числах Леонардо), каждая из которых является сортирующим деревом.
- I.1. Перебираем элементы массива слева-направо.
-
- II.1. Проверяем, можно ли с помощью текущего элемента объединить две крайние слева кучи в уже имеющейся куче леонардовых куч:
-
-
- II.1.а. Если да, то объединяем две крайние слева кучи в одну, текущий элемент становится корнем этой кучи, делаем просейку для объединённой кучи.
-
-
-
- II.1.б. Если нет, то добавляем текущий элемент в качестве новой кучи (состоящей пока из одного узла) в имеющуюся кучу леонардовых куч.
-
- II. Извлекаем из куч текущие максимальные элементы, которые перемещаем в конец неотсортированной части массива:
-
- II.1. Ищем максимумы в леонардовых кучах. Так как на предыдущем этапе для куч постоянно делалась просейка, максимумы находятся в корнях этих куч.
-
- II.2. Найденный максимум (который является корнем одной из куч) меняем местами с последним элементом массива (который является корнем самой последней кучи).
-
- II.3. После этого обмена куча, в которой был найден максимум перестала быть сортирующим деревом. Поэтому делаем для неё просейку.
- -II.4. В последней куче удаляем корень (в которой находится текущий максимум), в результате чего эта куча распадается на две кучи поменьше.
-
- II.5. После перемещения максимального элемента в конец, отсортированная часть массива увеличилась, а неотсортированная часть уменьшилась.
- Повторяем пункты II.1-II.4 для оставшейся неотсортированной части массива.
Визуализация данной сортировки
def smoothsort(lst):
leo_nums = leonardo_numbers(len(lst))
heap = []
for i in range(len(lst)):
if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
heap.pop()
heap[-1] += 1
else:
if len(heap) >= 1 and heap[-1] == 1:
heap.append(0)
else:
heap.append(1)
restore_heap(lst, i, heap, leo_nums)
for i in reversed(range(len(lst))):
if heap[-1] < 2:
heap.pop()
else:
k = heap.pop()
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
heap.append(k_l)
restore_heap(lst, t_l, heap, leo_nums)
heap.append(k_r)
restore_heap(lst, t_r, heap, leo_nums)
# Генерация чисел Леонардо, не превышающих количество элементов массива
def leonardo_numbers(hi):
a, b = 1, 1
numbers = []
while a <= hi:
numbers.append(a)
a, b = b, a + b + 1
return numbers
def restore_heap(lst, i, heap, leo_nums):
current = len(heap) - 1
k = heap[current]
while current > 0:
j = i - leo_nums[k]
if (lst[j] > lst[i] and
(k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
lst[i], lst[j] = lst[j], lst[i]
i = j
current -= 1
k = heap[current]
else:
break
while k >= 2:
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
if lst[t_r] > lst[t_l]:
lst[i], lst[t_r] = lst[t_r], lst[i]
i, k = t_r, k_r
else:
lst[i], lst[t_l] = lst[t_l], lst[i]
i, k = t_l, k_l
else:
break
# При удалении корня куча делится на две меньшие кучи,
# соответствующие двум предыдущим числами Леонардо
def get_child_trees(i, k, leo_nums):
t_r, k_r = i - 1, k - 2
t_l, k_l = t_r - leo_nums[k_r], k - 1
return t_r, k_r, t_l, k_l
Bogosort
В заключение к статье хочу сказать, что здесь рассмотрены алгоритмы сортировки со стороны асимптотики, не затрагивая расход памяти и скорости выполнения в “боевых” условиях. Но я оставляю эту задачу на читателя. Спасибо за внимание.