Алгоритмы сортировки в Python

Что такое сортировка

Сортировка – упорядочивание списка элементов данных в заранее определенной последовательности
Алгоритмы сортировки – это набор инструкций, которые принимают массив или список в качестве входных данных и упорядочивают элементы в определенном порядке.
Сортировка чаще всего выполняется в числовом или алфавитном порядке (называемом лексикографическим) и может быть в возрастающем (A-Z, 0-9) или убывающем (Z-A, 9-0) порядке.

Существует множество типов алгоритмов сортировки: поразрядная, быстрая, пирамидальная, слиянием, пузырьком, Шеллаи т.д. Ни один из них не может считаться самым быстрым, поскольку каждый алгоритм предназначен для определенной структуры данных и набора данных. Это зависит от того, какой набор данных вы хотите отсортировать.
В этой заметке я остановлюсь на 5 наиболее часто используемых алгоритмах сортировки в Python.

1. Сортировка вставками

При сортировке вставкой вы сравниваете ключевой элемент с предыдущими элементами. Если предыдущие элементы больше, чем ключевой элемент, то вы перемещаете предыдущий элемент на следующую позицию.
Обычно начинают с индекса 1 входного массива.

def insertion_sort(arr):
    '''
    insertion sort function that takes an array to be sorted as an input.
    With your key element at the index 1 of the input array,
    traverse the array comparing the key element with the previous elements.
    If the previous element is greater than the key element,
    then move the previous element to the next position
    '''
    l = len(arr)
    i=1 #key element index
    while i<l:
        key_element=arr[i] 
        j=i-1 #previous element index
        while j>=0 and arr[j]>key_element:
             # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
            arr[j+1] = arr[j]
            j=j-1  

        arr[j+1]=key_element 
        i=i+1

    return arr

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

• Космическая сложность: O(1)
• Сложность по времени: O(n), O(n* n), O(n* n) для лучшего, среднего и худшего случаев соответственно.
• Сортировка на месте: Да

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

Сортировка выбором берет текущий наименьший элемент и меняет его местами.

Вот как это работает:

1. Найдите наименьший элемент в массиве и поменяйте его местами с первым элементом. >2. Найдите второй наименьший элемент и поменяйте его местами со вторым элементом массива.
2. Найдите третий наименьший элемент и поменяйте его местами с третьим элементом массива.
3. Повторяйте процесс поиска следующего наименьшего элемента и его замены на нужную позицию, пока весь массив не будет отсортирован.

def selection_sort(alist):
    for i in range(0, len(alist) - 1):
        smallest = i
        for j in range(i + 1, len(alist)):
            if alist[j] < alist[smallest]:
                smallest = j
        alist[i], alist[smallest] = alist[smallest], alist[i]

    return alist

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

• Сложность пространства: O(n)
• Сложность по времени: O(n2)
• Сортировка на месте: Да
• Стабильный: Нет

3. Сортировка пузырьком

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

def bubble_sort(alist):
    n=len(alist)
    for i in range(n):
        for j in range(i):
            if alist[j]>alist[j+1]:
                temp = alist[j]
                alist[j] = alist[j+1]
                alist[j+1] = temp

    return alist

Плюсы

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

Минусы

• Поскольку временная сложность составляет Ο(n2), он не подходит для больших наборов данных.
• Сортировка пузырьком очень медленная по сравнению с другими алгоритмами сортировки, такими как Быстрая сортировка.

Свойства сортировки пузырьком

• Пространственная сложность: O(1)
• Производительность в лучшем случае: O(n)
• Средняя производительность: O(n*n)
• Наихудшая производительность: O(n*n)
• Стабильно: Да

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

Быстрая сортировка использует подход “разделяй и властвуй”. Она делит список на более мелкие “разделы” с помощью “стержня”. Значения, которые меньше стержня, располагаются в левом разделе, а большие значения располагаются в правом разделе. Каждый раздел рекурсивно сортируется с помощью быстрой сортировки.
Поворотным элементом может быть первый, последний, средний или любой случайный элемент массива.

Быстрая сортировка включает в себя следующие шаги:

1. Выберите элемент, который будет служить стержнем.
2. Разбиение на разделы: Отсортируйте массив таким образом, чтобы все элементы меньше стержня располагались слева, а все элементы больше стержня – справа.
3. Вызовите Quicksort рекурсивно, принимая во внимание предыдущий стержень, чтобы правильно разделить левый и правый массивы.

def quicksort(z):
    if(len(z)>1):        
        piv=int(len(z)/2)
        val=z[piv] 
        lft=[i for i in z if i<val]
        mid=[i for i in z if i==val]
        rgt=[i for i in z if i>val]

        res=quicksort(lft)+mid+quicksort(rgt)
        return res
    else:
        return z

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

• Пространственная сложность: O(n)
• Не стабильно
• Временная сложность: Лучший случай – nlog(n)

часть 1

часть 2

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

Merge sort – это алгоритм сортировки, основанный на подходе программирования “разделяй и властвуй”. Он продолжает делить список на более мелкие подсписки до тех пор, пока все подсписки не будут содержать только 1 элемент. Затем он объединяет их в отсортированном виде, пока все подсписки не будут заполнены.

def merge(left,right,compare):
    result = [] 
    i,j = 0,0
    while (i < len(left) and j < len(right)):
        if compare(left[i],right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result



def merge_sort(arr, compare = lambda x, y: x < y):
     #Used lambda function to sort array in both(increasing and decresing) order.
     #By default it sorts array in increasing order
    if len(arr) < 2:
        return arr[:]
    else:
        middle = len(arr) // 2
        left = merge_sort(arr[:middle], compare)
        right = merge_sort(arr[middle:], compare)
        return merge(left, right, compare)

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

• Сложность пространства: O(n)
• Временная сложность: O(nlog(n)).
• Стабильно: Да

Сложности алгоритмов сортировки