クイックソートの再帰エラー

Question

私の考え： 私はPythonでクイックソートを実装しようとしています。 最初の要素をピボットとして設定します。 左のマークの要素がピボットより大きい場合、ピボットよりも小さい要素を見つけてスワップするために右のマークを移動し始めます。 右のマークが左のマークよりも小さい場合は、右のマークの要素でピボットを入れ替えます。 リストをピボットで区切ります。そしてステップを繰り返してください。

質問： 私の想像通り、私のコードはリストを2つのリストに分けることができます。それが何らかの形で要素を何度かコピーして間違ってしまったときに戻します。私は再帰に精通しておらず、問題を見つけることができません。

def quick_sort(lst): 
    front = [] 
    rear = [] 
    temp = 0 
    pivot = lst[0] 
    i = 1     #leftmark 
    j = len(lst)-1  #rightmark 
    if len(lst) == 1: 
     return lst 
    while i<=j: 
     if lst[i]<pivot: 
      i+=1 
     else: 
      if lst[j]>pivot: 
       j-=1 
      elif lst[j] == pivot: 
       break 
      else: 
       temp = lst[i] 
       lst[i] = lst[j] 
       lst[j] = temp 

    '''if j<i (rightmark < leftmark) swap pivot with position j''' 
    temp = pivot 
    pivot = lst[j] 
    lst[j] = temp 
    lst[0] = pivot 
    front = lst[0:j+1] 
    rear = lst[i:len(lst)+1] 
    return quick_sort(front) + [pivot] + quick_sort(rear) 

Answer 1

リストを間違ってスライスしています。 （from the startを表し、:後till the endを表す:前に、ここでは空虚）のピボット位置jにあるので、あなたは、lst[ j + 1 : ]にlst[ : j ]とlst[i:len(lst)+1]にlst[0:j+1]を交換する必要がありますし、それを無視すべきです。 最後になりましたが、その代わりtemp VAR、例のスワップにタプルを使用することを検討してください：

temp = a 
a = b 
b = temp 

は1つのライナーここ

a, b = b, a 

に置き換えることができ、私の最後の作業コードです：

def quick_sort(lst): 
    if lst: 
     pivot = lst[0] 
     i = 1     #leftmark 
     j = len(lst)-1  #rightmark 
     if len(lst) == 1: 
      return lst 
     while i <= j: 
      if lst[i] < pivot: 
       i += 1 
      elif lst[j]>pivot: 
        j-=1 
      elif lst[j] == pivot: 
       break 
      else: 
       lst[i], lst[j] = lst[j], lst[i] 
     '''if j<i (rightmark < leftmark) swap pivot with position j''' 
     lst[0], lst[j] = lst[j], lst[0] 
     front = lst[ : j ] 
     rear = lst[ j+1 : ] 
     return quick_sort(front) + [ pivot ] + quick_sort(rear) 
    return [] 

は、

>>> quick_sort([1,3,4,2,6,9,0]) 
[0, 1, 2, 3, 4, 6, 9]