quicksortのドライランは正しいですか？混乱しました

Question

私は試験の準備をしており、現在はクイックソートのために再度学習しています。

私は、アレイ

8,6,2,7,1,4,3,5 

私の友人のためにクイックソート予行演習を行うことになってると言うには、クイックソートで、それは同時に、インデックスとスワップを移動しますので、私はそれが間違っていないと言います。基本的には以下の手順では、移動するステップをスキップできますi, j。だから彼は私が同じ時間に移動して交換する必要があると言います。彼が正しいのかい？私はそれがすべて良いと思う..今私は試験のために確信していないので教えてください...

私はインデックスを持っていますiそれはピボット要素よりも大きな要素を見つけるまで配列を経由します。 jはピボット要素より低いインデックスです。 Pはピボット要素である。 ||は、要素がソートされた正しい位置にあることを意味します。

8,6,2,7,1,4,3,5 
i   j P 

3,6,2,7,1,4,8,5 
    i  j P 

3,4,2,7,1,6,8,5 
    i  j P 

3,4,2,7,1,6,8,5 
     i j  P 

3,4,2,1,7,6,8,5 
     j i  P 

3,4,2,1,|5|,6,8,7 
     j P  i 

3,4,2,1,|5|,6,8,7 
i j P 

3,4,2, 1, |5|,6,8,7 
i  Pj 

1,4,2, 3, |5|,6,8,7 
i  Pj 

1,4,2,3,|5|,6,8,7 
    i j P 

1,2,4,3,|5|,6,8,7 
    j i P 

1,2,|3|,|4|,|5|,6,8,7 
    j P i 

1, 2, |3|,|4|,|5|,6,8,7 
i Pj 

1, 2, |3|,|4|,|5|,6,8,7 
j Pi 

|1|, |2|,|3|,|4|,|5|,6,8,7 
j Pi 

|1|,|2|,|3|,|4|,|5|,6,8,7 
        i j P 

|1|,|2|,|3|,|4|,|5|,6,8,7 
        j i P 

|1|,|2|,|3|,|4|,|5|,|6|,|7|,|8| 
        j P i 

これは彼のバージョンです。彼は私のような余分なステップで指数を動かさないので、私よりもずっと短い。だから、彼は私よりも2歩少ない。あなたは正しいと思いますか？ビューの試験の点からまあ

Answer 1

試験であなたその優れたが、それぞれ、すべてのステップを詳しく説明するので、私は、あなたのバージョンがより適切と思われると思います。

あなたの友人のバージョンでは、left(i)とright(j)イテレータとpivot要素の表示がないので、審査官は非常に満足しているでしょう。実装の観点から

、はあなたの両方は、基本的にあなたが別にイテレータの移動だけでなく、値のスワップを示し、それは、セマンティクスのを変更しないそのことだけ、同じことをやっていますアルゴリズム。

あなたは慎重に表示された場合、その同じこと：

YOU

swap(array[i] , array[j]) 
i = i + 1 
j = j - 1 

FRIEND

swap(array[i++] , array[j--])