選択法とは、基本選択法や選択ソートと呼ばれるもので、バブルソートと並ぶ代表的な整列アルゴリズムの一つです。
選択ではどのようにデータが並び替えられるか見てみましょう。再生ボタンを押すと「選択法」での並び替えが確認できます。
交換法(バブルソート)と似ているけれど、ちょっと違う感じがします。
そうだよね。隣同士を比べていないよね。最初はずっと左端と比較していたと思う。
交換法(バブルソート)とはアルゴリズムは異なります。どのように違うか確認しましょう。
情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-11
実践プログラム④ 整列アルゴリズム 選択法
3. 選択法とは ( 3 / 11 )
整列プログラム 選択法
学習の目的
-
1. 選択法とは
-
2. 選択法の手順
1. 選択法とは
2. 選択法の手順
次の5つのデータを選択法で昇順に並び替える例を見ていきましょう。
基準を決める
選択法は、左端もしくは右端を基準として並び替えを行います。
今回は、左端を基準として並び替えを行います。
基準と右隣の要素を比較する
基準の要素の値と右隣の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
基準とその次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が大きいので、何もせず次に進みます。
基準とその次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
基準とその次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が大きいので、何もせず次に進みます。
この段階で、左端を基準として残りのすべてのデータと比較が終わりました。
すべての値との比較が終わると、基準の位置のデータが確定します。
なるほど！先頭を固定して、他と比べて一番小さい値を交換しているので、左端が確定したってことか。
バブルソートは右端から決まっていったので逆ですね。
わかってきたようですね。続きを見ていきましょう。
基準を決める
残ったデータの左端を基準とします。
基準の要素と残ったデータを順に比較していきます。
基準と右隣の要素を比較する
基準の要素の値と右隣の要素の値を比較します。
右側の要素が大きいので、何もせず次の要素に進みます。
基準と次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
基準と次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が大きいので、何もせず次の要素に進みます。
左から2番めを基準とし、残りのすべてのデータと比較をしました。 最後まで比較が終わったので、基準の位置のデータが確定します。
基準を右にずらして、基準要素の値と他の要素の値を最後まで比較していくと基準の位置の数値が決まります。
並び替えが終わるまで続けましょう。
基準を決める
残ったデータの左端を基準とします。
基準の要素と残ったデータを順に比較していきます。
基準と右隣の要素を比較する
基準の要素の値と右隣の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
基準と次の要素を比較する
基準の要素の値と次の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
左から3番めを基準とし、残りのすべてのデータと比較をしました。 最後まで比較が終わったので、基準の位置のデータが確定します。
おー結構揃ってきた！もう少し！
もう少しですね。続きをやりましょう。
基準を決める
残ったデータの左端を基準とします。
基準の要素と残ったデータを順に比較していきます。
基準と右隣の要素を比較する
基準の要素の値と右隣の要素の値を比較します。
右側の要素が小さいので、基準の位置の要素と交換します。
左から4番めを基準とし、残りのすべてのデータと比較をしました。 最後まで比較が終わったので、基準の位置のデータが確定します。
ここで、残り1つですが、他のデータの並びが決まったので最後の一つも自動的に決まることになり、並び替えが完了しました。
昇順に並べるときは、端に小さいものを探して入れていくのでわかりやすかったです。
比較的わかりやすいアルゴリズムですね。
今の手順をもう一度ツールを使って確認しましょう。今回は処理内容も表示されているので、一つずつ確認してください。
