алгоритмы сортировки

В этом посте я собираюсь показать вам общие алгоритмы сортировки и представить их реализацию на python. Если вы работаете или уже проходили собеседование на программиста, вы наверняка знаете, как важно знать и осваивать алгоритмы, чтобы повысить свой уровень кодирования или иметь шанс получить работу.
Даже если они могут показаться легкими, они действительно могут быть запутанными. И именно поэтому вы должны много практиковаться.
Как сказал мудрец на Коре:

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

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

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

8 обязательных алгоритмов сортировки

Этот раздел посвящен объяснению каждого алгоритма: концепции, сложности и вариантов использования. Я также предоставил реализацию для каждого алгоритма, на Python. Однако, если вы хотите попрактиковаться, попробуйте написать реализацию самостоятельно, прежде чем смотреть готовую.

Пузырьковая сортировка

Пузырьковая сортировка — простой алгоритм сортировки, который работает, меняя элементы между собой, если они находятся в неправильном порядке.
Пример :

Пузырьковая сортировка

def bubbleSort(data):
    lenght = len(data)

    for iIndex in range(lenght):
        swapped = False

        for jIndex in range(0, lenght - iIndex - 1):

            if data[jIndex] > data[jIndex + 1]:
                data[jIndex], data[jIndex + 1] = data[jIndex + 1], data[jIndex]
                swapped = True

        if swapped == False:
            break

    print(data)
Алгоритм пузырьковой сортировки
  • Наихудшая и средняя сложность пузырьковой сортировки — это О (n2), это означает, что данные находятся в обратном порядке, который мы хотим отсортировать, или элементы произвольно распределены в списке.
  • В лучшем случае сложность O (n). Это тот случай, когда данные уже отсортированы.

Пузырьковая сортировка используется когда:

  • нужен простой код;
  • сложность не имеет значения.

Выборочная сортировка

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

Выборочная сортировка

Анимация алгоритма. Красный текущий минимум. Желтый это отсортированный список. Синий является текущим элементом.

Код:

def selectionSort(data):

    for scanIndex in range(0, len(data)):

        minIndex = scanIndex

        for compIndex in range(scanIndex + 1, len(data)):
            if data[compIndex] < data[minIndex]:
                minIndex = compIndex

        if minIndex != scanIndex:
            data[scanIndex], data[minIndex] = data[minIndex], data[scanIndex]

            print(data)
Алгоритм выборочной сортировки

Сортировка выбора имеет те же сложности, что и Пузырьковая сортировка.

Сортировка выбора используется, когда:

  • Объем массива не велик
  • Обязательна проверка всех элементов
  • Требуется минимум операций

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

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

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

Код:

def insertionSort(data):

    for scanIndex in range(1, len(data)):
        tmp = data[scanIndex]

        minIndex = scanIndex

        while minIndex > 0 and tmp < data[minIndex - 1]:
            data[minIndex] = data[minIndex - 1]
            minIndex -= 1

        data[minIndex] = tmp

        print(data)
Алгоритм сортировки вставкой
  • Сортировка вставки имеет наихудший и средний случай сложности O (n2). Это происходит соответственно, когда массив сортируется в обратном порядке и когда элементы произвольно организованы в массиве.
  • В лучшем случае сложность O (n). Это происходит, когда данные уже отсортированы в нужном порядке.

Сортировка вставки используется, когда:

  • Осталось отсортировать несколько элементов;
  • Массив маленький.

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

Быстрая сортировка- эффективный алгоритм сортировки. Он использует подход «разделяй-властвуй» для разделения массива на подмассивы, которые рекурсивно вызываются для сортировки элементов.
Реализация алгоритма Быстрой сортировки требует выбора оси, затем разбивает массив на два подмассива в соответствии с точкой, а затем располагает их следующим образом, если они больше / меньше точки. Затем мы сортируем два подмассива и повторяем процесс снова.
Пример:

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

Код:

def quickSort(data, left, right):
    if right<= left:
        return 
    else:
        pivot = partition(data, left, right)
        quickSort(data, left, pivot - 1)
        quickSort(data, pivot + 1, right)

    return data

def partition(data, left, right):
    """This function chooses a pivot point that dertermines the left and right side of the sort"""
    pivot = data[left]
    leftIndex = left + 1
    rightIndex = right

    while True:
        while leftIndex <= rightIndex and data[leftIndex] <= pivot:
            leftIndex += 1
        while rightIndex >= leftIndex and data[rightIndex] >= pivot:
            rightIndex -= 1
        if rightIndex <= leftIndex:
            break
        data[leftIndex], data[rightIndex] = data[rightIndex], data [leftIndex]
        print(data)

    data[left], data[rightIndex] = data[rightIndex], data[left]
    print(data)

    return rightIndex
Быстрая сортировка
  • Быстрая сортировка имеет сложность O (n2) в худшем случае. Это происходит, когда выбранный элемент поворота всегда является самым большим или самым маленьким элементом.
  • В лучшем и среднем случае сложность O (n * log (n)). Это происходит, когда элемент поворота всегда является средним элементом или рядом со средним элементом.

Быстрая сортировка используется, когда:

  • Рекурсия нужна и поддерживается;
  • Массив небольшой;
  • Осталось отсортировать несколько элементов.

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

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

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

Код:

def mergeSort(data):
    """Эта функция определяет разделен ли массив на части"""

    if len(data) < 2:
        return data

    middle = len(data)//2

    # We break the list in two parts
    left = mergeSort(data[:middle])
    right = mergeSort(data[middle:])

    # Merge the two sorted parts into a larger piece.

    print("The left side is: ", left)
    print("The right side is: ", right)

    merged = merge(left, right)

    print("Merged ", merged)
    return merged
def merge(left, right):
    """Когда левая сторона / правая сторона пуста,
     Это означает, что это отдельный элемент и он уже отсортирован."""

    #We make sure the right/left side is not empty
    #meaning that it's an individual item and it's already sorted.
    if not len(left):
        return left

    if not len(right):
        return right

    result = []
    leftIndex = 0
    rightIndex = 0
    totalLen = len(left) + len(right)

    #
    while (len(result) < totalLen):

        #Perform the required comparisons and merge the two parts

        if left[leftIndex] < right[rightIndex]:
            result.append(left[leftIndex])
            leftIndex += 1
        else:
            result.append(right[rightIndex])
            rightIndex += 1

        if leftIndex == len(left) or rightIndex == len(right):
            result.extend(left[leftIndex:] or right[rightIndex:])

            break

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

Сортировка слиянием имеет сложность O (n * log (n)) для наихудшего и среднего случаев, что делает его более быстрым, чем некоторые другие алгоритмы сортировки.

Bucket сортировка или сортировка по группам

Алгоритм сортировки по группам работает путем деления массива на сегменты. Затем элементы в каждом сегменте сортируются с использованием любых алгоритмов сортировки или путем рекурсивного вызова алгоритма сортировки сегментов.
Процесс сортировки может быть рассмотрен как подход рассеяния. Элементы сначала разбрасываются на сегменты, а затем элементы сортируются. Наконец, элементы собираются по порядку.

Код:

def bucketSort(data):
    bucket = []

    for iIndex in range(len(data)):
        bucket.append([])

    for jIndex in data:
        index_bucket = int(10 * jIndex)
        bucket[index_bucket].append(jIndex)
        print(bucket)

    for iIndex in range(len(data)):
#Я использовал встроенный метод sorted() для сортировки массива. 
        bucket[iIndex] = sorted(bucket[iIndex])

        kIndex = 0

        for iIndex in range(len(data)):

            for jIndex in range(len(bucket[iIndex])):
                data[kIndex] = bucket[iIndex][jIndex]
                kIndex += 1

    print(data)
Bucket сортировка
  • Алгоритм имеет сложность O (n2) в худшем случае. Это происходит, когда элементы в одном и том же диапазоне помещаются в один и тот же сегмент, что приводит к большему количеству элементов в некоторых сегментах, чем в других. Кроме того, может быть еще хуже, если для сортировки элементов в корзинах используется неподходящий алгоритм сортировки.
  • В лучшем случае сложность O (n + k). Это происходит, когда элементы равномерно распределены в корзинах с почти равным количеством элементов в каждой корзине. Может быть даже лучше, если массив уже отсортирован.
  • Средняя сложность случая O (n). Это происходит, когда элементы случайно распределены в массиве.

Bucket Sort используется:

  • С плавающими числами;
  • Ввод равномерно распределен по диапазону.

Shell Sort

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

Пример:

Shell сортировка

Код:

def shellSort(data, length):

    gap = length//2

    while gap > 0:
        for iIndex in range(gap, length):

            temp = data[iIndex]

            jIndex = iIndex

            while jIndex >= gap and data[jIndex - gap] > temp:
                data[jIndex] = data[jIndex - gap]

                jIndex -= gap

            data[jIndex] = temp

        gap //= 2

    print(data)
Shell сортировка
  • Shell сортировка имеет сложность в худшем случае, меньшую или равную O (n2).
  • Shell сортировка имеет сложность O (n * log (n)) в среднем и наилучшем случае.

Оболочка сортировки используется, когда:

  • Рекурсия превышает лимит.
  • Вставка не работает хорошо, когда близкие элементы находятся далеко.

Сортировка кучи

Сортировка кучи — это один из лучших методов сортировки на месте и без квадратичной сложности в худшем случае. Сортировка кучи использует структуру данных кучи.
Куча — это полное двоичное дерево. Также проверяются такие правила как:

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

Чтобы создать алгоритм сортировки кучи, мы должны сначала создать кучу массива. Когда все будет готово, мы можем написать алгоритм сортировки кучи. Преимущество сортировки кучи состоит в том, что значение в корне всегда больше, чем все значение, поэтому мы можем поместить его в конец отсортированного массива, удалить его из кучи, а затем снова сложить в двоичное дерево, чтобы получить большее значение снова наверху.
Пример:

Сортировка кучи

Код:

def createHeap(data, length, index):

    largest = index
    left = 2 * index + 1
    right = 2 * index + 2

    if left < length and data[index] < data[left]:
        largest = left

    if right < length and data[largest] < data[right]:
        largest = right

    if largest != index:
        data[index], data[largest] = data[largest], data[index]
        createHeap(data, length, largest)

def heapSort(data):
    length = len(data)

    #We build max heap
    for index in range(length, 0, -1):
        createHeap(data, length, index)

    for index in range(length -1, 0, -1):
        data[index], data[0] = data[0], data[index]

        createHeap(data, index, 0)

    print(data)
Сортировка кучи

Сортировка кучи имеет O (n * log (n)) временные сложности для всех случаев (лучший случай, средний случай и худший случай), что делает его одним из наиболее используемых алгоритмов сортировки.
Сортировка кучи хорош, когда вам нужно знать только «наименьшую» (или «самую большую») коллекцию предметов, без лишних затрат на хранение оставшихся предметов в отсортированном порядке. Например, приоритетная очередь.

Вывод

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