0

クイックソートアルゴリズムを学習していますが、何らかの理由で、この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
4

4 に答える 4

2

これが問題であると完全に確信しているわけではありませんが、ピボットを間違って選択しています:

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

変更されたリストの先頭ではなく、常に元のリストの先頭を取得しています。

ある時点で範囲を left=5,right=10 に縮小したと仮定します - list[0] をピボットとして選択しました - これは良いことではありません。
その結果、left>0リストの最初の要素を無視する各反復で、それを「見逃す」-部分的な並べ替えを説明できます

于 2012-04-06T06:55:13.497 に答える
1 
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

ピボット インデックスは、スワップ時にのみインクリメントする必要があります。ステートメントi = i + 1の一部として、スワップと同じ深さまでインデントします。if

おまけの質問: なぜ 2 回パーティション分割を行うのですか?

于 2012-04-06T07:14:05.657 に答える
0

最後のスワップも。

A[左]、A[i - 1] = A[i-1]、A[左] #swap

ピボットで行う必要があります。

それに加えて、クイックソートはインプレースで機能します。したがって、次の return は必要ありません。

return list[:pivot] + [list[pivot]] + list[pivot+1:]

于 2012-04-06T10:35:58.123 に答える
-1

あなたの質問に対する正確な答えではありませんが、それでも最も関連性があると思います。

クイックソートを実装するときにピボットを常に同じ位置に選択することは、アルゴリズムの欠陥です。アルゴリズムを O(n^2) 時間で実行する一連の数値を生成できますが、絶対実行時間はおそらくバブルソートよりも悪くなります。

あなたのアルゴリズムでは、左端の項目を選択すると、配列が既にソートされているか、ほぼソートされている最悪の場合にアルゴリズムが実行されます。

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

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

実際に穴の記事をチェック。それはあなたの時間の価値があります。

于 2012-08-24T12:25:48.703 に答える