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

94

Я совершенно не знаком с 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)
user2687481
источник
Для объединения списков можно использовать оператор «плюс» my_list = list1 + list2 + .... Или распаковать списки в новый списокmy_list = [*list1, *list2]
Марк Мишин

Ответы:

255
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
Бриониус
источник
8
Кроме того, можно поменять на 2 - й ifсек в течение цикла с elifи elseделать , чтобы избежать ненужных сравнений
SlimPDX
13
Это похоже на сортировку слиянием, а не на быструю сортировку
Эмад Мохтар
47
На самом деле это лучший и самый читаемый код Python, который я нашел для быстрой сортировки где угодно . Никаких индексов, никаких вспомогательных функций, ясно показывает суть алгоритма (разделяй и властвуй). (Значение по умолчанию для массива не обязательно)
cmantas
20
@jsmedmar он будет использовать больше памяти, чем версия на месте, см. ответ suquant для быстрой сортировки на месте.
Джон
15
Очень удобочитаемо, но разве это не противоречит цели быстрой сортировки, поскольку она не позволяет добиться сортировки «на месте»? @RasmiRanjanNayak sort - это пользовательская функция (рекурсивный вызов), а не встроенная функция.
Maksood 09
161

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

Применение:

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)
Suquant
источник
23
Это должен быть выбранный ответ, так как быстрая сортировка часто является предпочтительным алгоритмом (например, сортировкой слиянием), потому что она сортирует на месте (и по-прежнему дает время выполнения O (nlogn)).
BoltzmannBrain
3
if end is None:будет проверяться много раз, и только один раз True. Вы должны поместить это в функцию-оболочку, чтобы она вызывалась только один раз.
Гиллеспи
На самом деле, братва, @mksteve права, а эта строка неверна. Кроме того, array[pivot], array[begin] = array[begin], array[pivot]следует заменить beginна end.
Ryan J McCall
2
Хотя на месте это хорошо, это медленно и выдает ошибки из-за достижения максимальной глубины рекурсии при большом количестве элементов. см. repl.it/@almenon/quicksorts?language=python3
Almenon,
@mksteve и Райан, я протестировал эти изменения, и это нарушает сортировку
aljgom
68

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

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]])

Zangw
источник
15
@zangw возможные причины отрицательного голоса: 1) Квадратичное время выполнения для уже отсортированных или перевернутых массивов 2) Решение не на месте. Поэтому ужасная реализация, извините.
alisianoi
16
вообще не читается, вы действительно пытаетесь минимизировать количество строк? Код интерпретируется машинами, но понимается людьми.
jsmedmar
4
@AlfredoGallegos, весь смысл быстрой сортировки в том, что она происходит на месте, вы также можете реализовать сортировку слиянием, если собираетесь это делать.
Падраик Каннингем
14
Это настоящий комментарий? Если вам нужна производительность, используйте sorted, это явно в образовательных целях. И он читабельнее, чем принятый ответ.
Нобилис
4
FWIW, я подумал, что это самая читаемая реализация из всех. Он показывает рекурсивную структуру алгоритма лучше, чем любой другой ответ. Конечно, производительность не будет слишком высокой.
SolveIt
37

Этот ответ представляет собой быструю сортировку для файлов 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
Alisianoi
источник
Спасибо, что поделились этим решением. Не могли бы вы помочь нам понять временную сложность? Я вижу, что рекурсия вызовет его 15 раз. Из этих 8 действительных вызовов функции. Означает ли это, что временная сложность составляет O (n) для первого решения, а пространственная сложность - O (1) как его сортировка на месте?
ForeverLearner
@Tammy, похоже, вы неправильно поняли нотацию большого O. Более того, я не очень понимаю ваш вопрос. Не могли бы вы задать его как отдельный вопрос? Наконец, Quicksort как алгоритм работает за время O (n logn) и пространство O (n).
alisianoi
3
Моя вина. Зачем я считал рекурсии ?? :-) Итак, 15 рекурсий - это [1 вызов (уровень 0) + 2 вызова (раздел уровня 1) + 4 вызова (раздел уровня 2) + 8 вызовов (раздел уровня 3 или узлы Leaf). Итак, у нас все еще есть высота как (lg8 + 1) = lgn. Общее вычисление на каждом уровне для c1 (некоторая стоимость) * n. Следовательно, O (n lgn). Сложность места для одного обмена на месте = O (1). Следовательно, для n элементов = O (n). Спасибо за указатель.
ForeverLearner
3
это, несомненно, лучшая быстрая сортировка Python в Интернете, и грустно видеть, что она похоронена под таким количеством космических решений O (n) :(
Саша Кондрашов
Спасибо за добрые слова @Timofey. Вы можете захотеть взглянуть на мои алгоритмы репо, то есть и другие версии сортов, алгоритмов на графах, и т.д. и т.п. github.com/alisianoi/algos-py
alisianoi
23

Быстрая сортировка с 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аргумент.

Аарон Холл
источник
Ваша partitionфункция , похоже , не правильно работать: partition([5,4,3,2,1], 0, 4). Ожидаемый индекс доходности 4, а возврат 3.
матино
@matino Откуда пришло такое ожидание? Я считаю, что упростил алгоритм (как указано в Википедии при написании этого ответа), хотя я мог ошибаться или, возможно, менее эффективно. Если бы вы могли найти тестовый пример, для которого вся функция быстрой сортировки не работает, это было бы полезно.
Аарон Холл
@AaronHall, когда я выбрал pivot = a_list [high], но я просто не могу понять, как заставить его работать тогда. Вы можете помочь ?
Цюлан,
@matino У меня такая же путаница! Статистическая сумма в порядке, инвариант, которому она удовлетворяет, слабее, чем вы ожидаете - ей не нужно находить точное место, которое разделяет левую и правую части на меньшие и большие, чем точка поворота. Это гарантирует только нетривиальную секцию и то, что все слева от возвращаемого индекса меньше, чем справа от возвращаемого индекса.
Dror Speiser
21

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

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]])
Себастьян Дальгрен
источник
11
НА!)? это «медленная сортировка»?
Скотт 混合 理论
3
Я считаю, что в первом примере кода он должен быть «меньше» и «больше» вместо «[меньше]» и «[больше]» - иначе вы получите вложенные списки вместо плоского.
Алиса
@Scott 混合 理论 Я все еще изучаю временную сложность, не могли бы вы объяснить, почему эта реализация O(N!)? Предполагая, что список вложен [lesser]и [greater]содержит опечатки, не будет ли среднее значение, O(3N logN)которое снизится до ожидаемого среднего O(N logN)? Конечно, 3
составителя
@Chrispy, что, если вы отсортируете список в перевернутом порядке, например 5,4,3,2,1
Скотт 混合 理论
@Scott 混合 理论 вы правы, что в худшем случае время выполнения быстрой сортировки медленное Θ (n ^ 2), но, согласно «введению в алгоритм», среднее время выполнения составляет Θ (n lg n). И, что более важно, быстрая сортировка на практике обычно превосходит сортировку кучей
Lungang Fang
6

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

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)
акарка
источник
список зарезервирован в python 3. см. измененную версию вашего кода здесь: gist.github.com/kunthar/9d8962e1438e93f50dc6dd94d503af3d
Kunthar
akarca и @Kunthar Оба этих решения в python2 или python3 будут выталкивать элемент из списка при каждом запуске, тем самым уничтожая список. Вот фиксированная версия: gist.github.com/joshuatvernon/634e0d912401899af0fdc4e23c94192b
joshuatvernon
4

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

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]
Арнальдо П. Фигейра Фигейра
источник
4

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

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)
Алиса
источник
3

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

Например, попытка отсортировать следующий массив [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]])
FedeN
источник
Между прочим, краткая версия имеет меньшую производительность, чем длинная, поскольку она дважды повторяет массив в пониманиях списка.
FedeN
3

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

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)
Маду Аликор
источник
3

Разделение - разделение массива поворотной точкой, при которой меньшие элементы перемещаются влево, а большие элементы - вправо или наоборот. Поворот может быть случайным элементом из массива. Чтобы создать этот алгоритм, нам нужно знать, что такое начальный и конечный индекс массива и где находится точка поворота. Затем установите два вспомогательных указателя 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)
Гжегож Елерик
источник
пожалуйста, объясните свой код / ​​дополнения, чтобы OP и будущие представления могли принести больше пользы.
Омар Эйнеа 04
2

Или, если вы предпочитаете однострочник, который также иллюстрирует 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])
Брюс Лукас
источник
2
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)
MoeChen
источник
2

Я знаю, что многие люди правильно ответили на этот вопрос, и мне понравилось их читать. Мой ответ почти такой же, как и 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 (быстрая сортировка (элементов))

grepit
источник
2

Алгоритм содержит две границы: одна имеет элементы меньше, чем точка поворота (отслеживается индексом «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))

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

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

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

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

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


источник
2
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)
Мина
источник
Хотя этот код может предоставить решение проблемы, настоятельно рекомендуется предоставить дополнительный контекст относительно того, почему и / или как этот код отвечает на вопрос. Ответы только на код обычно становятся бесполезными в долгосрочной перспективе, потому что будущие зрители, сталкивающиеся с аналогичными проблемами, не могут понять причину решения.
палата
1
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 []
Dapangmao
источник
1
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
Эми
источник
1
Пожалуйста, включите объяснение того, что делает ваш код и как он отвечает на вопрос. Особенно как это связано с кодом, опубликованным в вопросе. Ответ должен дать OP и будущим посетителям руководство по отладке и устранению их проблемы. Указание на идею, лежащую в основе вашего кода, очень помогает понять проблему и применить или изменить ваше решение. Stack Overflow - это не сервис для написания кода, это место для преподавания и обучения.
Palec 06
1

«Настоящая» реализация на месте [алгоритмы 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()
анаск
источник
1

Алгоритм состоит из 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])

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

Мамта Канвинде
источник
1

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

# 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)
Гиллеспи
источник
1

Для версии 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])
жизненный баланс
источник
Приятно (если говорить о недокументированном коде ), если они похожи на ответы acarca , Арнальдо П. Фигейра Фигейра и Биргера из прошлых лет. Не уверен, что это ответ, когда читают вопрос … complete my code?. Использование lambdato define sublist()не выглядит строго необходимым.
глиняный кувшин
@greybeard На самом деле, код Арнальдо не компилировался в Python 3. Кроме того, как можно sublistопределить только с помощью filter? Это вообще возможно?
lifebalance
1
(Временный комментарий: thinkin 'of def- пока не начал возиться, поскольку я пытаюсь выяснить, есть ли более эффективный способ «распределить» элементы итерации по отдельным спискам (или, альтернативно, один список с одним » категория»после того, как другой)).
пожилой человек
1

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

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]))
abhishek4996
источник
0
  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
Дан Хабиб
источник
0
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
Фероз
источник
18 других ответов, более половины из которых отвечают на исходный вопрос OP «как объединить три массива». Ваш ответ добавляет что-нибудь новое?
Teepeemm
0

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

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))
Андрей Сура
источник
0
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()
Игорь Мансуров
источник
1
пожалуйста, дайте объяснение
Рай
0

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

Позвольте 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]
CopyPasteIt
источник
0

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

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)
Робо Рик
источник