Алгоритмы сортировки данных с Python3

newbie

Опубликован:  2018-10-03T12:54:47.480212Z
Отредактирован:  2018-10-03T12:27:31.804356Z
Сортировка данных по тому или иному признаку - очень частая задача, с которой сталкивается программист при работе с данными. В этом обзоре поговорим о сортировке списков с целыми числами, методах сортировки доступных с Python3, а так же рассмотрим некоторые классические алгоритмы сортировки массивов целых чисел.

1. Постановка задачи

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

Далее под спойлерами ниже я предлагаю несколько вариантов решения этой задачи при помощи языка программирования Python3.

2. Сортировка средствами Python3

К счастью, Python3 является языком программирования высокого уровня и имеет в своём арсенале стандартные средства для решения стандартных задач. Сортировка массива целых чисел по возрастанию - задача стандартная и средствами Питона решается элементарно.

RHqULrbedK.png

Бывает так, что экзаменатор хочет убедиться в достаточной алгоритмической подготовке экзаменуемого, и просит написать программу, которая не использует стандартные средства сортировки, а именно метод list.sort или функцию sorted из модуля builtins. Тогда решение этой задачи может выглядеть иначе.

fcu37RJrzl.png

Чуть-чуть больше кода... Здесь нужно кое-что пояснить.

Итак, создаю функцию sort_n, которая в качестве аргумента принимает какой-то список.

def sort_n(list_):

В теле этой функции создаю пустой список box.

    box = list()

Далее открываю цикл, в голове которого проверяется переданный в функцию список.

    while list_:

Напоминаю, что в Python3 булево значение пустого списка - False, а булево значение списка содержащего хотя бы один элемент - True, таким образом, цикл будет действовать до тех пор, пока в списке list_ есть хотя бы один элемент, и как только список list_ становится пустым, цикл прерывается.

В теле цикла создаём переменную m и даём ей значение минимального элемента в списке list_, минимальный элемент находим при помощи встроенной функции min.

        m = min(list_)

Добавляем значение переменной m в конец списка box.

        box.append(m)

А из списка list_ значение переменной m удаляем.

        list_.remove(m)

После завершения цикла while отдаём списку list_ все элементы содержащиеся в списке box.

    list_.extend(box)

И возвращаем None.

    return None

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

Таким образом, на скриншоте выше видно, что функция sort_n удовлетворяет условиям поставленной задачи и сортирует заданный список по возрастающей.

Случается так, что экзаменатору хочется большего, и он даёт ещё одну вводную, программа сортировки должна быть написана без использования встроенной функций min и стандартных методов списка. Uh-oh! Если в арсенале экзаменуемого нет ни одного классического алгоритма сортировки, тогда всё плохо. Поэтому под спойлерами ниже присутствуют дополнительные решения задачи.

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

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

iaaNMewyxY.png

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

Sdp6p8PUks.png

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

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

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

rJuqCqQUrn.png

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

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

Ещё один классический алгоритм сортировки массива чисел - сортировка выбором.

kbecvxTu7v.png

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

Комментарии:

newbie

2018-10-04T07:01:12.912091Z

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

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

def sort_i(list_):
    for i in range(1, len(list_)):
        box = list_[i]
        j = i - 1
        while j >= 0 and box < list_[j]:
            list_[j+1] = list_[j]
            j -= 1
        list_[j+1] = box
    return None

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

def sort_b(list_):
    for i in range(len(list_) - 1):
        marker = False
        for j in range(len(list_) - i - 1):
            if list_[j] > list_[j+1]:
                list_[j], list_[j+1] = list_[j+1], list_[j]
                marker = True
        if not marker:
            break
    return None

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

def sort_s(list_):
    for i in range(len(list_)):
        m = i
        box = list_[i]
        for j in range(i+1, len(list_)):
            if list_[j] < box:
                m = j
                box = list_[j]
        list_[m], list_[i] = list_[i], box
    return None