クイックソートの考え方？

質問

そこで、クイックソートのアルゴリズムで躓いています。

10,20,11,19,13,17,14,16,15

真中の値 13 を基準値として使う。
左から基準値と比較してより大きい値は 20。
右から基準値と比較して20 の手前までのより小さい値11。
両者を置換。
10,11,20,19,13,17,14,16,15

真中の値 13 を基準値として使って比較。
左から基準値と比較してより大きい値は 20。
右から基準値と比較して20 の手前までのより小さい値はない。
基準値と20とを置換。
10,11,13,19,20,17,14,16,15

真中の値 20 を基準値として使って比較。
左から基準値と比較してより大きい値はない。
右から基準値と比較してより小さい値は15。
両者を置換。
10,11,13,19,15,17,14,16,20

真中の値 15 を基準値として使って比較。
左から基準値と比較してより大きい値は19。
右から基準値と比較してより小さい値は14。
両者を置換。
10,11,13,14,15,17,19,16,20

真中の値 15 を基準値として使って比較。
左から基準値と比較してより大きい値はない。
右から基準値と比較してより小さい値はない。
これで15が真中と確定。

この後は、「同じ過程を再帰的に二つのサブセットに適用」するのは同じ。
これは、単に、クイックソートの処理手順を追えばわかる話です。

問題は、「なぜ、『右から基準値と比較して20 の手前まで』なのだ？」ということ。
そうでないと、「堂々巡りに陥るからだ！」というのはわかります。
が、私の理解はそこで立ち往生したままです。

還暦を迎えた私の頭は、オーバーヒート気味。

「そこは、このように考えたらよい」という回答をお願いします。

※自らの理解力と理解度の問題で質問するのは非常に恐縮。
※しかし、後一歩の理解の壁を超えたいので質問します。

回答No.2

KG_ · ベストアンサー

ちょっと長いですが、こういうことでは。

(位置の値は、検索範囲の左から数えて何番目かです。)

13が基準値
[ 10 20 11 19 13 17 14 16 15 ]

左から比べていって13以上なのは20(位置2)
右から比べていって13以下なのは11(位置3)
双方を入れ換える。

[ 10 11 20 19 13 17 14 16 15 ]

最後の位置を開始位置とし、さらに比べます
左から比較している位置2と、右から比較している位置3が
すれ違うので（又は同じ位置）、そこで、エリアをわける

[ 10 11 ][ 20 19 13 17 14 16 15 ]

＜左のエリアからさらに同じように繰り返す＞

11が基準値
左から比べていって11以上なのは11(位置2)
右から比べていって11以下なのは11(位置2)
すれ違うので（又は同じ位置）、そこでエリアをわける

[ 10 ][ 11 ][ 20 19 13 17 14 16 15 ]

要素が１になったエリアはさわらない。

＜右のエリアからさらに同じように繰り返す＞

17が基準値
左から比べていって17以上なのは20(位置1)
右から比べていって17以下なのは15(位置7)
双方を入れ換える。

[ 10 ][ 11 ][ 15 19 13 17 14 16 20 ]

最後の位置を開始位置とし、さらに比べます
位置1から左へ比べていって17以上なのは19(位置2)
位置7から右へ比べていって17以下なのは16(位置6)
双方を入れ換える。

[ 10 ][ 11 ][ 15 16 13 17 14 19 20 ]

最後の位置を開始位置とし、さらに比べます
位置2から左へ比べていって17以上なのは17(位置4)
位置6から右へ比べていって17以下なのは14(位置5)
双方を入れ換える。

[ 10 ][ 11 ][ 15 16 13 14 17 19 20 ]

最後の位置を開始位置とし、さらに比べます
左から比較している位置4と、右から比較している位置5が
すれ違うので（又は同じ位置）、そこで、エリアをわける

[ 10 ][ 11 ][ 15 16 13 14 ][ 17 19 20 ]

＜[15～14]のエリアを同じように処理する＞
ここからは要素の入換えだけ書き込みます。

基準値13
[ 10 ][ 11 ][ 15 16 13 14 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 16 15 14 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 ][ 16 15 14 ][ 17 19 20 ]

＜[ 16 15 14 ]のエリアを同じように処理する＞

基準値15
[ 10 ][ 11 ][ 13 ][ 16 15 14 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 ][ 14 15 16 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 16 ][ 17 19 20 ]

＜[ 15 16 ]のエリアを同じように処理する＞

基準値16
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 16 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 19 20 ]

＜[ 17 19 20 ]のエリアを同じように処理する＞

基準値19
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 19 20 ]
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 20 ]

＜[ 17 19 20 ]のエリアを同じように処理する＞

基準値20
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 20 ]
[ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 ][ 20 ]

すべての要素が１になったので終了。

#長年この考え方でやっているのだが、人に教えるとなると自信がない(~_~;

お礼

シ、シマッタ！
と、とんどもない考え違いをしていたようです。
正に、回答の通りです。
面目ない次第です。

ともかく、もう一度よーく考えてみます。

補足

補足でお礼を！

やっと理解できました。
要は、基準値の右に大きいのを集めて左に小さいのを集める。
そのために基準値を移動させている。
隣同志になるまで。

そういうことでした。

回答No.1

A88No8

こんにちは
>問題は、「なぜ、『右から基準値と比較して20 の手前まで』なのだ？」ということ。
>そうでないと、「堂々巡りに陥るからだ！」というのはわかります。
>が、私の理解はそこで立ち往生したままです。

　質問者さんのお考えを整理しましょう。
　「20 の手前まで」でないとしたら、どこまでと思われたのですか？
　「「堂々巡りに陥るからだ！」というのは判る」とのことなのですが、20も含めて同じようにシミュレーションしてみるとかでは納得できる結果が得られないのでしょうか？
　お考え通りにやってみるべしです。

お礼

function qsort(v, left, right) {
　　var i, last;

　　if (left >= right) /* 対象が2以下なら終了 */
　　　　return;
　　swap(v, left, Math.round((left + right) / 2)); /* 基準値を v[0] へ */
　　last = left;
　　for (i=left + 1; i <= right; i++) /* 基準値未満を前方と置換 */
　　　　if (v[i] < v[left])
　　　　　　swap(v, ++last, i);
　　swap(v, left, last); /* 基準値を所定位置へ戻す */
　　qsort(v, left, last - 1);
　　qsort(v, last + 1, right);
}

このクイックソートにアルゴリズムはスッキリと理解できます。
多分、頭の中でイメージできるからかも知れません。
しかし、質問のアルゴリズムは理解不能。

＞そうでないと、20と11とが永遠に入れ替えられる事態に陥る。

は、試して気付きました。

が、、「なぜ、『右から基準値と比較して20 の手前まで』なのだ？」
それは、「堂々巡りに陥るからだ！」
では、「なぜ、堂々巡り陥るのだ！」
「・・・・・」

私が、「・・・・・」に陥るのは理由は明確です。

＞おいおい！基準値を確定することが大事じゃないか？

という声は聞こえるのですが・・・。
その声に私の脳は「・・・・・」とダンマリ。
多分、質問のクイックソートの考え方を私が全く理解していないから。
なんとか、もう少し粘って「ガッテン！」に到達したいと思います。

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