내 빠른 정렬 알고리즘 구현의 버그

Question

최근에 파이썬에서 퀵 정렬 알고리즘을 구현하려고했지만 제대로 작동하지 못했습니다. 프로그램이 하위 배열을 정렬하더라도 주 목록에는 반영되지 않습니다. 프로그래밍에 익숙하지 않아 누구나 내가 옳지 않은 부분이나 개념을 이해하도록 도와 줄 수 있습니까?

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

변경이 :

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

퀵는 일반적으로 구현되는 "인 -이에

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

장소 복사 "를 피하십시오. 구현은 대신 각 단계에서 배열의 전체 복사본을 생성하고 반환하므로 조각을 직접 재구성해야합니다.

UPDATE

작은 변화는 알고리즘을 만드는 대신-장소 : IMO

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 

가, 다음이 명확하고 더 가깝게 알고리즘의 일반적인 설명과 일치 :

을

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

정확하게 맞습니다! left 및 right은 split_array 다음에 별개의 개체이며, 원래 부분은 아닙니다 arr입니다. quick_sort(right) 이후에 arr=left+right이라고 말하면됩니다. 나는 그것을 할 것이라고 생각합니다. (left 또는 right 중 하나에 하나 개의 요소가있을 때 케이스를 확인해야합니다.)