等しい要素を使ったクイックソートアルゴリズムの進化

Question

私は同じ要素（1（a）、1（b）、1（c））の配列を使ってクイックソートアルゴリズムの進展を示すために必要なアルゴリズム割り当てに取り組んでいます。 、など）、ピボットは配列の最後の要素です。アルゴリズムの再帰的な部分は私を混乱させるものです。私が考える1（d）になる

1(a) 1(b) 1(c) 1(d) [1(e)] 
1(a) | 1(b) 1(c) 1(d) 1(e) 
1(a) 1(b) | 1(c) 1(d) 1(e) 
1(a) 1(b) 1(c) | 1(d) 1(e) 
1(a) 1(b) 1(c) 1(d) | 1(e) 

このピボット後と進行は一つ少なく為替を除いて上記と同じで、次のようになります。これまでのところ私は進行しています。私は左と右の再帰呼び出しがどのように動作するのか混乱しています。配列の「右側」の要素は、それ自身で交換されるでしょうか？どの時点でこのアルゴリズムは停止しますか？ここ

は擬似コードである：

QS(A, p, r): 
if p < r 
    q = PARTITION(A, p, r) 
    QS(A, p, q - 1) 
    QS(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 
     exchange A[i] with A[j] 
exchange A[i + 1] with A[r] 
return i + 1 

Pは、第1の素子アレイ、rは最後の要素です。

ありがとうございました。

Answer 1

if p < rガードによって無操作になりませんあなたのケースでは2回目の呼び出し、QS(A, q + 1, r)、コールがQS(A, r+1, r)なるようqは常に、rに等しくなりますので、必ず、無操作できなくなります、（p < rは常になります偽）。

あなたの配列が1、2、...、5; qの最初の値は5なので、最初の再帰呼び出しはQS(A,1,4)で、2番目の - QS(A,6,5)（no-op）です。

同じことがQS(A,1,4)ために起こるのだろう - そのqは4になり、2つの呼び出し - QS(A,1,3)とQS(A,5,4)。

QA(A,1,5) 
    PARTITION(A,1,5) -> 5 
    QS(A,1,4) 
     PARTITION(A,1,4) -> 4 
     QS(A,1,3) 
      PARTITION(A,1,3) -> 3 
      QS(A,1,2) 
       PARTITION(A,1,2) -> 2 
        QS(A,1,1) 
        QS(A,3,2) 
      QS(A,4,3) 
     QS(A,5,4) 
    QS(A,6,5) 

partitionに興味深い方法は、このようにしては決して見たことがありません。私は<=の代わりに<を使用して、同等の要素を交換することはありません。 （ここでは、もちろん、すべてのスワップは、2つの等しい指標の間でもありますが、一般的なケースではありません）。