quickSortアルゴリズムのすべてのピボット値を見つける

Question

私は、クイックソートの適切な実装についてちょっと混乱しているようです。

QuickSortのピボット値をすべて探したければ、どの時点でサブアレイの分割を停止できますか？

QuickSort(A,p,r): 
    if p < r: 
     q = Partition(A,p,r) 
     Quicksort(A,p,q-1) 
     Quicksort(A,q+1,r) 

Partition(A,p,r): 
    x = A[r] 
    i = p-1 
    for j = p to r-1: 
    if A[j] ≤ x: 
     i = i + 1 
     swap(A[i], A[j]) 
    swap(A[i+1], A[r]) 
    return i+1 

意味、私は、配列がある場合： A = 9、7、5、11、12、2、14、3、10、6]

としてクイックソート区切りをこの混乱のポイントに到達するため、その構成片に...

A = [2,5、3] [12、7、14、9、10、11]

一歩...

A = [2,5] [7,12,14,9,10,11]

左側のサブアレイはここで停止しますか？またはそれ（quickSort）は最終的なピボット値として5を使ってquickSortを最後に呼び出しますか？

私は、すべてのサブアレイが単一のアイテムになるまで続けますが、私の同僚の1人がそうでなければ私に言いました。

Answer 1

例のピボットは、6, 3, 11, 10, 9, 12です。関連項目

左側のサブアレイはここで停止しますか？

ソースコードを調べることが常にベストです。再帰的サブアレイが[2, 5, 3]になると、関数QuickSortがp = 0とr = 2で呼び出されます。次の2つのコールはQuicksort(A,0,0)とQuicksort(A,2,2)になるので、進めよう：Partition(A,0,2)はq = 1を返します。したがって、Quicksort(A,0,1)は呼び出されませんので、サブ配列[2, 5]を調べる機会はありません。既にソートされています。