Статья Алгоритмы сортировки и их реализация на Python

[tabac]

Сегодня расскажу про методы сортировки
В данной статье пойдет речь про:

• Сортировка выбором
• Сортировка вставками
• Сортировка “Методом пузырька”
• Сортировка Шелла
• Быстрая сортировка

Спойлер: Сортировка выбором

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

Пример реализации

def ssort(array):
    for i in range(len(array)):
        indxMin = i
        for j in range(i+1, len(array)):
            if array[j] < array[indxMin]:
                indxMin = j
        tmp = array[indxMin]
        array[indxMin] = array[i]
        array[i] = tmp
    return a

Спойлер: Сортировка вставками

Алгоритм примерно такой:

• из массива последовательно берется каждый элемент
• вставляется в его отсортированную часть(например в начале массива)

Код сортировки:

def isort(array):
    for i in range(len(array)):
        v = array[i]
        j = i
        while (array[j-1] > v) and (j > 0):
            array[j] = array[j-1]
            j = j - 1
        array[j] = v
        print array
    return array

Спойлер: Bubble sort(Сортировка методом пузырька)

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

def bubble_sort(array):
    a = array
    for i in range(len(a),0,-1):
        for j in range(1, i):
            if a[j-1] > a[j]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
                print a
    return a

Спойлер: Сортировка методом шелла

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

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

def Shell(A):
    t = int(len(A)/2)
    while t > 0:
        for i in range(len(A)-t):
            j = i
            while j >= 0 and A[j] > A[j+t]:
                A[j], A[j+t] = A[j+t], A[j]
                j -= 1
        t = int(t/2)

Спойлер: Быстрая сортировка

Одна из самых быстрых сортировок. Идея алгоритма заключается в том, что выбирается опорный элемент, относительно которого будет происходит сортировка. Равные и бОльшие элементы помещаются справа, меньшие – слева. Затем к полученным подмассивам рекурсивно применяются два первых пункта.

def QuickPas(s, aL, aR):
    l, r=aL, aR
    mid = (s[l]+s[(l+r)/2]+s[r])/3
    while lmid:r-=1
        if l<=r:
            if s[l]>s[r]:
                s[l], s[r] = s[r], s[l]
            l+=1
            r-=1
    if r>aL: QuickPas(s, aL, r)
    if l<aR: QuickPas(s, l, aR)

Если у кого возник вопрос какая сортировка самая быстрая - это надо обращаться к понятию о сложности алгоритма.
А пока - из предложенных быстрая сортировка показывает себя наилучшим образом.

Если было полезно или интересно ставь лайк!)
Еще нашел прикольный сайт с демонстрацией алгоритмов

автор @komodikus

 

[Guron_18]

ÐпиÑание алгоÑиÑмов ÑоÑÑиÑовки и ÑÑавнение Ð¸Ñ Ð¿ÑоизводиÑелÑноÑÑи

ÐÑÑÑпление Ðа ÑÑÑ ÑÐµÐ¼Ñ Ð½Ð°Ð¿Ð¸Ñано Ñже немало ÑÑаÑей. Ðднако Ñ ÐµÑе не видел ÑÑаÑÑи, в коÑоÑой ÑÑавниваÑÑÑÑ Ð²Ñе оÑновнÑе ÑоÑÑиÑовки на болÑÑом ÑиÑле ÑеÑÑов Ñазного Ñипа и ÑазмеÑа. ÐÑоме Ñого...

habr.com