python - QuickSort は正しい値を返しますが、その場で並べ替えません

Question

QuickSortがソートされた値を正しく返す理由を理解するのに苦労していますが、結果の配列は正しくソートされていません。

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index = partition(array)
    p_value = array[p_index]
    return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

def partition(array):
    pivot = array[0]
    i = 1
    for j in xrange(1,len(array)):
        print j
        if array[j] < pivot:
            tmp = array[j]
            array[j] = array[i]
            array[i]=tmp
            i += 1
    tmp = array[i-1]
    array[i-1] = pivot
    array[0] = tmp
    return i-1

出力例を次に示します。

>>> q = [5,4,3,2,1]
>>> qSort(q)
[1, 2, 3, 4, 5]
>>> q
[1, 4, 3, 2, 5]

前もって感謝します！

Answer 1

これは、returnステートメントで新しいリストを作成しているためです。

return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

関数qSortが基本ケースに達すると、リストを返します。これは と連結さ[p_value]れ、 として返されますlist。list渡されたものをどこにも変更しません。

関数を再帰的に呼び出すとqSort、リストのスライスが与えられ、関数は基本ケースのリストを返し、pivotそれを他の再帰呼び出しに追加して、新しいリストを生成します。

qSort関数を次のように変更して、何が起こっているかを確認します

def qSort(array):
    n = len(array)
    if (n == 1 or n ==0):
            return array
    p_index, array = partition(array)
    p_value = array[p_index]
    returnVal = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    print "Returning:", returnVal, "Original Array:", array
    return returnVal

出力 -

>>> q = [5,4,3,2,1]
>>> qSort(q)
Returning: [2, 3] Original Array: [2, 3]
Returning: [2, 3, 4] Original Array: [2, 3, 4]
Returning: [1, 2, 3, 4] Original Array: [1, 4, 3, 2]
Returning: [1, 2, 3, 4, 5] Original Array: [1, 4, 3, 2, 5]
[1, 2, 3, 4, 5]

元の に変更を反映するにlistは、次のオプションを実行できますq = qSort(q)。

PS - 最初の値の代わりにランダムなインデックスを設定すると、クイックソート機能に適しています。ここのビットを参照してくださいChoice of Pivots。

Answer 2

配列を返し、その場で並べ替えたい場合は、返す前に配列を結果と等しくし、新しいものを作成しないでください。return ステートメントを次のように変更することで、これを行うことができます。

    array[:] = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])
    return array

ご了承ください

    array = qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n])

lhs 変数はローカル変数として扱われるため、どちらも機能しません。

Answer 3

関数を q に適用する

q = qSort(q)