Python QuickSortのみ部分的にソートする

Question

私はクイックソートアルゴリズムを学んでいますが、何らかの理由でこのPython実装の出力が部分的にソートされており、大きな入力に対しては最大再帰深度に達しています。私は最後の数日間、これに対して頭を叩いていたし、おそらく何か本当に馬鹿だと知っていますが、私はそれを理解することができないので、私はどんな助けにも感謝します。

def ChoosePivot(list): 
    return list[0] 

def Partition(A,left,right): 
    p = ChoosePivot(A) 
    i = left + 1 

    for j in range(left + 1,right + 1): #upto right + 1 because of range() 
     if A[j] < p: 
       A[j], A[i] = A[i], A[j] #swap 
       i = i + 1 
    A[left], A[i - 1] = A[i-1], A[left] #swap 
    return i - 1 

def QuickSort(list,left, right): 
    if len(list) == 1: return 
    if left < right: 
     pivot = Partition(list,left,right)    
     QuickSort(list,left, pivot - 1) 
     QuickSort(list,pivot + 1, right) 
     return list[:pivot] + [list[pivot]] + list[pivot+1:] 

sample_array = [39,2,41,95,44,8,7,6,9,10,34,56,75,100] 
print "Unsorted list: " 
print sample_array 
sample_array = QuickSort(sample_array,0,len(sample_array)-1) 
print "Sorted list:" 
print sample_array 

Answer 1

これが問題であることを確認しentirleyが、あなたは間違ってピボットを択一ているわけではありません：あなたは常に変更され、リストの先頭を元のリストの頭を取って、とされていない

def ChoosePivot(list): 
    return list[0] 
def Partition(A,left,right): 
    p = ChoosePivot(A) 
    .... 

。

範囲をleft = 5、right = 10に減らしたと仮定します。リスト[0]をピボットとして選択しました。これはうまくいかない場合があります。その結果、
は、リストの最初の要素を無視し、left>0各反復でそれを「ミス」 - アミットが言ったように

Answer 2

def ChoosePivot(list): 
    return list[0] 

ソート部分を説明することができ、これは間違っています。あなたはp = A[left]が欲しいです。しかし、別の問題がある：あなたが交換するとき

if A[j] < p: 
    A[j], A[i] = A[i], A[j] #swap 
i = i + 1 

ピボット指数はインクリメントされなければなりません。 ifステートメントの一部としてスワップと同じ深さにインデントi = i + 1を挿入します。

ボーナスの質問：なぜ2回のパーティショニングですか？

Answer 3

また最後のスワップ。

A [左]、Aは、[I - 1] [I-1]、

#swap Aは、[左]ピボットで行わなければなりません=。

Quicksortはその場で動作します。だから、あなたは帰還の必要はありません。

復帰リスト[ピボット] + [リスト[ピボット]] +リスト[ピボット+ 1：]

Answer 4

ない正確にあなたの質問への答えが、私はそれはまだ最も関連性のだと信じています。

クイックソートの実装時に常に同じ位置にピボットを選択することは、アルゴリズム上の欠陥です。あなたのアルゴリズムをO（n^2）時間で実行させる数列を生成することができ、絶対実行時間はおそらくbubblesortより悪くなります。

アルゴリズムでは、一番左の項目を選択すると、配列がすでにソートされているかソートされている最悪の時間にアルゴリズムが実行されます。

ピボットの選択は、この問題を回避するためにランダムに実行する必要があります。

ウィキペディアにアルゴリズム実装上の問題を確認してください：実際にhttp://en.wikipedia.org/wiki/Quicksort#Implementation_issues

、穴の記事を確認してください。それはあなたの時間の価値がある。