Szybkie sortowanie bez dodatkowej pamięci (na miejscu)

Użycie:

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)

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ól mi wyjaśnić powyższe kody dla szczegółów

1. Wybierz pierwszy element tablicy arr[0] jako pivot

   [arr[0]]

2. qsort te elementy tablicy, które są mniejsze niż pivot 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 z List Comprehension

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

Jeśli poszukam "implementacja Pythona quicksort" w Google, to pytanie jest pierwszym wynikiem, który się pojawi. Rozumiem, że początkowe pytanie dotyczyło "pomocy w poprawieniu kodu", ale istnieje już wiele odpowiedzi, które ignorują tę prośbę: obecnie druga najczęściej głosowana , horrendalna jednowierszowa z komicznym komentarzem "jesteś zwolniony" i ogólnie wiele implementacji, które nie są na miejscu (tzn. używają dodatkowej pamięci proporcjonalnej do rozmiaru listy wejściowej). to ODPOWIEDŹ zapewnia rozwiązanie w miejscu, ale jest dla python 2.x. Tak więc, poniżej następuje moja interpretacja rozwiązania in-place z kodu Rosetta , które będzie działać dobrze dla python 3 zbyt:

import random

def qsort(l, fst, lst):
    if fst >= lst: return

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

    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j - 1
    qsort(l, fst, j)
    qsort(l, i, lst)

A jeśli chcesz zrezygnować z nieruchomości in-place, poniżej znajduje się kolejna wersja, która lepiej ilustruje podstawowe pomysły quicksort. Oprócz czytelności, jego drugą zaletą jest to, że jest stabilna (równe elementy pojawiają się na posortowanej liście w tej samej kolejności, co kiedyś mieli na liście niesortowanej). Ta właściwość stabilności nie działa w przypadku mniej wymagającej pamięci implementacji in-place przedstawionej powyżej.

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

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

Odpowiedzi na to jest już wiele, ale myślę, że takie 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 zwrócić je od razu w następujący 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]])

Quicksort z Pythonem

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

Moim celem jest rozbicie tematu tak, aby czytelnik mógł go łatwo zrozumieć i odtworzyć bez konieczności powrotu do materiałów referencyjnych.

Algorytm quicksort jest zasadniczo następujący:

1. Wybierz dane przestawne punkt.
2. Przenieś wszystkie punkty danych mniejsze niż (poniżej) Pivota do pozycji poniżej Pivota - przenieś te większe lub równe (powyżej) Pivota do pozycji powyżej niego.
3. Zastosuj algorytm do obszarów powyżej i poniżej Pivota

Jeśli dane są losowo rozmieszczone, wybranie pierwszego punktu danych jako pivot jest równoznaczne z wyborem losowym.

Czytelny przykład:

Najpierw spójrzmy na czytelny przykład, który wykorzystuje komentarze i nazwy zmiennych wskazujące na 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 zrestartować algorytm i kod pokazany tutaj-przenosimy wartości powyżej Pivota w prawo, a wartości poniżej Pivota w lewo, a następnie przekazujemy te partycje do tej samej funkcji, aby zostały dalej posortowane.

Golfed:

To może być 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 się tam dostaniemy, najpierw weź nasz czytelny przykład, usuń komentarze i docstringi i znajdź pivot in-place:

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, w 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 and zwraca poprzedni element jeśli false, 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]]))

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

I aby zredukować do naszego przykładu, skróć nazwy funkcji i zmiennych do jednego liter, i wyeliminować 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, jak większość code golfa, jest raczej złym stylem.

Poprzednia implementacja tworzy wiele niepotrzebnych dodatkowych list. Jeśli zrobimy to na miejscu, unikniemy marnowania miejsca.

Poniższa implementacja wykorzystuje schemat partycjonowania Hoare, o którym możesz przeczytać więcej na Wikipedii (ale mamy widocznie usunięto do 4 nadmiarowych obliczeń na wywołanie partition(), używając semantyki pętli while zamiast do-while I przesuwając kroki zwężenia na koniec zewnętrznej pętli 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 wiem, 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]

Podsumowanie

Algorytm ten jest często nauczany na kursach informatyki i pytany o rozmowę kwalifikacyjną. Pomaga nam myśleć o rekurencji i dzielić i podbijać.

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)

Aproach programowania funkcyjnego

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]

Myślę, że obie odpowiedzi tutaj działają ok dla podanej listy (która odpowiada na oryginalne pytanie), ale pękną, jeśli tablica zawierająca Nie unikalne wartości zostanie przekazana. Więc dla kompletności, chciałbym po prostu wskazać mały błąd w każdym i wyjaśnić, jak je naprawić.

Na przykład próbuje posortować następującą tablicę [12,4,5,6,7,3,1,15,1] (zauważ, że 1 pojawia się dwa razy) algorytmem Brionius.. w pewnym momencie skończy się z mniej tablica pusta i równa tablica z parą wartości (1,1), których nie można rozdzielić w następnej iteracji i len() > 1...w ten sposób skończysz z nieskończoną pętlą

Możesz to naprawić zwracając tablicę, jeśli less jest puste lub lepiej przez a nie wywołanie sortowania w tablicy równości, jak w zangw odpowiedź

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

Rozwiązanie fancier również się psuje, ale z innej przyczyny brakuje klauzuli return w linii rekurencji, która spowoduje, że w pewnym momencie zwróci None i spróbuje dodać go do listy ....

Aby to naprawić wystarczy dodać 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]])

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

Algorytmy 8.9, 8.11 z książki algorithms Design and Applications autorstwa Michaela T. Goodricha i Roberto Tamassiego:

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

Algorytm ma 4 proste kroki:

1. Podziel tablicę na 3 różne części: lewa, pivot i prawa, gdzie pivot będzie miał tylko jeden element. Wybierzmy ten element pivot jako pierwszy element tablicy
2. dołącza elementy do odpowiedniej części, porównując je z elementem pivot. (wyjaśnienie w komentarzach)
3. Wykonaj rekurencję algorytmu aż wszystkie elementy tablicy zostaną posortowane
4. na koniec połącz lewe + pivot+prawe części

Kod dla algorytm 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ą.

Dla Wersji Python 3.x : Styl funkcjonalny wykorzystujący moduł operator, 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])

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)

partycja - dzielenie tablicy przez pivot, w którym mniejsze elementy przesuwają się w lewo, a większe w prawo lub odwrotnie. Pivot może być elementem losowym z tablicy. Aby wykonać ten algorytm musimy wiedzieć, co jest indeksem początku i końca tablicy oraz gdzie jest pivot. Następnie Ustaw Dwa wskaźniki pomocnicze L, R.

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

Pozycja początkowa L i R pointers
[..., begin, next,..., end,...]
     R L

While L   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 while zamień użytkownika [R] z użytkownikiem [pivot]

szybkie sortowanie - używaj algorytmu partycji, aż każda następna część podziału przez pivot będzie miała indeks begin większy lub równy niż indeks end.

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)

Lub jeśli wolisz jednolinijkowy, który ilustruje również pythonowy odpowiednik C / C++ varags, wyrażenia lambda i wyrażenia 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])

1. najpierw deklarujemy pierwszą wartość w tablicy jako pivot_value i ustawiamy również lewy i prawy znacznik
2. tworzymy pierwszą pętlę while, ta pętla while jest proces partycji uruchomić ponownie, jeśli nie spełnia warunek konieczny
3. następnie stosujemy proces partycji
4. Po uruchomieniu obu procesów partycji sprawdzamy czy spełnia odpowiednie warunki. Jeśli tak, oznaczamy to jako zrobione, jeśli nie zmienimy lewo i prawo wartości i zastosuj je ponownie
5. po jego zakończeniu Przełącz wartości lewo i prawo i zwróć split_point

Dołączam poniższy kod! Ten quicksort jest doskonałym narzędziem do nauki ze względu na położenie wartości pivot . Ponieważ znajduje się w stałym miejscu, możesz przejść przez niego wiele razy i naprawdę dowiedzieć się, jak to wszystko działa. W praktyce najlepiej jest randomizować pivot, aby uniknąć O (N^2) runtime.

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

Pełny przykład z wydrukowanymi zmiennymi w kroku partycji:

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

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)

Jest to wersja quicksort wykorzystująca schemat partycji Hoare i z mniejszą ilością swapów 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)

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

def quick_sort(list):
    if len(list) ==0:
        return []

    return  quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ]  +  quick_sort( filter( lambda item: item > list[0], list))

def quicksort(items):
    if not len(items) > 1:
        return items
    items, pivot = partition(items)
    return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])


def partition(items):
    i = 1
    pivot = 0
    for j in range(1, len(items)):
        if items[j] <= items[pivot]:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i - 1], items[pivot] = items[pivot], items[i - 1]
    return items, i - 1

Inlace sort

def qsort(a, b=0, e=None):
    # partitioning
    def part(a, start, end):
        p = start
        for i in xrange(start+1, end):
            if a[i] < a[p]:
                a[i], a[p+1] = a[p+1], a[i]
                a[p+1], a[p] = a[p], a[p+1]
                p += 1
        return p

    if e is None:
        e = len(a)
    if e-b <= 1: return

    p = part(a, b, e)
    qsort(a, b, p)
    qsort(a, p+1, e)

Bez rekurencji:

deq = collections.deque()
deq.append((b, e))
while len(deq):
    el = deq.pop()
    if el[1] - el[0] > 1:
        p = part(a, el[0], el[1])
        deq.append((el[0], p))
        deq.append((p+1, el[1]))

Zamiast pobierać trzy różne tablice dla mniej równej Większej i następnie łączyć wszystkie spróbuj tradycyjnego pojęcia (metody partycjonowania):

Http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

Jest to bez użycia żadnej wbudowanej funkcji.

Funkcja partycjonowania-

def partitn(alist, left, right):  
 i=left  
 j=right  
 mid=(left+right)/2   

pivot=alist[mid]  
while i <= j:  
    while alist[i] < pivot:  
        i=i+1   

    while alist[j] > pivot:  
        j=j-1   

    if i <= j:  
        temp = alist[i]  
        alist[i] = alist[j]  
        alist[j] = temp  
        i = i + 1   
        j = j - 1   

Zrobię quicksort używając biblioteki numpy. Myślę, że to naprawdę przydatna biblioteka. Zaimplementowali już metodę szybkiego sortowania, ale możesz zaimplementować również metodę niestandardową.

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort

indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)

temp_array = []

for index in index_list:
    temp_array.append( array[index])

array = temp_array

print array #it will show sorted array