Q&A
どのソートプログラムも最終的には1、23、32、43と返ってくるかと思いますが、
「３２、２３、１、４３と予想した」というのは初回ループでの結果の話でしょうか？
「左右の比較をずらしながらやっている」バブルソートと勘違いしていないでしょうか？
選択ソートでぐぐれば、図解でわかりやすく解説しているサイトがいくつも見つかります。
そちらを確認されたほうが手っ取り早く理解も早いと思います。
前提
C++で選択ソートを勉強している時にどう動いているかわからなくなりました。
このコードだと一番小さい値を検索できていないと思ったのですが
コードを読む限りi番目とj(i+1番目の左右だけを検索しているように見えます。
実際にN＝4
値を43、32、23、1の順番に入れました。自分の予想だと左右の比較をずらしながらやっていると考えたため、３２、２３、１、４３と予想したのですが、1、23、32、43の順番で帰ってきました。
私がわからないのは「未ソート部分から最小値の位置を探し」の部分が私が上げたプログラムとどこに対応しているのか、とfor文の中にfor文とswap関数が入っていてどういう順番で動くのかがわかっていません。
私のどこのコードを読み間違えているかご指摘お願いします。
実現したいこと
-選択ソートのコードがどう動いているか理解したい
発生している問題・エラーメッセージ
#include <iostream> using namespace std; int N, A[200009]; int main() { // 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; // 選択ソート for (int i = 1; i <= N - 1; i++) { int Min = i, Min_Value = A[i]; for (int j = i + 1; j <= N; j++) { if (A[j] < Min_Value) { Min = j; // Min は最小値のインデックス（1～N） Min_Value = A[j]; // Min_Value は現時点での最小値 } } swap(A[i], A[Min]); } // 出力 for (int i = 1; i <= N; i++) cout << A[i] << endl; return 0; }
選択ソートは未ソート部分から最小値の位置を探し、その位置の要素と未ソート部分の先頭の要素を交換する。交換されて先頭にきたものはソート済みとすると考えています。私がわからないのは「未ソート部分から最小値の位置を探し」の部分が私が上げたプログラムとどこに対応しているのか、とfor文の中にfor文とswap関数が入っていてどういう順番で動くのかがわかっていません。
43、32、23、1がどういう推移で「３２、２３、１、４３」となる想定なのか簡単に説明してもらえますか？
43と32を比較 入れ替え [32,43,23,1]
43と23を比較 入れ替え [32,23,43,1]
43と1を比較 入れ替え [32,23,1,43]
ということでしょうか？
回答1件
0
ベストアンサー
先にこちらを回答。
引用テキスト「for文の中にfor文とswap関数が入っていてどういう順番で動くのか」
順番はプログラム通り動くとしかいいようがないですが、
二重for文の処理の流れが読み解けないということでしょうか。
以下は単純なfor文の処理例ですが、これはおわかりになるでしょうか。
c++
1 for (int i = 1; i <= 3; i++) { 2 処理A; 3 処理B; 4 }
流れとしは以下のようになります。
i=1 処理A; 処理B; i=2 処理A; 処理B; i=3 処理A; 処理B;
今回の二重for文処理はざっくり以下のような処理です。
上記の処理Aをfor文に置き換えているだけです。
c++
1 for (int i = 1; i <= 3; i++) { 2 for (int j = i+1 ; j <= 4; j++) { 3 最小値との比較処理; 4 } 5 swap処理; 6 }
流れとしては以下のようになります。
i=1 j=2 最小値との比較処理; J=3 最小値との比較処理; J=4 最小値との比較処理; swap処理; i=2 J=3 最小値との比較処理; J=4 最小値との比較処理; swap処理; i=3 J=4 最小値との比較処理; swap処理;
大前提として、ご提示のアルゴリズムはざっくり以下のようになっているものと理解しています。
A[1]A[2]A[3]A[4]から最小値のindex(min)を見つけ出し、最小値A[min]をA[1]に設定する(swap)
次に
A[1]は既に最小値なのでソート済み、A[2]A[3]A[4]が未ソートなので同様に最小値を探して、A[2]を最小値に設定(swap)する。
これを最後まで繰り返す。
最後は
A[1]A[2] がソート済み、 未ソートA[3]A[4]の最小値をA[3]に設定(swap)すれば、ソート完了。
ソート対象(未ソート部分)は
A[1]A[2]A[3]A[4]
A[2]A[3]A[4]
A[3]A[4]
と変化します
外側のfor文でi は 1,2,3 と変化します。iが指し示すのは未ソート部分の先頭インデックスです。
4はA[1]A[2]A[3]がソート済みであれば最大値が自ずとA[4]になるので不要です。
内側のfor文で j は
i=1のとき2、3、4
i=2のとき3、4
i=3のとき4
と変化します。jが指し示すのは未ソート部分の先頭を除いたインデックスの並びです。
i=1のときの二重for文での対象データは
A[1]A[2]A[3]A[4]
j は 2,3,4と推移
c++
1int Min = i, Min_Value = A[i];
とすることでソート部分先頭を仮の最小値として設定しています。
これによって二個目のfor文でjの初期値をi+1（初回は2）とすることができます。
A[1]を仮の最小値としているので あとはA[2]～A[4]が仮の最小値と比較して小さいかどうか確認すればいいわけです。
以下説明が冗長になりますが
引用テキスト「未ソート部分から最小値の位置を探し」の部分が私が上げたプログラムとどこに対応しているのか
「未ソート部分から最小値の位置を探し」はswapを除いた二重forループ内が該当します。
プログラム的にはこの箇所です。
c++
1 for (int i = 1; i <= N - 1; i++) { 2 int Min = i, Min_Value = A[i]; 3 for (int j = i + 1; j <= N; j++) { 4 if (A[j] < Min_Value) { 5 Min = j; // Min は最小値のインデックス（1～N） 6 Min_Value = A[j]; // Min_Value は現時点での最小値 7 } 8 } 9 10 }
「未ソート部分」の指定は、
外側のforループの変数iで未ソート部分の先頭indexを指定
内側のforループで未ソート部分の先頭以外のindexを指定
これで未ソート部分のindexをすべて指定しています。
「最小値の位置を探す」
1回目のループ処理を例にすると
c++
1 for (int i = 1; i <= N - 1; i++) { 2 int Min = i, Min_Value = A[i];
ここで A[1]の値(43)をMin_value、index(1)をMinに仮設定
内側forループでMin_valueと未ソートの残り部分を比較
c++
1for (int j = i + 1; j <= N; j++) { 2 if (A[j] < Min_Value) {
jは2,3,4と推移するので
A[2] < 仮の最小値 (実質A2とA1の比較)
A[2]のほうが小さいので Minを2 Min_Valueを32に
A[3] < 仮の最小値 (実質A3とA2の比較)
A[3]のほうが小さいので Minを3 Min_Valueを23に
A[4] < 仮の最小値 (実質A4 とA3の比較)
A[4]のほうが小さいので Minを4 Min_Valueを1に
と網羅的に比較し、A[1]A[2]A[3]A[4]の最小値indexがMinの値 4 とわかります。
投稿2022/08/16 21:54
総合スコア509
あなたの回答
tips
プレビュー
