В данной статье я рассмотрю алгоритмы сортировки, которые способны быть быстрее 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

bogsort

 

В заключение к статье хочу сказать, что здесь рассмотрены алгоритмы сортировки со стороны асимптотики, не затрагивая расход памяти и скорости выполнения в “боевых” условиях. Но я оставляю эту задачу на читателя. Спасибо за внимание.

Note: статья была написана 21 января 2023 года: https://telegra.ph/Algoritmy-sortirovki-bystree-ON-x-log-N-01-21