Я совершенно не знаком с Python и пытаюсь реализовать в нем быструю сортировку. Может ли кто-нибудь помочь мне завершить код?

Я не знаю, как объединить три массива и распечатать их.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Быстрая сортировка без дополнительной памяти (на месте)

Применение:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

Есть еще один лаконичный и красивый вариант

def qsort(arr): 
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]]) + \
               [arr[0]] + \
               qsort([x for x in arr[1:] if x >= arr[0]])

# this comment is just to improve readability due to horizontal scroll!!!

Позвольте мне объяснить приведенные выше коды для подробностей.

1. выберите первый элемент массива arr[0]как опорный элемент

   [arr[0]]

2. qsort те элементы массива, которые меньше, чем точка поворота с List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort те элементы массива, которые больше, чем точка поворота с List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

Этот ответ представляет собой быструю сортировку для файлов Python 2.x. Мой ответ - это интерпретация локального решения из Rosetta Code, которое Python 3тоже работает :

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

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

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

Быстрая сортировка с Python

В реальной жизни мы всегда должны использовать встроенную сортировку, предоставляемую Python. Однако понимание алгоритма быстрой сортировки поучительно.

Моя цель здесь - так разбить предмет, чтобы читатель мог легко его понять и воспроизвести без необходимости возвращаться к справочным материалам.

Алгоритм быстрой сортировки по сути следующий:

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

Если данные распределены случайным образом, выбор первой точки данных в качестве точки поворота эквивалентен случайному выбору.

Читаемый пример:

Во-первых, давайте посмотрим на читаемый пример, в котором комментарии и имена переменных используются для указания промежуточных значений:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

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

В гольф:

Это может быть гольф до 88 символов:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Чтобы увидеть, как мы к этому пришли, сначала возьмите наш читаемый пример, удалите комментарии и строки документации и найдите точку поворота на месте:

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

Теперь найдите внизу и вверху на месте:

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

Теперь, зная, что andвозвращает предыдущий элемент, если ложно, иначе, если это правда, он оценивает и возвращает следующий элемент, у нас есть:

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

Поскольку лямбда-выражения возвращают одно выражение, и мы упростили его до одного выражения (хотя оно становится все более нечитаемым), теперь мы можем использовать лямбда:

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

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

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Обратите внимание, что эта лямбда, как и большинство игр в гольф, - довольно плохой стиль.

Быстрая сортировка на месте с использованием схемы Hoare Partitioning

Предыдущая реализация создает множество ненужных дополнительных списков. Если мы сможем сделать это на месте, мы не тратим впустую пространство.

В приведенной ниже реализации используется схема разделения Хоара, о которой вы можете прочитать больше в Википедии (но мы, по-видимому, удалили до 4 избыточных вычислений на каждый partition()вызов, используя семантику цикла while вместо do-while и переместив шаги сужения в конец внешний цикл while.).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

Не уверен, достаточно ли тщательно протестировал:

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

Вывод

Этот алгоритм часто преподается на курсах информатики и спрашивается на собеседовании. Это помогает нам думать о рекурсии и о разделении и победе.

Quicksort не очень практичен в Python, поскольку наш встроенный алгоритм timsort достаточно эффективен, и у нас есть ограничения на рекурсию. Можно было бы ожидать , чтобы сортировать списки в месте с list.sortили создавать новые отсортированные списки sorted- оба из которых принять keyи reverseаргумент.

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

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

Конечно, вы можете пропустить сохранение всего в переменных и сразу вернуть их следующим образом:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

функциональный подход:

def qsort(list):
    if len(list) < 2:
        return list

    pivot = list.pop()
    left = filter(lambda x: x <= pivot, list)
    right = filter(lambda x: x > pivot, list)

    return qsort(left) + [pivot] + qsort(right)

подход к функциональному программированию

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Простая реализация от алгоритмов гроккинга

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

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

Например, попытка отсортировать следующий массив [12,4,5,6,7,3,1,15,1] (обратите внимание, что 1 появляется дважды) с помощью алгоритма Бриониуса .. в какой-то момент закончится пустым массивом less и равный массив с парой значений (1,1), которые не могут быть разделены на следующей итерации, и len ()> 1 ... следовательно, вы получите бесконечный цикл

Вы можете исправить это, либо возвращая массив, если меньше пусто, либо лучше, не вызывая sort в вашем равном массиве, как в ответе zangw

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)

        # Don't forget to return something!
        return sort(less)+ equal +sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Более причудливое решение также не работает, но по другой причине отсутствует предложение return в строке рекурсии, что в какой-то момент приведет к возврату None и попытке добавить его в список ...

Чтобы исправить это, просто добавьте возврат к этой строке

def qsort(arr): 
   if len(arr) <= 1:
      return arr
   else:
      return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

Это версия быстрой сортировки с использованием схемы разделения Хоара и с меньшим количеством свопов и локальных переменных.

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Разделение - разделение массива поворотной точкой, при которой меньшие элементы перемещаются влево, а большие элементы - вправо или наоборот. Поворот может быть случайным элементом из массива. Чтобы создать этот алгоритм, нам нужно знать, что такое начальный и конечный индекс массива и где находится точка поворота. Затем установите два вспомогательных указателя L, R.

Итак, у нас есть массив user [..., begin, ..., end, ...]

Начальная позиция указателей L и R
[..., begin, next, ..., end, ...]
     R L

while L <end
  1. Если пользователь [pivot]> пользователь [L], то переместите R на одну и поменяйте местами пользователя [R] с пользователем [L]
  2. переместите L на одну

Через некоторое время поменяйте местами пользователя [R] с пользователем [pivot]

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

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)

Или, если вы предпочитаете однострочник, который также иллюстрирует Python-эквивалент переменных C / C ++, лямбда-выражений и выражений if:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)

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

Как это работает ?

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

Вот пример вместе с визуальными элементами ... (поворот) 9,11,2,0

среднее: n журнал из n

худший случай: n ^ 2

Код:

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

items = [9,11,2,0] print (быстрая сортировка (элементов))

Алгоритм содержит две границы: одна имеет элементы меньше, чем точка поворота (отслеживается индексом «j»), а другая имеет элементы, превышающие точку поворота (отслеживается индексом «i»).

На каждой итерации новый элемент обрабатывается путем увеличения j.

Инвариант: -

1. все элементы между точкой поворота и i меньше точки поворота, и
2. все элементы между i и j больше, чем точка поворота.

Если инвариант нарушен, i-й и j-й элементы меняются местами, а i увеличивается.

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

Теперь элемент поворота будет на своем месте в последовательности. Элементы до него будут меньше, а следующие после него будут больше, и они не будут отсортированы.

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Выбор точки поворота

«Хороший» поворот приведет к двум подпоследовательностям примерно одинакового размера. Детерминистически поворотный элемент можно выбрать либо наивным образом, либо путем вычисления медианы последовательности.

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

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

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

def quicksort(array):
 if len(array) < 2:
  return array
 else:
  pivot = array[0]

 less = [i for i in array[1:] if i <= pivot]
 greater = [i for i in array[1:] if i > pivot]
 return quicksort(less) + [pivot] + quicksort(greater)

def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []

def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A

«Настоящая» реализация на месте [алгоритмы 8.9, 8.11 из книги по разработке алгоритмов и приложений Майкла Т. Гудрича и Роберто Тамасси]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()

Алгоритм состоит из 4 простых шагов:

1. Разделите массив на 3 разные части: левую, поворотную и правую, при этом поворотная точка будет иметь только один элемент. Выберем этот элемент поворота как первый элемент массива
2. Добавьте элементы в соответствующую часть, сравнивая их с элементом поворота. (объяснение в комментариях)
3. Повторяйте этот алгоритм, пока все элементы в массиве не будут отсортированы
4. Наконец, соедините левую + поворотную + правую части

Код для алгоритма на Python:

def my_sort(A):

      p=A[0]                                       #determine pivot element. 
      left=[]                                      #create left array
      right=[]                                     #create right array
      for i in range(1,len(A)):
        #if cur elem is less than pivot, add elem in left array
        if A[i]< p:
          left.append(A[i])         
          #the recurssion will occur only if the left array is atleast half the size of original array
          if len(left)>1 and len(left)>=len(A)//2:          
              left=my_sort(left)                            #recursive call
        elif A[i]>p: 
          right.append(A[i])                                #if elem is greater than pivot, append it to right array
          if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
              right=my_sort(right)
     A=left+[p]+right                                        #append all three part of the array into one and return it
     return A

my_sort([12,4,5,6,7,3,1,15])

Выполните этот алгоритм рекурсивно с левой и правой частями.

Еще одна реализация быстрой сортировки:

# A = Array 
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index

def swap(A,i1,i2):
  A[i1], A[i2] = A[i2], A[i1]

def partition(A,g,p):
    # O(n) - just one for loop that visits each element once
    for j in range(g,p):
      if A[j] <= A[p]:
        swap(A,j,g)
        g += 1

    swap(A,p,g)
    return g

def _quicksort(A,s,e):
    # Base case - we are sorting an array of size 1
    if s >= e:
      return

    # Partition current array
    p = partition(A,s,e)
    _quicksort(A,s,p-1) # Left side of pivot
    _quicksort(A,p+1,e) # Right side of pivot

# Wrapper function for the recursive one
def quicksort(A):
    _quicksort(A,0,len(A)-1)

A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]

print(A)
quicksort(A)
print(A)

Для версии Python 3.x : operatorмодуль использования функционального стиля , в первую очередь для улучшения читаемости.

from operator import ge as greater, lt as lesser

def qsort(L): 
    if len(L) <= 1: return L
    pivot   = L[0]
    sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

    return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

и протестирован как

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

Вот простая реализация: -

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

1. Сначала мы объявляем первое значение в массиве pivot_value, а также устанавливаем левую и правую метки
2. Мы создаем первый цикл while, этот цикл должен сообщить процессу раздела снова запустить его, если он не удовлетворяет необходимому условию.
3. затем мы применяем процесс разделения
4. после того, как оба процесса разделения были запущены, мы проверяем, удовлетворяет ли он надлежащему условию. Если это так, мы отмечаем его как выполненное, если нет, мы меняем левое и правое значения и применяем его снова
5. Как только это будет сделано, переключите левое и правое значения и верните split_point

Прилагаю код ниже! Эта быстрая сортировка - отличный инструмент для обучения из-за местоположения значения сводной таблицы . Поскольку он находится в постоянном месте, вы можете пройти его несколько раз и действительно понять, как все это работает. На практике лучше всего рандомизировать точку поворота, чтобы избежать времени выполнения O (N ^ 2).

def quicksort10(alist):
    quicksort_helper10(alist, 0, len(alist)-1)

def quicksort_helper10(alist, first, last):
    """  """
    if first < last:
        split_point = partition10(alist, first, last)
        quicksort_helper10(alist, first, split_point - 1)
        quicksort_helper10(alist, split_point + 1, last)

def partition10(alist, first, last):
    done = False
    pivot_value = alist[first]
    leftmark = first + 1
    rightmark = last
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivot_value:
            rightmark = rightmark - 1

        if leftmark > rightmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark

def quick_sort(l):
    if len(l) == 0:
        return l
    pivot = l[0]
    pivots = [x for x in l if x == pivot]
    smaller = quick_sort([x for x in l if x < pivot])
    larger = quick_sort([x for x in l if x > pivot])
    return smaller + pivots + larger

Полный пример с напечатанными переменными на этапе разбиения:

def partition(data, p, right):
    print("\n==> Enter partition: p={}, right={}".format(p, right))
    pivot = data[right]
    print("pivot = data[{}] = {}".format(right, pivot))

    i = p - 1  # this is a dangerous line

    for j in range(p, right):
        print("j: {}".format(j))
        if data[j] <= pivot:
            i = i + 1
            print("new i: {}".format(i))
            print("swap: {} <-> {}".format(data[i], data[j]))
            data[i], data[j] = data[j], data[i]

    print("swap2: {} <-> {}".format(data[i + 1], data[right]))
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1


def quick_sort(data, left, right):
    if left < right:
        pivot = partition(data, left, right)
        quick_sort(data, left, pivot - 1)
        quick_sort(data, pivot + 1, right)

data = [2, 8, 7, 1, 3, 5, 6, 4]

print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))

def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don`t have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()

Этот алгоритм не использует рекурсивные функции.

Позвольте Nбыть любой список чисел с len(N) > 0. Установите K = [N]и выполните следующую программу.

Примечание: это стабильный алгоритм сортировки.

def BinaryRip2Singletons(K, S):
    K_L = []
    K_P = [ [K[0][0]] ] 
    K_R = []
    for i in range(1, len(K[0])):
        if   K[0][i] < K[0][0]:
            K_L.append(K[0][i])
        elif K[0][i] > K[0][0]:
            K_R.append(K[0][i])
        else:
            K_P.append( [K[0][i]] )
    K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
    while len(K_new) > 0:
        if len(K_new[0]) == 1:
            S.append(K_new[0][0])
            K_new = K_new[1:]
        else: 
            break
    return K_new, S

N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []

print('K =', K, 'S =', S)
while len(K) > 0:
    K, S = BinaryRip2Singletons(K, S)
    print('K =', K, 'S =', S)

ВЫХОД ПРОГРАММЫ:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]

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

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  left  = []
  right = []
  equal = []
  pivot = arr[-1]
  for num in arr:
    if num < pivot:
      left.append(num)
    elif num == pivot:
      equal.append(num)
    else:
      right.append(num)

  return quicksort(left) + equal + quicksort(right)