Если спросить любого, хоть немного знакомого с ИТ человека, какие алгоритмы сортировки он знает, то самым популярным ответом будет, конечно, сортировка методом пузырька. Однако в реальности это, конечно, не единственный способ сортировки. В этой статье мы поговорим о том, какие алгоритмы сортировки бывают и как их можно реализовать на Python.

Будем считать, что у нас имеется некоторый неупорядоченный набор числовых  значений, которые нам необходимо отсортировать по возрастанию.

Но начнем мы все-таки с пузырька, как с самого популярного алгоритма.

Собственно, сама идея, лежащая в основе алгоритма, очень проста. Имея неупорядоченный список, мы сравниваем соседние элементы в списке и после каждого сравнения размещаем их в правильном порядке величины. Это работает путем замены соседних элементов, если они не находятся в правильном порядке. Процесс повторяется n-1 раз для списка из n элементов. В каждой итерации наибольший элемент размещается в конце.

Самый известный алгоритм сортировки на практике является не слишком эффективным, так как он обеспечивает сложность выполнения в худшем O(n²) и в лучшем случае O(n).

Вот его реализация на Python:

def bubbleSort(arr):
 for i in range(len(arr)-1):
  for j in range(len(arr)-1-i):
   if arr[j]>arr[j+1]:
    arr[j],arr[j+1] = arr[j+1],arr[j] # swap arr[j] with arr[j+1] and vice versa

if name=="__main__":
 lst = [8,4,52,0,20,3,9]
 bubbleSort(lst)
 print(lst)

Сортировка вставкой

При использовании сортировки вставкой мы начинаем с одного элемента, предполагая, что он отсортирован, а затем берем другой элемент из несортированного блока и помещаем его в правильную позицию (по отношению к первому элементу) в отсортированном блоке. Это означает, что наш отсортированный блок теперь имеет два элемента. Затем мы снова берем другой элемент из несортированного блока и помещаем его в правильную позицию (по отношению к уже двум отсортированным элементам) в отсортированном блоке. Мы многократно следуем этому процессу, чтобы вставить все элементы по одному из несортированного блока в отсортированный.

Алгоритм сортировки вставкой также дает наихудшую сложность выполнения O(n²), а лучшую сложность O(n).

Реализация:

def insertionSort(arr):
    for i in range(1, len(arr)):
        value = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] > value:
            arr[pos] = arr[pos-1]
            pos -= 1
    arr[pos] = value
if name == "__main__":
    lst = [8, 4, 52, 0, 20, 3, 9]
    insertionSort(lst)
    print(lst)

#################################

def insertion_sort(arr):
    for i in range(len(arr)):
        pos = i
        while pos > 0 and arr[pos-1] > arr[pos]:
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            pos = pos-1

if name == "__main__":
    lst = [8, 4, 52, 0, 20, 3, 9]
    insertion_sort(lst)
    print(lst)

Сортировка выбором

Еще один из простых алгоритмов сортировки это алгоритм сортировки выбором. Он начинает работу с поиска наименьшего элемента в списке и обмена его с первым элементом в списке. Таким образом, он делает подсписок отсортированным до первого элемента. Затем определяется второй наименьший элемент, который является наименьшим элементом в оставшемся списке, и обменивается со второй позицией в списке. Это делает начальные два элемента отсортированными. Процесс повторяется, и наименьший элемент, оставшийся в списке, должен быть обменен с элементом в третьем индексе в списке. Это означает, что первые три элемента теперь отсортированы. Этот процесс повторяется (n-1) раз для сортировки n элементов.

Здесь сложность в любом случае будет O(n²), так как необходимо перебирать все варианты в любом случае.

Алгоритм:

  for i in range(len(arr)):
    pos = i
    for j in range(i+1,len(arr)):
      if arr[pos]>arr[j]:
        pos = j

    if pos != i:
      arr[i],arr[pos] = arr[pos],arr[i]

if name=="__main__":
   lst = [8,4,52,0,20,3,9]
   selectionSort(lst)
   print(lst)

Сортировка слиянием

Сортировка слиянием — это рекурсивный алгоритм, который непрерывно делит список пополам. Если список пуст или содержит один элемент, он сортируется по определению (базовый случай). Если список содержит более одного элемента, мы делим список и рекурсивно вызываем сортировку слиянием для обеих половин. После сортировки двух половин выполняется основная операция, называемая слиянием. Слияние — это процесс взятия двух меньших отсортированных списков и объединения их в один отсортированный новый список.

Здесь сложность также во всех случаях будет одинаковая O(n log n).

def mergeSort(arr):
    if len(arr)>1:
        mid = len(arr)//2
        lefthalf = arr[:mid]
        rightHalf = arr[mid:]
        mergeSort(lefthalf)
        mergeSort(rightHalf)
   
        i,j,k = 0,0,0
        while i<len(lefthalf) and j<len(rightHalf):
            if lefthalf[i]>rightHalf[j]:
                arr[k]=rightHalf[j]
                j +=1
            else:
               arr[k]=lefthalf[i]
                i +=1
            k += 1
          
        while len(lefthalf)>i:
            arr[k]=lefthalf[i]
            i +=1
            k +=1
   
        while len(rightHalf)>j:
            arr[k]=rightHalf[j]
            j +=1
            k +=1
    
if name=="__main__":
 lst = [-5,8,4,52,0,20,3,9,100]
 mergeSort(lst)
 print(lst)

Быстрая сортировка

Алгоритм быстрой сортировки относится к классу алгоритмов «разделяй и властвуй», подобно алгоритму сортировки слиянием, где мы разбиваем (делим) задачу на более мелкие части, которые гораздо проще решить (завоевать). Концепция быстрой сортировки заключается в разбиении заданного списка или массива. Чтобы разбить список, мы сначала выбираем опорный элемент. Все элементы в списке будут сравниваться с этим опорным элементом. В конце процесса разбиения все элементы, которые меньше опорного элемента, будут находиться слева от опорного элемента, в то время как все элементы, которые больше опорного элемента, будут находиться справа от опорного элемента в массиве.

Сложность в среднем случае — O(n log n), в худшем случае — O(n²).

Реализация на Python:

def quickSort(arr, first, last):
    if last > first:
        split = partition(arr, first, last)
        quickSort(arr, first, split-1)
        quickSort(arr, split+1, last)

def partition(arr, first, last):
    pivot = arr[first]
    left = first+1
    right = last
    done = True
    while done:
        while left <= right and arr[left] <= pivot:
            left = left + 1
        while arr[right] >= pivot and right >= left:
            right = right - 1
        if right < left:
            done = False
        else:
            arr[left], arr[right] = arr[right], arr[left]

    arr[first], arr[right] = arr[right], arr[first]
    return right

if name == "__main__":
    lst = [-5, 8, 4, 52, 0, 20, 3, 9, 100]
    quickSort(lst, 0, len(lst)-1)
    print(lst)

Сортировка подсчетом

Данный алгоритм на первом шаге определяет максимальное значение в массиве. Далее создатся вспомогательный массив (счетчик) длиной, равной максимальному значению + 1. Каждый индекс этого массива будет представлять элемент из исходного массива, а значение по этому индексу — количество его вхождений. На следующем шаге необходимо пройти по исходному массиву и для каждого элемента увеличить соответствующий индекс в вспомогательном массиве. После этого мы рассчитываем совокупную сумму элементов в вспомогательном массиве. Затем нужно определить индекс каждого элемента из исходного массива в вспомогательном массиве и поместить элемент на вычисленный индекс в отсортированном массиве. После размещения каждого элемента уменьшить его счёт на 1 в вспомогательном массиве. Да, этот алгоритм посложнее всех предыдущих!

Сложность алгоритма сортировки подсчётом — O(n + k), где n — длина входного массива, а k — диапазон значений элементов.

Программная реализация на Python:

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    output = [0] * len(arr)

    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    for i in range(len(arr)):
        arr[i] = output[i]

data = [4, 2, 2, 8, 3, 3, 1]
counting_sort(data)
print("Sorted array:", data) 

Поразрядная сортировка

Алгоритм поразрядной сортировки (Radix Sort) менее распространен в отличии от предыдущих. Это линейный алгоритм сортировки, который сортирует элементы, обрабатывая их значение за значением. Это эффективный алгоритм сортировки для целых чисел или строк с ключами фиксированного размера.

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения, например, строки, и вообще любые данные, представленные в виде набора байтов.

Сравнение производится поразрядно: сначала сравниваются значения одного крайнего разряда, и элементы группируются по результатам этого сравнения, затем сравниваются значения следующего разряда, соседнего, и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе групп, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем аналогично делается для следующего разряда, и так до конца.

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц — LSD (least significant digit)) или более значащих цифр (по левой стороне, со стороны более значащих разрядов — MSD от (most significant digit)).

При LSD-сортировке получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя сортировку по единицам внутри десятков, затем по сотням, сохраняя сортировку по десяткам и единицам внутри сотен, и так далее.

При MSD-сортировке получается алфавитный порядок, который уместен для сортировки строк текста. Например, «b, c, d, e, f, g, h, i, j, ba» сортировку как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, то получится алфавитный, но не числовой порядок: 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Сложность этого алгоритма O(n*k), где k- разрядность элементов массива.

Ниже представлена программная реализация для LSD сортировки.

def countingSort(arr, exp1): 
    n = len(arr) 
    output = [0] * (n) 
    count = [0] * (10) 

    for i in range(0, n): 
        index = (arr[i]/exp1) 
        count[int((index)%10)] += 1

    for i in range(1,10): 
        count[i] += count[i-1] 

    i = n-1
    while i>=0: 
        index = (arr[i]/exp1) 
        output[ count[ int((index)%10) ] - 1] = arr[i] 
        count[int((index)%10)] -= 1
        i -= 1

    i = 0
    for i in range(0,len(arr)): 
        arr[i] = output[i] 

def radixSort(arr):

    max1 = max(arr)
    exp = 1
    while max1 // exp > 0:
        countingSort(arr,exp)
        exp *= 10

arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)

for i in range(len(arr)):
    print(arr[i],end=" ")

Заключение

Мы рассмотрели семь алгоритмов сортировки, начиная от самых простых и наименее эффективных и заканчивая более сложными, но и во многих случаях более быстрыми. Вообще, в современных языках программирования уже имеется множество библиотек, содержащих готовые реализации алгоритмов сортировки, однако понимание принципов работы и возможность при необходимости модернизировать реализацию алгоритма под свои нужды тоже часто требуется разработчикам. Так что понимание принципов работы алгоритмов сортировки будет весьма полезно в работе.

Всех желающих приглашаем на открытые уроки онлайн-курса «Алгоритмы и структуры данных», на которых погрузимся в мир алгоритмов и сортировки:

• Эффективное сжатие текста: код Хаффмана в действии — 11 июня в 20:00

• Продвинутые методы архивации: LZ77/78 — 25 июня в 20:00

А чтобы проверить свой уровень знаний для поступления на курс по алгоритмам, пройдите вступительное тестирование.