クイックソートアルゴリズムの実装でのバグ

Question

最近、私はPythonでクイックソートアルゴリズムを実装しようとしていましたが、正しく動作させることができませんでした。プログラムはサブ配列をソートしますが、メインリストには反映されていません。私はプログラミングに慣れていないので、誰も私が正しくやっていない部分やコンセプトを理解するのを助けることができますか？

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のいずれかで唯一の要素がある場合を確認する必要があります。）