ソートアルゴリズム

ソートアルゴリズムとは?

ソートアルゴリズムとはなんでしょう?簡単に説明します。まずソートとは「並べ替え」のことで、アルゴリズムとは「方法」です。つまり並べ替えの方法です。

学校で同じクラスの生徒を身長の小さい順に並べ替えたいとします。とりあえずランダムですが一列にならんでもらいましょう。

並べ替えの方法①挿入法
並べ替えの方法②選択法
並べ替えの方法③交換法(バブルソート)

挿入法

簡単に説明します。
生徒①、生徒②、生徒③、生徒④、生徒⑤、の5人でやってみましょう。
それぞれ身長は、
①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。

挿入法では、先頭の生徒を仮確定し次の生徒の位置を決めます。終わったら次の生徒。。。と繰り返します。やってみましょう。


1回目 ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
2回目 ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
3回目 ③1m50cm、①1m70cm、②1m90cm、④1m60cm、⑤1m80cm。
4回目 ③1m50cm、④1m60cm、①1m70cm、②1m90cm、⑤1m80cm。
5回目 ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm

3回目で③の生徒が一番に挿入されたのがわかります。4回目でも④の生徒が二番に挿入されました。

選択法

先頭の生徒と残り全員の身長を比較して一番小さい生徒を探し出し、先頭の生徒と位置を交換します。一番小さい生徒が確定したあと、未確定の先頭の生徒と残り全員の身長を比較して二番目に小さい生徒を選択します。あとは繰り返します。

1回目 ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
2回目 ③1m50cm、②1m90cm、①1m70cm、④1m60cm、⑤1m80cm。
3回目 ③1m50cm、④1m60cm、①1m70cm、②1m90cm、⑤1m80cm。
4回目 ③1m50cm、④1m60cm、①1m70cm、②1m90cm、⑤1m80cm
5回目 ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm②1m90cm

未確定(黒字)の先頭と全てを比較し、一番小さいものが選択(青字)され、位置が入れ替わってるのがわかります。

交換法(バブルソート)

今回は小さい順に左から確定したいので、右から追いやる形で移動します。

1回目 ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
    ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
    ①1m70cm、②1m90cm、③1m50cm、④1m60cm、⑤1m80cm。
    ①1m70cm、③1m50cm、②1m90cm、④1m60cm、⑤1m80cm。
    ③1m50cm、①1m70cm、②1m90cm、④1m60cm、⑤1m80cm。
2回目 ③1m50cm、①1m70cm、②1m90cm、④1m60cm、⑤1m80cm。
    ③1m50cm、①1m70cm、②1m90cm、④1m60cm、⑤1m80cm。
    ③1m50cm、①1m70cm、④1m60cm、②1m90cm、⑤1m80cm。
    ③1m50cm、④1m60cm、①1m70cm、②1m90cm、⑤1m80cm。
3回目 ③1m50cm、④1m60cm、①1m70cm、②1m90cm、⑤1m80cm。
    ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm。
    ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm。
4回目 ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm。
    ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm。
5回目 ③1m50cm、④1m60cm、①1m70cm、⑤1m80cm、②1m90cm。

各回は左に追いやるまで隣と交換を繰り返していきます。

まとめ

今回は代表的な3つを取り上げましたが他にもあるので「ソート アルゴリズム」検索してみてください。おまけですが、アニメーションで並び替えられてる様子をみることができるサイトを紹介します。
海外のサイトなので、右クリックで翻訳するとわかりやすいです。

https://www.toptal.com/developers/sorting-algorithms

コメント