[アルゴリズム] 選択ソートの実装(解説)

Pocket
LINEで送る
GREE にシェア
LinkedIn にシェア

前回行なったバブルソートは昇順処理の定番だったのですが、今回扱う選択ソートも非常に分かりやすく、実装も手軽なので、言語別対応してみようと思います。
でも、前回の時も同じでしたが、各言語において、ソート処理は関数化されているので、ソート処理を自分で書くという行為は、ギアの再発明にあたります。
でも、エンジニアとしてこうしたアルゴリズムのコーディングは、写経してでも手打ちしておきたいと考えることが非常に重要と考えのは僕だけではないはず。
そうしたエンジニアイズムの考え方の見合う人に読んでもらいたい記事としてもらえると幸いでございます。

選択ソートとは?

前回のバブルソートは、小さい数字が泡のように上に上っていく様子から付けられた名前ですが、今回の「選択ソート」は、選択された数値を入れ替えていく事から安易に呼ばれているのだと思います。
wikipedia
アルゴリズムとしてはバブルソートに比べて、ロープ回数が少なく且つ一定量で行えるという事で、高速であると言えるようですが、wikipediaに書かれている内容としては、数値に同数がある場合のアルゴリズムとしては安定性が無いという結論のようです。
ただ、同一数値においての優劣差は無いと考えると、その点は考慮しなくても大丈夫だと思われます。

詳しく解説

選択ソートの基本動作は、下記の手順です。

1. 一列にして順に評価する

対象の数値列を一列に並べて左から順に評価していく
%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-33-37

2. 最小値を取得

評価対象数値よりも右側にある数値列の中から一番小さな数値を取得
%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-37-22

3. 評価値と最小値を入れ替える

評価対象の数値を右側の最小値を入れ替える。
%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-40-34

4. 評価値をロックする

上記までの作業が完了すると、評価対象の数値はロックされ、評価対象が右に一つシフトする作業を繰り返す
%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-45-18

5. 一番右の数値まで処理する

上記を繰り返して全ての数値が評価されたら完了です。
%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-55-55

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-00

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-06

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-12

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-18

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-23

6. 完成

%e3%82%b9%e3%82%af%e3%83%aa%e3%83%bc%e3%83%b3%e3%82%b7%e3%83%a7%e3%83%83%e3%83%88-2016-12-29-8-56-30

関連リンク

バブルソート

Javascript編
PHP編
Python編
Shell編
Awk編
C言語編
Go言語編
Ruby

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です