import random
UnorderedList =[random.randint(1,10000) for i in range(100000)]
OrderedList= ['' for i in range(len(UnorderedList))]


def QuickSort( lists, OrderedLists,index):
    if len(lists)==0:
        return OrderedLists
    UList = []; LList =[]
    pivot = random.choice(lists)
    lists.remove(pivot)
    for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)
    OrderedLists[index+len(LList)]= pivot
    QuickSort(UList, OrderedLists, index+len(LList)+1)
    QuickSort(LList,OrderedLists,index)
    return OrderedLists


ans = QuickSort(UnorderedList, OrderedList,0)
print(ans)

Вчера в школе мы обсуждали методы сортировки, и я познакомился с быстрой сортировкой, которая известна (по названию) как очень быстрый метод сортировки. Мой учитель информатики также сказал, что алгоритм имеет рекурсию и обычно «задействован». Он также сказал, что не ожидал, что кто-то из нашего класса сможет его запрограммировать, что я воспринял как вызов. Итак, час в мою субботу, и вот мое решение.

Предпосылки:

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

  • Рекурсия
  • Понимание списка
  • Функции и параметры
  • Знание других методов сортировки, таких как пузырьковая, вставка и слияние.
  • Индексация списка

Что такое быстрая сортировка?

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

В этом методе используется принцип «разделяй и властвуй», поскольку мы сразу распределяем значения по половинкам набора (выше, чем точка опоры и ниже точки опоры), что, в свою очередь, означает, что это применимо для очень больших списков. Так, например, при использовании модуля time он сортировал список из 100 элементов в диапазоне целых чисел от 1 до 10 000 за 0,001232 секунды. Поскольку это разделяй и властвуй, это означает, что запись O будет равна 0 (n x log n), поэтому 1000 элементов заняли 0,2994 секунды и, наконец, 100 000 элементов за 0,543 секунды, что очень быстро. К сожалению, работа с большими числами замедляется: 1 000 000 элементов занимает 11,18 секунд, но в конце статьи я предложу способ ускорения программы, который станет для вас проблемой, если вы захотите адаптировать этот код.

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



QuickSort — GeeksforGeeks
Как и сортировка слиянием, QuickSort — это алгоритм «разделяй и властвуй. Он выбирает элемент в качестве опорного и разбивает данный…www.geeksforgeeks.org»



Код:

import random
UnorderedList =[random.randint(1,10000) for i in range(100000)]
OrderedList= ['' for i in range(len(UnorderedList))]

Первоначально мы импортируем случайную библиотеку, чтобы мы могли использовать ее как для создания неупорядоченного списка, так и для случайного выбора опорной точки. Затем мы используем понимание списка, используя метод random.randint, который выбирает случайное число от 1 до 10 000, это происходит 100 000 раз, что означает, что в конце у нас есть список из 100 000 случайных элементов, которые неупорядочены. Затем я создаю упорядоченный список, который пока будет пуст, но постепенно будет заполняться всеми правильно упорядоченными элементами. По этой причине он заполнен ‘s.

ans = QuickSort(UnorderedList, OrderedList,0)
print(ans)

Прежде чем перейти к основной функции, я объясню эти последние 2 строки. Это вызывает функцию QuickSort и передает все соответствующие аргументы, а возвращаемое значение будет сохранено в переменной ans. Затем мы можем распечатать этот окончательный результат. Сначала я установил его как переменную, потому что в реальном приложении вам нужен отсортированный список для более реалистичной обработки.

def QuickSort( lists, OrderedLists,index):
    if len(lists)==0:
        return OrderedLists
    UList = []; LList =[]
    pivot = random.choice(lists)
    lists.remove(pivot)
    for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)
    OrderedLists[index+len(LList)]= pivot
    QuickSort(UList, OrderedLists, index+len(LList)+1)
    QuickSort(LList,OrderedLists,index)
    return OrderedLists

Эта последняя часть кода является фактической функцией. Во-первых, я объясню параметры:

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

if len(lists)==0:
        return OrderedLists

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

UList = []; LList =[]
pivot = random.choice(lists)
lists.remove(pivot)

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

for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)

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

OrderedLists[index+len(LList)]= pivot
QuickSort(UList, OrderedLists, index+len(LList)+1)
QuickSort(LList,OrderedLists,index)

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

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

Задача: как вы видели, для сортировки 1 000 000 элементов программе потребовалось 11 секунд, а это слишком много. Ваша задача состоит в том, чтобы добавить в код функции так, чтобы если какой-либо список, переданный в функцию, состоял всего из 3 элементов, то они просто добавляли набор этих значений в упорядоченный список. Это связано с тем, что при сортировке в верхнем и нижнем списках они автоматически означают, что сортируются 3 значения.