Fehler in meinem schnellen Sortieralgorithmus Implementierung

Question

Kürzlich habe ich versucht, den QuickSort-Algorithmus in Python zu implementieren, und ich konnte es nicht richtig funktionieren. Obwohl das Programm die Sub-Arrays sortiert, wird es nicht in der Hauptliste angezeigt. Ich bin neu im Programmieren, also kann mir jemand helfen zu verstehen, welchen Teil oder welches Konzept ich nicht richtig gemacht habe?

def swap(arr, right, left): 
    temp = arr[right] 
    arr[right] = arr[left] 
    arr[left] = temp 

def split_array(arr, right): 
    left_half = arr[:right] 
    right_half = arr[right:] 
    a = (left_half, right_half) 
    return a 

def quick_sort(arr): 
    if len(arr) >= 2: 
     pivot = 0 
     left_mark = pivot + 1 
     right_mark = len(arr) - 1 
     stop = True 

     while stop: 
      while arr[pivot] > arr[left_mark] and left_mark < right_mark: 
       left_mark += 1 
      while arr[pivot] < arr[right_mark] and left_mark < right_mark: 
       right_mark -= 1 
      if left_mark < right_mark: 
       swap(arr, right_mark, left_mark) 
       right_mark -= 1 
       left_mark += 1 
      else: 
       if arr[pivot] > arr[right_mark]: 
        swap(arr, right_mark, pivot) 
       stop = False 
     left, right = split_array(arr, right_mark) 
     quick_sort(left) 
     quick_sort(right) 
    return arr 

array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1] 
print(quick_sort(array)) 

Answer 1

ändern diese:

left, right = split_array(arr, right_mark) 
quick_sort(left) 
quick_sort(right) 

dazu:

left, right = split_array(arr, right_mark) 
arr = quick_sort(left) + quick_sort(right) 

Quicksort wird in der Regel umgesetzt „in- platzieren ", um das Kopieren von Arrays zu vermeiden. Ihre Implementierung erstellt stattdessen eine vollständige Kopie des Arrays bei jedem Schritt und gibt sie zurück, so dass Sie die Teile selbst zusammensetzen müssen.

UPDATE

Eine kleine Änderung Ihrer Algorithmus an Ort und Stelle zu machen statt:

def quick_sort(arr, start=0, end=None): 
    if end is None: end = len(arr)-1 
    if end > start: 
     pivot = start 
     left_mark = start + 1 
     right_mark = end 
     stop = True 

     while stop: 
      while arr[pivot] > arr[left_mark] and left_mark < right_mark: 
       left_mark += 1 
      while arr[pivot] < arr[right_mark] and left_mark < right_mark: 
       right_mark -= 1 
      if left_mark < right_mark: 
       swap(arr, right_mark, left_mark) 
       right_mark -= 1 
       left_mark += 1 
      else: 
       if arr[pivot] > arr[right_mark]: 
        swap(arr, right_mark, pivot) 
       stop = False 
     quick_sort(arr, start, right_mark - 1) 
     quick_sort(arr, right_mark, end) 

array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1] 
quick_sort(array) # in-place 
print(array) # now sorted 

IMO, die folgende ist klarer und entspricht genau die typische Beschreibung des Algorithmus:

def quick_sort(arr, start=0, end=None): 
    if end is None: 
     end = len(arr) - 1 

    if end <= start: 
     return 

    pivot = arr[start] 
    left_mark = start - 1 
    right_mark = end + 1 

    while left_mark < right_mark: 
     left_mark += 1 
     while arr[left_mark] < pivot: 
      left_mark += 1 

     right_mark -= 1 
     while arr[right_mark] > pivot: 
      right_mark -= 1 

     if left_mark < right_mark: 
      arr[left_mark], arr[right_mark] = arr[right_mark], arr[left_mark] 

    quick_sort(arr, start, right_mark) 
    quick_sort(arr, right_mark + 1, end) 

Answer 2

Sie sind genau richtig! left und right sind separate Einheiten nach , nicht Teile der ursprünglichen arr. Nach quick_sort(right), sagen wir arr=left+right. Ich denke, das wird es tun. (Notwendigkeit, den Fall zu überprüfen, wenn es nur ein Element ist entweder in left oder right.)