Lokalny QuickSort w Pythonie

Question

Musiałem wdrożyć algorytm QuickSort do zadania domowego w wybranym przez siebie języku i wybrałem Python.

Podczas wykładów powiedziano nam, że QuickSort jest wydajny w pamięci, ponieważ działa w miejscu; tj. nie ma żadnych dodatkowych kopii części tablicy wejściowej dla rekurencji.

Z tą myślą próbowałem wdrożyć algorytm QuickSort w Pythonie, ale wkrótce potem zdałem sobie sprawę, że aby napisać elegancki fragment kodu, będę musiał przekazać części tablicy do samej funkcji podczas rekursji. Ponieważ Python tworzy nowe listy za każdym razem, gdy to robię, próbowałem używać Python3 (ponieważ obsługuje on nielokalne słowo kluczowe). Oto mój skomentowany kod.

def quicksort2(array): 
# Create a local copy of array. 
arr = array 

    def sort(start, end): 
     # Base case condition 
     if not start < end: 
      return 

     # Make it known to the inner function that we will work on arr 
     # from the outer definition 
     nonlocal arr 

     i = start + 1 
     j = start + 1 

     # Choosing the pivot as the first element of the working part 
     # part of arr 
     pivot = arr[start] 

     # Start partitioning 
     while j <= end: 
      if arr[j] < pivot: 
       temp = arr[i] 
       arr[i] = arr[j] 
       arr[j] = temp 
       i += 1 
      j += 1 
     temp = arr[start] 
     arr[start] = arr[i - 1] 
     arr[i - 1] = temp 
     # End partitioning 

     # Finally recurse on both partitions 
     sort(start + 0, i - 2) 
     sort(i, end) 
    sort(0, len(array) - 1) 

Teraz nie jestem pewien, czy dobrze wykonałem pracę, czy też czegoś brakuje. Napisałem bardziej Pythonową wersję QuickSorta, ale z pewnością nie działa ona w miejscu, ponieważ utrzymuje powracające części tablicy wejściowej i łączy je.

Moje pytanie brzmi: czy jest to sposób na zrobienie tego w Pythonie? Przeszukałem zarówno Google, jak i SO, ale nie znalazłem prawdziwej implementacji QuickSort w miejscu, więc pomyślałem, że najlepiej będzie zapytać.

Answer 1

pewno nie jest najlepszym sposobem, plus ten słynny algorytm będzie miał dziesiątki doskonałych wdrożeń .. to jest moje, dość łatwe do zrozumienia

def sub_partition(array, start, end, idx_pivot): 

    'returns the position where the pivot winds up' 

    if not (start <= idx_pivot <= end): 
     raise ValueError('idx pivot must be between start and end') 

    array[start], array[idx_pivot] = array[idx_pivot], array[start] 
    pivot = array[start] 
    i = start + 1 
    j = start + 1 

    while j <= end: 
     if array[j] <= pivot: 
      array[j], array[i] = array[i], array[j] 
      i += 1 
     j += 1 

    array[start], array[i - 1] = array[i - 1], array[start] 
    return i - 1 

def quicksort(array, start=0, end=None): 

    if end is None: 
     end = len(array) - 1 

    if end - start < 1: 
     return 

    idx_pivot = random.randint(start, end) 
    i = sub_partition(array, start, end, idx_pivot) 
    #print array, i, idx_pivot 
    quicksort(array, start, i - 1) 
    quicksort(array, i + 1, end) 

Ok pierwszą funkcję oddzielna dla podprogramu partycji. Bierze tablicę, początkowy i końcowy punkt zainteresowania oraz indeks osi obrotu. Ta funkcja powinna być wolna:

Quicksort następnie wywoła podprogram partycji po raz pierwszy w całej tablicy; następnie dzwoni sam w sobie, aby posortować wszystko do pivota i wszystkiego po nim.

zapytać jeśli nie rozumiesz czegoś

Answer 2

zacząłem naukę Pythona ostatnio i po to moja próba realizacji quicksort przy użyciu Pythona. Mam nadzieję, że to jest pomocne. Opinia jest mile widziany :)

#!/usr/bin/python 

Array = [ 3,7,2,8,1,6,8,9,6,9] 

def partition(a, left, right): 

    pivot = left + (right - left)/2 
    a[left],a[pivot] = a[pivot], a[left] # swap 
    pivot = left 
    left += 1 

    while right >= left : 
     while left <= right and a[left] <= a[pivot] : 
      left += 1 
     while left <= right and a[right] > a[pivot] : 
      right -= 1 

     if left <= right: 
      a[left] , a[right] = a[right], a[left] # swap 
      left += 1 
      right -= 1 
     else: 
      break 

    a[pivot], a[right] = a[right] , a[pivot] 

    return right 


def quicksort(array , left,right): 
    if left >= right: 
     return 
    if right - left == 1: 
     if array[right] < array[left]: 
      array[right], array[left] = array[left] , array[right] 
      return   

    pivot = partition(array, left, right) 

    quicksort(array, left, pivot -1) 
    quicksort(array, pivot+1,right)   

def main(): 
    quicksort(Array, 0 , len(Array) -1) 
    print Array 

main() 

Answer 3

Oto, co wymyśliłem. Algorytm jest na miejscu, wygląda ładnie i jest rekurencyjny.

# `a` is the subarray we're working on 
# `p` is the start point in the subarray we're working on 
# `r` is the index of the last element of the subarray we're working on 

def part(a,p,r): 
    k=a[r] #pivot 
    j,q=p,p 
    if p<r: # if the length of the subarray is greater than 0 
     for i in range(p,r+1): 
      if a[i]<=k: 
       t=a[q] 
       a[q]=a[j] 
       a[j]=t 
       if i!=r: 
        q+=1 
       j+=1 
      else: 
       j+=1 
     part(a,p,q-1) # sort the subarray to the left of the pivot 
     part(a,q+1,r) # sort the subarray to the right of the pivot 
    return a 
def quicksort(a): 
    if len(a)>1: 
     return part(a,0,len(a)-1) 
    else: 
     return a 

Answer 4

Oto kolejna realizacja:

def quicksort(alist): 
    if len(alist) <= 1: 
     return alist 
    return part(alist,0,len(alist)-1) 

def part(alist,start,end): 
    pivot = alist[end] 
    border = start 
    if start < end: 
     for i in range(start,end+1): 
      if alist[i] <= pivot: 
       alist[border], alist[i] = alist[i], alist[border] 
       if i != end: 
        border += 1 
     part(alist,start,border-1) 
     part(alist,border+1,end) 
    return alist 

Answer 5

Objaśnienie: Pivot jest zawsze ostatnim elementem w danej tablicy. W moim podejściu śledzę "granicę" między liczbami mniejszymi i większymi niż liczby przestawne. Border to indeks pierwszego numeru w grupie "większych". Na końcu każdej iteracji zamieniamy liczbę pod "obramowaniem" z numerem pivot.

I kod:

def qs(ar, start, end): 
    if (end-start < 1): 
     return 
    if (end-start == 1): 
     if(ar[start] > ar[end]): 
      tmp = ar[start] 
      ar[start] = ar[end] 
      ar[end] = tmp 
     return 
    pivot = ar[end - 1] 
    border_index = start 
    i = start 
    while(i <= end - 1): 
     if (ar[i] < pivot): 
      if i > border_index: 
       tmp = ar[i] 
       ar[i] = ar[border_index] 
       ar[border_index] = tmp 
      border_index += 1 
     i+=1 
    ar[end-1] = ar[border_index] 
    ar[border_index] = pivot 
    qs(ar, start, border_index) 
    qs(ar, border_index + 1, end) 

qs(ar, 0, n)