そこで、クイックソートのアルゴリズムで躓いています。
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ベストアンサー
- 回答日時:
ちょっと長いですが、こういうことでは。
(位置の値は、検索範囲の左から数えて何番目かです。)
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 ]
要素が1になったエリアはさわらない。
<右のエリアからさらに同じように繰り返す>
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 ]
すべての要素が1になったので終了。
#長年この考え方でやっているのだが、人に教えるとなると自信がない(~_~;
この回答への補足
補足でお礼を!
やっと理解できました。
要は、基準値の右に大きいのを集めて左に小さいのを集める。
そのために基準値を移動させている。
隣同志になるまで。
そういうことでした。
シ、シマッタ!
と、とんどもない考え違いをしていたようです。
正に、回答の通りです。
面目ない次第です。
ともかく、もう一度よーく考えてみます。
No.1
- 回答日時:
こんにちは
>問題は、「なぜ、『右から基準値と比較して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 の手前まで』なのだ?」
それは、「堂々巡りに陥るからだ!」
では、「なぜ、堂々巡り陥るのだ!」
「・・・・・」
私が、「・・・・・」に陥るのは理由は明確です。
>おいおい!基準値を確定することが大事じゃないか?
という声は聞こえるのですが・・・。
その声に私の脳は「・・・・・」とダンマリ。
多分、質問のクイックソートの考え方を私が全く理解していないから。
なんとか、もう少し粘って「ガッテン!」に到達したいと思います。
ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 環境・エネルギー資源 原発福島の排出水の数値の公表を 5 2023/08/11 19:57
- 統計学 統計学、エクセルがわかりません!解答と詳しい解説をお願いします! (1)それぞれの地域別に記述統計量 9 2022/08/21 16:30
- その他(バイク) 休日になると、主要道を音大きいバイクが走って行きます。 2 2023/05/27 12:34
- 一戸建て 注文住宅の総費用について 2 2022/08/13 17:12
- 郵便・宅配 ヤマト運輸なんて使う価値なんてなんかあるの? 無駄に高いだけで 例えば 日本郵便と比較 ゆうパケット 3 2023/03/07 15:57
- 映画館 映画館のメンズデイ、レディスデイ、シニア割引、損しているのは誰? 3 2022/06/16 09:47
- Visual Basic(VBA) セルの値を比較してセルの値の色を変更するには 4 2022/05/22 20:28
- Access(アクセス) Accessテキストボックス内に2つのフィールドの値を比較して大きい方の値を表示させる方法 1 2022/09/09 10:50
- 統計学 個別の期待値は小さいけど集計すると期待値は大きくなる場合とは? 4 2022/06/14 08:27
- 統計学 最適化問題について質問がございます。 群知能という分野で、粒子群最適化や猫群知能の比較グラフを見た時 1 2022/06/17 15:58
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語 exitの使い方
-
ラジオボタンの値の取得につい...
-
足して100になるような乱数のア...
-
フォームを開くときに、コンボ...
-
Excel-vba 文字列と変数を...
-
C#で動的にコントロールを取得...
-
VBAで多項式近似曲線の計算
-
VB6.0-整数と余りを求める
-
数字の位ごとの値を表示するプ...
-
Nullってどういう意味ですか?
-
VBAのチェックボックス結果を集...
-
シグマのプログラムについて
-
UWSCのcallについて
-
C言語でCLAMP(a,b,c)
-
VBAでC列が入力済みならそのま...
-
railsのControllerでフォームの...
-
世界のナベアツ
-
DataGridView 複数行同時変更...
-
相関係数p値の出し方
-
VBAでダブルコーテーション入り...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語 exitの使い方
-
フォームを開くときに、コンボ...
-
Excel-vba 文字列と変数を...
-
数字の位ごとの値を表示するプ...
-
VB6.0-整数と余りを求める
-
VBAで配列のNULL判定
-
足して100になるような乱数のア...
-
フリーランタイマーの時間差分...
-
DataGridView 複数行同時変更...
-
相関係数p値の出し方
-
世界のナベアツ
-
10進数をアスキーコードに変換
-
C#で動的にコントロールを取得...
-
ラジオボタンの値の取得につい...
-
DWORDって
-
バッチファイルで正規表現を使...
-
4択問題のプログラムでランダム...
-
1つ前の値を変数に保存する方法
-
VBAの定数の使い方で、計算値を...
-
コンボボックスの名前を変数に...
おすすめ情報