Алгоритмы неформально. Инструкция для начинающих питонистов - [33]

    if(len(left) > 0):

        for i in left:

            newcabinet.append(i)

    if(len(right) > 0):

        for i in right:

            newcabinet.append(i)

    return(newcabinet)

import math

def mergesort(cabinet):

    newcabinet = []

    if(len(cabinet) == 1):

        newcabinet=cabinet

    else:

        left = mergesort(cabinet[:math.floor(len(cabinet)/2)])

        right = mergesort(cabinet[math.floor(len(cabinet)/2):])

        newcabinet = merging(left,right)

    return(newcabinet)

cabinet = [4,1,3,2,6,3,18,2,9,7,3,1,2.5,-9]

newcabinet=mergesort(cabinet)

Можно добавить в код сортировки слиянием счетчик шагов и сравнить результаты с алгоритмом сортировки слиянием. Процесс сортировки слиянием состоит из последовательного разбиения исходного списка на подсписки и последующего слияния подсписков с сохранением порядка сортировки. Каждый раз, когда список разбивается надвое, полученные списки имеют половинную длину. Количество разбиений списка длины n пополам, прежде чем один подсписок будет содержать только один элемент, составляет около log(n) (логарифм по основанию 2), а количество сравнений при каждом слиянии не превышает n. Таким образом, n или менее сравнений log(n) разбиений означают, что сортировка слиянием имеет сложность O(n× log(n)), что на первый взгляд не впечатляет, но в действительности этот алгоритм один из лучших. Собственно, при вызове встроенной функции сортировки Python:

print(sorted(cabinet))

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

Спящая сортировка

В 2011 году анонимный участник интернет-форума 4chan предложил и предоставил код алгоритма сортировки, который до этого нигде не публиковался. Этот алгоритм получил название спящей сортировки (sleep sort).

Спящая сортировка не разрабатывалась для моделирования каких-либо реальных ситуаций наподобие вставки папок на полку шкафа. Если вам нужна аналогия, то можно рассмотреть задачу распределения мест на спасательных шлюпках тонущего «Титаника». Детям и молодежи отдается приоритет, а люди зрелого возраста пытаются занять оставшиеся места. Если объявить: «Сначала на шлюпки допускаются молодые, а потом старые», возникнет хаос, так как все пассажиры начнут сравнивать свой возраст — они столкнутся с трудной задачей сортировки в неразберихе тонущего корабля.

Подход спящей сортировки к распределению мест выглядел бы примерно так. Вы объявляете: «Пожалуйста, оставайтесь на месте и считайте по порядку: 1, 2, 3… Как только вы досчитаете до своего текущего возраста, выходите вперед и идите занимать место на шлюпке». Восьмилетние пассажиры закончат считать на секунду раньше девятилетних, получат секунду форы и смогут занять место на шлюпке раньше тех, кому исполнилось девять. Восьми- и девятилетние окажутся на лодках раньше десятилетних и т.д. Мы рассчитываем на то, что люди способны выждать время, пропорциональное метрике сортировки, и в дальнейшем занять свое место на шлюпке, после чего сортировка происходит без каких-либо усилий и без прямых сравнений отдельных элементов.

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

На Python спящая сортировка может быть реализована так, как показано ниже. Мы импортируем модуль threading, который позволяет создавать разные программные потоки (компьютерные процессы), чтобы каждый элемент мог сделать паузу, а затем вставить себя в итоговый список. Вдобавок импортируется модуль time.sleep для перевода программных потоков в «спящее» состояние на соответствующий промежуток времени.

import threading

from time import sleep

def sleep_sort(i):

    sleep(i)

    global sortedlist

    sortedlist.append(i)

    return(i)

items = [2, 4, 5, 2, 1, 7]

sortedlist = []

ignore_result = [threading.Thread(target = sleep_sort, args = (i,)).start() \

for i in items]

Отсортированный список будет храниться в переменной sortedlist, а на список ignore_result не обращайте внимания. Вы увидите, что одно из преимуществ спящей сортировки заключается в том, что она компактно записывается на Python. Кроме того, будет интересно вывести переменную sortedlist до завершения сортировки (в данном случае около 7 секунд), поскольку в зависимости от того, когда именно будет выполняться команда print, вы увидите разные списки. Тем не менее у этой сортировки есть и серьезные недостатки. Один из них заключается в том, что выполнение невозможно приостановить на отрицательное время, так что спящая сортировка не позволяет сортировать списки с отрицательными числами. Другой недостаток — значительная зависимость выполнения сортировки от выбросов; если вставить в список число 1000, то завершения выполнения придется ожидать не менее 1000 секунд. Наконец, числа, близкие друг к другу, могут быть вставлены в неверном порядке, если параллельное выполнение потоков было неидеальным. Наконец, так как спящая сортировка использует многопоточное выполнение, она не сможет (эффективно) работать на оборудовании или в программных средах, которые не поддерживают (эффективно) многопоточность.