クイックソートが予期せぬ結果を返さない - Python3

Question

私は、壁の左側の現在の要素とデータセットの最後のピボットを具体的に設定するクイックソートアルゴリズムに取り組んでいます。 ソートでは、現在の要素とピボットを比較し、ピボットより大きいたびに現在の要素をインクリメントします。ピボットに等しいかそれより小さい場合は、現在の要素を壁の右側にあるアイテムと入れ替え、壁を右に1つ移動します。ここで

は私のコードです：

def QuickSort(dataset, low, high): 
    if (low >= high): 
     return dataset 
    else: 
     #Set pivot to last element 
     pivot = high 
     #Set wall at first element 
     wall = low 
     #Loop through list - if current element is less or equal 
     #to the pivot, swap current element with element right of wall 
     #and move wall on. 
     for i in range(high): 
      if (dataset[i] <= pivot): 
       temp = dataset[wall] 
       dataset[wall] = dataset[i] 
       dataset[i] = temp 
       wall = wall + 1 
       if wall >= high: 
        break 

     #recursively call for subsequent part of list 
     QuickSort(dataset, low, wall-1) 
     QuickSort(dataset, wall, high) 

dataset = [1,6,2,3,6,7,4,2,5] 
dataset_length = len(dataset) 
sorted_data = QuickSort(dataset, 0, dataset_length) 
print(sorted_data) 

input() 

コードを実行すると、データセットが返されないと私は間違っているところ私はかなり見ることができません。ご協力ありがとうございました。

Answer 1

これは、ピボットをリストの最後の要素に設定しません。代わりに、ピボットを9のデータセットの長さに設定します。したがって、dataset[high - 1]に変更すると機能します。

また、あなたがpivot以上であるか未満pivotがrange(high)ない要素を検索する必要のある範囲は、それはあなたが再帰に深く行くときので、リストのサイズが変化range(low, high)であり、またそのインデックスの開始と終了。

def QuickSort(dataset, low, high): 
    if (low >= high): 
     return 
    #Set pivot to last element 
    pivot = dataset[high - 1] 
    #Set wall at first element 
    wall = low 
    #Loop through list - if current element is less or equal 
    #to the pivot, swap current element with element right of wall 
    #and move wall on. 
    for i in range(low, high): 
     if (dataset[i] <= pivot): 
      temp = dataset[wall] 
      dataset[wall] = dataset[i] 
      dataset[i] = temp 
      wall = wall + 1 
      if wall >= high: 
       break 
     #recursively call for subsequent part of list 
    QuickSort(dataset, low, wall - 1) 
    QuickSort(dataset, wall, high) 

dataset = [1,6,2,3,6,7,4,2,5] 
dataset_length = len(dataset) 
QuickSort(dataset, 0, dataset_length) 
print(dataset)