Szybkie sortowanie w Pythonie

94

Jestem zupełnie nowy w Pythonie i próbuję zaimplementować w nim quicksort. Czy ktoś mógłby mi pomóc w uzupełnieniu kodu?

Nie wiem, jak połączyć te trzy tablice i je wydrukować.

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
źródło
Aby połączyć listy, możesz użyć operatora plus my_list = list1 + list2 + .... Lub rozpakuj listy do nowej listymy_list = [*list1, *list2]
Mark Mishyn

Odpowiedzi:

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
Brionius
źródło
8
Możesz także zamienić 2 ifsekundy w pętli for z elifi elseuniknąć niepotrzebnych porównań
SlimPDX.
13
To brzmi jak sortowanie przez scalanie, a nie sortowanie szybkie
Emad Mokhtar
47
W rzeczywistości jest to najlepszy i najbardziej czytelny kod Pythona, jaki znalazłem do szybkiego sortowania w dowolnym miejscu . Brak indeksów, brak funkcji pomocniczych jasno pokazuje istotę algorytmu (dziel i rządź). (Domyślna wartość tablicy jest raczej niepotrzebna)
cmantas
20
@jsmedmar zajmie więcej pamięci niż wersja lokalna, zobacz odpowiedź suquant, aby uzyskać szybkie sortowanie w miejscu.
John
15
Bardzo czytelne, ale czy nie jest to sprzeczne z celem szybkiego sortowania, ponieważ nie zapewnia sortowania „na miejscu”? @RasmiRanjanNayak sort tutaj jest funkcją zdefiniowaną przez użytkownika (jest to wywołanie rekurencyjne), a nie jakąkolwiek funkcją wbudowaną.
Maksood
161

Szybkie sortowanie bez dodatkowej pamięci (na miejscu)

Stosowanie:

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
źródło
23
Powinna to być wybrana odpowiedź, ponieważ quicksort jest często wybieranym algorytmem (np. Zamiast sortowania przez scalanie), ponieważ sortuje w miejscu (i nadal daje O (nlogn) runtime).
BoltzmannBrain
3
if end is None:będzie sprawdzany wiele razy i tylko raz True. Powinieneś umieścić to w funkcji opakowującej, aby była wywoływana tylko raz.
Gillespie
Ackchyically, bruhs, @mksteve ma rację, a ta linia jest nieprawidłowa. Dodatkowo array[pivot], array[begin] = array[begin], array[pivot]należy wymienić beginz end.
Ryan J McCall
2
Chociaż w miejscu jest dobre, jest powolne i powoduje błędy ze względu na osiągnięcie maksymalnej głębokości rekurencji, gdy jest dużo elementów. patrz repl.it/@almenon/quicksorts?language=python3
Almenon
@mksteve i Ryan, przetestowałem te zmiany i to zrywa sortowanie
aljgom
68

Jest jeszcze jedna zwięzła i piękna wersja

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!!!

Pozwólcie, że wyjaśnię powyższe kody dla szczegółów

  1. wybierz pierwszy element tablicy arr[0]jako przestawny

    [arr[0]]

  2. qsort te elementy tablicy, które są mniejsze niż obrót z List Comprehension

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

  3. qsort te elementy tablicy, które są większe niż pivot with List Comprehension

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

zangw
źródło
15
@zangw Możliwe przyczyny negatywnego głosu: 1) Kwadratowe środowisko uruchomieniowe na już posortowanych lub odwróconych tablicach 2) Rozwiązanie nie jest na miejscu. Dlatego straszna realizacja, przepraszam.
alisianoi
16
w ogóle nieczytelny, czy naprawdę próbujesz zminimalizować liczbę wierszy? Kod jest interpretowany przez maszyny, ale rozumiany przez ludzi.
jsmedmar
4
@AlfredoGallegos, sedno szybkiego sortowania polega na tym, że dzieje się to na miejscu, równie dobrze możesz zaimplementować scalanie-sortowanie, jeśli zamierzasz to zrobić.
Padraic Cunningham,
14
Czy te komentarze są prawdziwe? Jeśli chcesz wydajności, używaj sorted, jest to wyraźnie w celach edukacyjnych. Jest czytelny, bardziej czytelny niż przyjęta odpowiedź.
Nobilis
4
FWIW, pomyślałem, że to najbardziej czytelna implementacja z nich wszystkich. Pokazuje rekurencyjną strukturę algorytmu lepiej niż jakakolwiek inna odpowiedź. Oczywiście wydajność nie będzie zbyt dobra.
SolveIt
36

Ta odpowiedź to szybkie sortowanie w miejscu dla Python 2.x. Moja odpowiedź to interpretacja rozwiązania lokalnego z Rosetta Code, które działa Python 3również w przypadku:

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)

A jeśli chcesz zrezygnować z własności lokalnej, poniżej znajduje się kolejna wersja, która lepiej ilustruje podstawowe idee związane z quicksort. Oprócz czytelności, jego inną zaletą jest to, że jest stabilny (równe elementy pojawiają się na posortowanej liście w tej samej kolejności, w jakiej miały na liście niesortowanej). Ta właściwość stabilności nie zachowuje się w przypadku implementacji lokalnej, która jest mniej wymagająca pamięci, przedstawiona powyżej.

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
źródło
Dzięki za udostępnienie tego rozwiązania. Czy możesz nam pomóc zrozumieć złożoność czasową? Widzę, że rekurencja wywoła to 15 razy. Z tych 8 to prawidłowe wywołania funkcji. Czy to oznacza, że ​​złożoność czasowa wynosi O (n) dla pierwszego rozwiązania, a złożoność przestrzeni wynosi O (1) jako sortowanie na miejscu?
ForeverLearner
@Tammy, wygląda na to, że źle zrozumiałeś notację duże-O. Co więcej, tak naprawdę nie rozumiem twojego pytania. Czy mógłbyś zapytać o to osobno? Wreszcie, Quicksort jako algorytm działa w czasie O (n logn) i O (n) przestrzeni.
alisianoi
3
Mój błąd. Dlaczego do licha liczyłem rekurencje? :-) Cóż, 15 rekurencji to [1 wywołanie (poziom 0) + 2 wywołanie (partycja na poziomie 1) + 4 wywołanie (partycja na poziomie 2) + 8 wywołanie (partycja na poziomie 3 lub węzły liści). Więc nadal mamy wysokość jako (lg8 + 1) = lgn. Całkowite obliczenia na każdym poziomie dotyczą c1 (jakiś koszt) * n. Stąd O (n lgn). Złożoność przestrzeni, dla jednej wymiany na miejscu = O (1). Stąd dla n elementów = O (n). Dzięki za wskazówkę.
ForeverLearner
3
to zdecydowanie najlepszy szybki sortownik Pythona w Internecie i smutno jest widzieć go pochowany pod tak wieloma rozwiązaniami kosmicznymi O (n) :(
Sasha Kondrashov
Dzięki za miłe słowa @Timofey. Możesz rzucić
alisianoi
23

Szybkie sortowanie w Pythonie

W prawdziwym życiu powinniśmy zawsze używać wbudowanego sortowania udostępnianego przez Pythona. Jednak zrozumienie algorytmu quicksort jest pouczające.

Moim celem jest takie rozbicie tematu, aby był on łatwy do zrozumienia i odtworzenia przez czytelnika bez konieczności powracania do materiałów referencyjnych.

Algorytm szybkiego sortowania jest zasadniczo następujący:

  1. Wybierz obrotowy punkt danych.
  2. Przenieś wszystkie punkty danych poniżej (poniżej) obrotu do pozycji poniżej osi - przesuń te większe lub równe (powyżej) obrotu do pozycji nad nim.
  3. Zastosuj algorytm do obszarów powyżej i poniżej osi obrotu

Jeśli dane są rozmieszczone losowo, wybranie pierwszego punktu danych jako osi obrotu jest równoważne z wyborem losowym.

Czytelny przykład:

Najpierw spójrzmy na czytelny przykład, w którym zastosowano komentarze i nazwy zmiennych, aby wskazać wartości pośrednie:

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

Aby powtórzyć pokazany tutaj algorytm i kod - przenosimy wartości powyżej osi w prawo, a wartości poniżej osi w lewo, a następnie przekazujemy te partycje do tej samej funkcji w celu dalszego sortowania.

Grał w golfa:

Można grać w golfa do 88 znaków:

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

Aby zobaczyć, jak to osiągnąć, weźmy najpierw nasz czytelny przykład, usuń komentarze i dokumenty, a następnie znajdź punkt zwrotny w miejscu:

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

Teraz znajdź poniżej i powyżej, na miejscu:

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

Teraz, wiedząc, że andzwraca poprzedni element, jeśli jest fałszywy, w przeciwnym razie, jeśli jest prawdziwy, ocenia i zwraca następujący element, mamy:

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

Ponieważ lambdy zwracają pojedyncze wyrażenie, a my uprościliśmy się do jednego wyrażenia (nawet jeśli staje się ono bardziej nieczytelne), możemy teraz użyć lambdy:

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

Aby sprowadzić się do naszego przykładu, skróć nazwy funkcji i zmiennych do jednej litery oraz wyeliminuj białe znaki, które nie są wymagane.

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

Zauważ, że ta lambda, podobnie jak większość golfistów kodowych, jest raczej złym stylem.

Lokalne szybkie sortowanie przy użyciu schematu partycjonowania Hoare

Wcześniejsze wdrożenie tworzy wiele niepotrzebnych dodatkowych list. Jeśli możemy to zrobić na miejscu, unikniemy marnowania miejsca.

Poniższa implementacja używa schematu partycjonowania Hoare, o którym możesz przeczytać więcej na Wikipedii (ale najwyraźniej usunęliśmy do 4 zbędnych obliczeń na partition()wywołanie, używając semantyki while-loop zamiast do-while i przenosząc zwężające kroki na koniec zewnętrzna pętla 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

Nie jestem pewien, czy przetestowałem go wystarczająco dokładnie:

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]

Wniosek

Ten algorytm jest często nauczany na kursach informatycznych i proszony o udział w rozmowach kwalifikacyjnych. Pomaga nam myśleć o rekurencji oraz dziel i rządź.

Szybkie sortowanie nie jest zbyt praktyczne w Pythonie, ponieważ nasz wbudowany algorytm sortowania czasu jest dość wydajny i mamy ograniczenia rekursji. Spodziewalibyśmy się sortowania list na miejscu za pomocą list.sortlub tworzenia nowych posortowanych list za pomocą sorted- obie przyjmują argument keyi reverse.

Aaron Hall
źródło
Twoja partitionfunkcja wydają się nie działać poprawnie: partition([5,4,3,2,1], 0, 4). Oczekiwany indeks zwrotu to 4, podczas gdy zwraca 3.
matino
@matino Skąd się wzięło to oczekiwanie? Wydaje mi się, że uprościłem algorytm (jak stwierdzono na Wikipedii podczas pisania tej odpowiedzi), chociaż mogę się mylić lub być może mniej wydajnie. Gdybyś mógł znaleźć przypadek testowy, dla którego cała funkcja quicksort zawodzi, byłoby to pomocne.
Aaron Hall
@AaronHall, kiedy wybrałem pivot = a_list [high], ale po prostu nie potrafię zrozumieć, jak to działa. Możesz pomóc ?
Qiulang
@matino Miałem to samo zamieszanie! Funkcja podziału jest w porządku, niezmiennik, który spełnia, jest słabszy niż to, czego się spodziewasz - nie musi znajdować dokładnego miejsca, które oddziela lewą i prawą stronę od mniejszych i większych niż oś obrotu. Gwarantuje tylko nietrywialną partycję i że wszystkie lewe zwrócone indeksy są mniejsze niż prawa zwróconego indeksu.
Dror Speiser
21

Istnieje już wiele odpowiedzi na to pytanie, ale myślę, że to podejście jest najbardziej czystą implementacją:

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

Możesz oczywiście pominąć przechowywanie wszystkiego w zmiennych i od razu je zwrócić w ten sposób:

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]])
Sebastian Dahlgren
źródło
11
NA!)? czy to jest „slowSort”?
Scott 混合 理论
3
Uważam, że w pierwszym przykładzie kodu powinien on być „mniejszy” i „większy” zamiast „[mniejszy]” i „[większy]” - w przeciwnym razie skończy się na zagnieżdżonych listach zamiast płaskiej.
Alice
@Scott 混合 理论 Wciąż uczę się złożoności czasowej, czy możesz wyjaśnić, dlaczego taka implementacja jest O(N!)? Zakładając zagnieżdżoną listę [lesser]i [greater]literówki, czy nie byłaby to średnia, O(3N logN)która zmniejszyłaby się do oczekiwanej średniej O(N logN)? To prawda, 3 kompozycje z listy wykonują niepotrzebną pracę ...
Chrispy,
@Chrispy co jeśli posortujesz odwróconą listę zamówień, na przykład 5,4,3,2,1
Scott 混合 理论
@Scott 混合 理论 masz rację, że czas wykonywania najgorszego przypadku szybkiego sortowania jest wolny Θ (n ^ 2), ale zgodnie z „wprowadzeniem do algorytmu” średni czas wykonywania przypadków wynosi Θ (n lg n). Co ważniejsze, szybkie sortowanie generalnie przewyższa sortowanie na stosie w praktyce
Lungang Fang
6

podejście funkcjonalne:

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)
akarca
źródło
lista jest zarezerwowana w Pythonie 3. zobacz zmodyfikowaną wersję swojego kodu tutaj: gist.github.com/kunthar/9d8962e1438e93f50dc6dd94d503af3d
Kunthar
akarca i @Kunthar Oba te rozwiązania w python2 lub python3 będą usuwać element z listy za każdym razem, gdy zostanie uruchomiony, niszcząc listę. Oto poprawiona wersja: gist.github.com/joshuatvernon/634e0d912401899af0fdc4e23c94192b
joshuatvernon
4

podejście do programowania funkcjonalnego

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]
Arnaldo P. Figueira Figueira
źródło
4

Łatwa implementacja dzięki grokkingowym algorytmom

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)
Alice
źródło
3

Myślę, że obie odpowiedzi tutaj działają dobrze dla podanej listy (która odpowiada na oryginalne pytanie), ale zepsują się, jeśli zostanie przekazana tablica zawierająca nieunikalne wartości. Więc dla kompletności wskazałbym tylko mały błąd w każdym z nich i wyjaśnił, jak je naprawić.

Na przykład próba posortowania następującej tablicy [12,4,5,6,7,3,1,15,1] (Zauważ, że 1 pojawia się dwa razy) z algorytmem Brioniusa .. w pewnym momencie zakończy się mniejszą tablicą i równą tablicę z parą wartości (1,1), których nie można rozdzielić w następnej iteracji i len ()> 1 ... w ten sposób otrzymasz nieskończoną pętlę

Możesz to naprawić zwracając tablicę jeśli less jest puste lub lepiej nie wywołując sortowania w swojej równej tablicy, jak w zangw answer

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

Bardziej wyszukane rozwiązanie również się psuje, ale z innego powodu brakuje w nim klauzuli return w wierszu rekursji, co w pewnym momencie spowoduje zwrócenie None i próbę dołączenia go do listy ....

Aby to naprawić, po prostu dodaj powrót do tej linii

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
źródło
Nawiasem mówiąc, zwięzła wersja ma mniejszą wydajność niż długa, ponieważ wykonuje iterację tablicy dwa razy do w składanych listach.
FedeN
3

To jest wersja quicksort używająca schematu partycji Hoare i z mniejszą liczbą wymian i zmiennych lokalnych

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)
Madu Alikor
źródło
3

Partycja - podziel tablicę za pomocą obrotu, w którym mniejsze elementy przesuwają się w lewo, a większe w prawo lub odwrotnie. Przestawienie może być losowym elementem z tablicy. Aby stworzyć ten algorytm, musimy wiedzieć, co jest indeksem początkowym i końcowym tablicy oraz gdzie znajduje się punkt obrotu. Następnie ustaw dwa pomocnicze wskaźniki L, R.

Mamy więc użytkownika tablicy [..., begin, ..., end, ...]

Pozycja początkowa wskaźników L i R
[..., begin, next, ..., end, ...]
     R L

while L <end
  1. Jeśli użytkownik [pivot]> użytkownik [L] to przesuń R o jeden i zamień użytkownika [R] z użytkownikiem [L]
  2. przesuń L o jeden

Po chwili zamień użytkownika [R] na użytkownika [pivot]

Szybkie sortowanie - używaj algorytmu partycjonowania, dopóki każda następna część podziału według obrotu będzie miała indeks początkowy większy lub równy indeksowi końcowemu.

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)
Grzegorz Eleryk
źródło
proszę wyjaśnij swój kod / dodatki, aby OP i przyszłe widoki mogły przynieść większe korzyści.
Omar Einea
2

Lub jeśli wolisz jednolinijkowy tekst, który ilustruje również Pythonowy odpowiednik waragów C / C ++, wyrażeń lambda i wyrażeń 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])
Bruce Lucas
źródło
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
źródło
2

Wiem, że wiele osób odpowiedziało poprawnie na to pytanie i lubiłem je czytać. Moja odpowiedź jest prawie taka sama jak zangw, ale myślę, że poprzedni współautorzy nie wykonali dobrej roboty, wyjaśniając wizualnie, jak to naprawdę działa ... więc oto moja próba pomocy innym, którzy mogą odwiedzić to pytanie / odpowiedzi w przyszłości na temat proste rozwiązanie do implementacji quicksort.

Jak to działa ?

  1. Zasadniczo wybieramy pierwszy element jako nasz punkt zwrotny z naszej listy, a następnie tworzymy dwie listy podrzędne.
  2. Nasza pierwsza podlista zawiera pozycje mniejsze niż przestawne
  3. Nasza druga podlista zawiera nasze pozycje, które są większe lub równe pivot
  4. Następnie szybko sortujemy każdy z nich i łączymy je z pierwszą grupą + przestawną + drugą grupą, aby uzyskać ostateczny wynik.

Oto przykład wraz z wizualizacją ... (pivot) 9,11,2,0

średnia: n log z n

gorszy przypadek: n ^ 2

wprowadź opis obrazu tutaj

Kod:

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 (quicksort (items))

grepit
źródło
2

Algorytm zawiera dwie granice, z których jedna ma elementy mniejsze niż oś (śledzona przez indeks „j”), a druga ma elementy większe niż oś (śledzona przez indeks „i”).

W każdej iteracji nowy element jest przetwarzany poprzez zwiększenie wartości j.

Niezmienny:-

  1. wszystkie elementy między pivot i i są mniejsze niż pivot i
  2. wszystkie elementy między i i j są większe niż oś.

Jeśli niezmiennik zostanie naruszony, zamieniane są i-ty i j-ty elementy, a i jest inkrementowane.

Po przetworzeniu wszystkich elementów i podzieleniu wszystkiego po przestawieniu na partycje element przestawny jest zamieniany na ostatni element mniejszy od niego.

Element obrotowy będzie teraz znajdował się na właściwym miejscu w sekwencji. Elementy przed nim będą mniejsze od niego, a te po nim będą większe od niego i będą nieposortowane.

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

Wybór punktu obrotu

„Dobry” obrót spowoduje powstanie dwóch pod-sekwencji o mniej więcej tej samej wielkości. Z deterministycznego punktu widzenia element obrotowy można wybrać w sposób naiwny lub przez obliczenie mediany sekwencji.

Naiwna implementacja wyboru pivota będzie pierwszym lub ostatnim elementem. W tym przypadku najgorszym rozwiązaniem będzie sytuacja, w której sekwencja wejściowa jest już posortowana lub odwrotnie posortowana, ponieważ jeden z podciągów będzie pusty, co spowoduje usunięcie tylko jednego elementu na wywołanie rekurencyjne.

Idealnie zbalansowany podział uzyskuje się, gdy punkt obrotu jest środkowym elementem sekwencji. Istnieje równa liczba elementów większa od niej i mniejsza od niej. Takie podejście gwarantuje lepszy całkowity czas działania, ale jest znacznie bardziej czasochłonne.

Niedeterministycznym / losowym sposobem wyboru punktu obrotu byłoby wybranie elementu równomiernie i losowo. Jest to proste i lekkie podejście, które zminimalizuje najgorszy scenariusz, a także doprowadzi do z grubsza zbalansowanego podziału. Zapewni to również równowagę między naiwnym podejściem a medianą wyboru punktu obrotu.


źródło
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)
Mina
źródło
Chociaż ten kod może stanowić rozwiązanie problemu, zdecydowanie zaleca się podanie dodatkowego kontekstu wyjaśniającego, dlaczego i / lub jak ten kod odpowiada na pytanie. Odpowiedzi zawierające tylko kod zazwyczaj stają się bezużyteczne na dłuższą metę, ponieważ przyszli widzowie doświadczający podobnych problemów nie są w stanie zrozumieć przyczyny rozwiązania.
pałac
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
źródło
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
Amy
źródło
1
Dołącz wyjaśnienie, co robi Twój kod i jak odpowiada na pytanie. Szczególnie, jak to się ma do kodu zamieszczonego w pytaniu. Odpowiedź powinna dać OP i przyszłym odwiedzającym wskazówki, jak debugować i rozwiązać ich problem. Wskazanie, jaka jest idea kodu, bardzo pomaga w zrozumieniu problemu i zastosowaniu lub zmodyfikowaniu rozwiązania. Stack Overflow nie jest usługą pisania kodu, to miejsce do nauczania i uczenia się.
Palec
1

„Prawdziwa” implementacja na miejscu [algorytmy 8.9, 8.11 z książki Algorithm Design and Applications autorstwa Michaela T. Goodricha i Roberto Tamassii]:

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()
anask
źródło
1

Algorytm składa się z 4 prostych kroków:

  1. Podziel tablicę na 3 różne części: left, pivot i right, gdzie pivot będzie miał tylko jeden element. Wybierzmy ten element przestawny jako pierwszy element tablicy
  2. Dołącz elementy do odpowiedniej części, porównując je z elementem obrotowym. (wyjaśnienie w komentarzach)
  3. Powtarzaj ten algorytm, aż wszystkie elementy w tablicy zostaną posortowane
  4. Na koniec dołącz do lewej + pivot + prawej części

Kod algorytmu w Pythonie:

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

Kontynuuj ten algorytm rekurencyjnie z lewą i prawą częścią.

Mamta Kanvinde
źródło
1

Kolejna implementacja quicksort:

# 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)
Gillespie
źródło
1

Wersja Python 3.x : funkcjonalny styl wykorzystujący operatormoduł, głównie w celu poprawy czytelności.

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

i jest testowany jako

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])
równowaga życiowa
źródło
Ładne (jeśli chodzi o nieudokumentowany kod ), choć podobne do odpowiedzi Acarca , Arnaldo P. Figueira Figueira i Birgera z minionych lat. Nie jestem pewien, czy to odpowiedź, gdy czyta się pytanie … complete my code?. Używanie lambdado definiowania sublist()nie wygląda na absolutnie konieczne.
siwobrody
@greybeard Właściwie, kod Arnaldo nie został skompilowany w Pythonie 3. Poza tym, jak można sublistzdefiniować tylko za pomocą filter? Czy to w ogóle jest możliwe?
saldo ratunkowe
1
(Komentarz tymczasowy: myślenie o def- nie zacząłem jeszcze majstrować, gdy próbuję dowiedzieć się, czy istnieje bardziej skuteczny sposób na „dystrybucję” elementów iterowalnych do oddzielnych list (lub alternatywnie jednej listy z jedną ” kategoria "po drugiej).)
siwobrody
1

Oto prosta implementacja: -

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
źródło
0
  1. Najpierw deklarujemy pierwszą wartość w tablicy jako pivot_value, a także ustawiamy lewy i prawy znacznik
  2. Tworzymy pierwszą pętlę while, ta pętla while jest po to, aby nakazać procesowi partycjonowania ponowne uruchomienie, jeśli nie spełnia niezbędnego warunku
  3. następnie zastosujemy proces partycji
  4. po uruchomieniu obu procesów partycji sprawdzamy, czy spełnia on właściwy warunek. Jeśli tak, oznaczamy to jako wykonane, jeśli nie, zamieniamy lewą i prawą wartość i stosujemy ponownie
  5. Po zakończeniu zamień lewą i prawą wartość i zwróć split_point

Załączam kod poniżej! To szybkie sortowanie jest doskonałym narzędziem do nauki ze względu na lokalizację wartości przestawnej . Ponieważ znajduje się w stałym miejscu, możesz przejść przez niego wiele razy i naprawdę zrozumieć, jak to wszystko działa. W praktyce najlepiej jest randomizować pivot, aby uniknąć czasu wykonywania 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
DanHabib
źródło
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
feroz
źródło
18 innych odpowiedzi, z których ponad połowa odpowiada pierwotnemu pytaniu OP: „jak połączyć trzy tablice”. Czy twoja odpowiedź dodaje coś nowego?
Teepeemm
0

Pełny przykład z wypisywanymi zmiennymi w kroku podziału:

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))
Andrei Sura
źródło
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()
Igor Mansurov
źródło
1
proszę o wyjaśnienie
Rai
0

Ten algorytm nie używa funkcji rekurencyjnych.

Niech Nbędzie dowolna lista liczb z len(N) > 0. Ustaw K = [N]i wykonaj następujący program.

Uwaga: jest to stabilny algorytm sortowania.

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)

WYJŚCIE PROGRAMU:

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
źródło
0

Prawdopodobnie jest to tylko kwestia preferencji, ale lubię dodawać walidację do górnej części moich funkcji.

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)
Robo Rick
źródło