mirror of
https://gist.github.com/28f941c9e7fba992808afa3c89140300.git
synced 2024-11-10 16:06:32 +03:00
284 lines
14 KiB
Markdown
284 lines
14 KiB
Markdown
В данной статье я рассмотрю алгоритмы сортировки, которые способны быть быстрее O(n x log), или другими словами быстрее всем известного quicksort.
|
||
|
||
### **[Сортировка подсчётом](https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D1%91%D1%82%D0%BE%D0%BC) (Сounting sort)**
|
||
|
||
Этот метод подходит для случаев, когда у вас большое количество целых чисел в каком-то числовом диапазоне.
|
||
|
||
Сложность сортировки по времени:
|
||
- Худшая O(n + k)
|
||
- Средняя O(n + k)
|
||
- Лучшая O(n)
|
||
|
||
```python
|
||
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
|
||
```
|
||
Основной смысл алгоритма заключается в подсчёте количества различных чисел встречающихся в неотсортированном массиве и последующее выставление их в том количестве, в котором они встречаются в исходном массиве.
|
||
|
||
### **[Блочная/Карманная сортировка](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B0%D1%80%D0%BC%D0%B0%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) (bucket sort)**
|
||
Этот алгоритм эффективен при малом количестве или при сильно отличных данных.
|
||
|
||
Сложность сортировки по времени:
|
||
|
||
- Худшая O(n2)
|
||
- Средняя O(n)
|
||
- Лучшая O(n+k)
|
||
|
||
```python
|
||
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](https://habr.com/ru/company/infopulse/blog/133303/)
|
||
Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
|
||
|
||
Сложность сортировки по времени:
|
||
|
||
- Худшая O(nlogn)
|
||
- Средняя O(n)
|
||
- Лучшая O(n)
|
||
|
||
- По специальному алгоритму разделяем входной массив на подмассивы
|
||
- Сортируем каждый подмассив обычной сортировкой вставками
|
||
- Собираем тсортированные подмассивы в единый массив с помощью модифицированной сортировки слиянием.
|
||
|
||
```python
|
||
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](https://svn.python.org/projects/python/trunk/Objects/listsort.txt)
|
||
|
||
### [Сортировка с помощью двоичного дерева](https://ru.m.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0)
|
||
Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).
|
||
|
||
Сложность сортировки по времени:
|
||
|
||
- Худшая O(n2)
|
||
- Средняя O(nlogn)
|
||
- Лучшая O(nlogn)
|
||
|
||
Сортировка в целом несложная:
|
||
|
||
- На основании массива строим бинарное дерево поиска. Первый элемент массива кладём в корень, остальные элементы сравниваем сначала с корнем, затем, в зависимости от сравнения, движемся вниз по левым или правым веткам.
|
||
- Обходим построенное бинарное дерево поиска от минимума к максимуму.
|
||
|
||
### [Сортировка выворачиванием](https://habr.com/ru/company/edison/blog/504012/)(Splay sort)
|
||
|
||
Данный алгоритм решает проблему предыдущего, с помощью операций, называемые Zig, ZigZig и ZigZag. Они позволяют вывернуть дерево поиска так, что новый узел, вставленный в дерево, становится корнем.
|
||
|
||
Сложность сортировки по времени:
|
||
|
||
- Худшая O(nlogn)
|
||
- Средняя O(nlogn)
|
||
- Лучшая O(nlogn)
|
||
|
||
### Плавная сортировка(Smoothsort)
|
||
Это алгоритм является усорвешенствоной версией другого алгоритма - heapsort.
|
||
|
||
Сложность сортировки по времени:
|
||
|
||
- Худшая O(nlogn)
|
||
- Средняя O(nlogn)
|
||
- Лучшая O(nlogn)
|
||
|
||
алгоритм:
|
||
Создаём из массива кучу леонардовых куч(леонардовая куча - несбалансированное бинарное дерево, которая построена на [числах Леонардо](https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE)), каждая из которых является сортирующим деревом.
|
||
|
||
- I.1. Перебираем элементы массива слева-направо.
|
||
- - II.1. Проверяем, можно ли с помощью текущего элемента объединить две крайние слева кучи в уже имеющейся куче леонардовых куч:
|
||
- - - II.1.а. Если да, то объединяем две крайние слева кучи в одну, текущий элемент становится корнем этой кучи, делаем просейку для объединённой кучи.
|
||
- - - II.1.б. Если нет, то добавляем текущий элемент в качестве новой кучи (состоящей пока из одного узла) в имеющуюся кучу леонардовых куч.
|
||
- II. Извлекаем из куч текущие максимальные элементы, которые перемещаем в конец неотсортированной части массива:
|
||
- - II.1. Ищем максимумы в леонардовых кучах. Так как на предыдущем этапе для куч постоянно делалась просейка, максимумы находятся в корнях этих куч.
|
||
- - II.2. Найденный максимум (который является корнем одной из куч) меняем местами с последним элементом массива (который является корнем самой последней кучи).
|
||
- - II.3. После этого обмена куча, в которой был найден максимум перестала быть сортирующим деревом. Поэтому делаем для неё просейку.
|
||
- -II.4. В последней куче удаляем корень (в которой находится текущий максимум), в результате чего эта куча распадается на две кучи поменьше.
|
||
- - II.5. После перемещения максимального элемента в конец, отсортированная часть массива увеличилась, а неотсортированная часть уменьшилась.
|
||
- Повторяем пункты II.1-II.4 для оставшейся неотсортированной части массива.
|
||
|
||
[Визуализация данной сортировки](https://youtu.be/Xu5ia5x2Vsw)
|
||
|
||
```python
|
||
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~~
|
||
|
||
В заключение к статье хочу сказать, что здесь рассмотрены алгоритмы сортировки со стороны асимптотики, не затрагивая расход памяти и скорости выполнения в “боевых” условиях. Но я оставляю эту задачу на читателя. Спасибо за внимание. |