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

Posted on 14 Oct 2015

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

Но иногда интересно заглянуть под капот и понять какие есть алгоритмы сортировки и как они работают. Цель текущей стати на примерах продемонстрировать некоторые из элементарных алгоритмов сортировки.

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

Этот алгоритм эффективно работает при сортировке небольшого количества элементов. Ниже приведен пример реализации данного алгоритма

def insertion_sort(arrayToSort):
    for i in xrange(1, len(arrayToSort)):
        key = arrayToSort[i]
        j = i - 1
        while (j >= 0) and (arrayToSort[j] > key):
            arrayToSort[j + 1] = arrayToSort[j]
            j -= 1
        arrayToSort[j+1] = key
    print("Sorted array: ", arrayToSort)

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

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

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

Разделение - Делим n-элементную последовательность на две подпоследовательности по n/2 элементов

Властвование - Рекурсивно сортируем эти две подпоследовательности с использованием сортировки слиянием

Комбинирование - Соединяем две отсортированные последовательности для получения результата

Пример реализации данного алгоритма:

def merge_sort(arrayToSort):

    if len(arrayToSort) > 1:
        mid = len(arrayToSort) // 2
        lefthalf = arrayToSort[:mid]
        righthalf = arrayToSort[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)
        i = 0
        j = 0
        k = 0

        while (i < len(lefthalf)) and (j < len(righthalf)):
            if lefthalf[i] < righthalf[j]:
                arrayToSort[k] = lefthalf[i]
                i += 1
            else:
                arrayToSort[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):
            arrayToSort[k] = lefthalf[i]
            i += 1
            k += 1

        while j<len(righthalf):
            arrayToSort[k] = righthalf[j]
            j += 1
            k += 1

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