超初歩的なソートアルゴリズムのまとめ

はじめに

未来電子テクノロジーでインターンをしているやっきーです。
プログラミング初心者であるため、内容に誤りがあるかもしれません。
もし、誤りがあれば修正するのでどんどん指摘してください。

アルゴリズムとは

アルゴリズムは、コンピュータが行う計算方法のことです。アルゴリズムには、順次処理、分岐処理、繰り返し処理の3つがあります。この3つを組み合わせることで目的の計算を実現します。

アルゴリズムの例

ここでは、代表的なアルゴリズムとして、ソートアルゴリズムの一部を紹介します。

バブルソート

隣あう2つの値を比較して、並び替えを行う方法です。

例えば、(61,15,54,34,87,46,23)という配列を昇順に並べたい時は、

1. 61と15を比較、並び替える (15,61,54,34,87,46,23)
2. 61と54を比較、並び替える (15,54,61,34,87,46,23)
3. 61と34を比較、並び替える (15,54,34,61,87,46,23)
4. 61と87を比較、並び替えは行わない
5. 87と46を比較、並び替える (15,54,34,61,46,87,23)
6. 87と23を比較、並び替える (15,54,34,61,46,87,23)
7. 2週目に突入、15と54を比較、並び替えは行わない
8. 54と34を比較、並び替える (15,34,54,61,46,87,23)
9. 54と61を比較、並び替えは行わない
10. 61と46を比較、並び替える (15,34,54,46,61,87,23)
11. 61と87を比較、並び替えは行わない
12. 87と23を比較、並び替える (15,34,54,46,61,23,87)

以下、同じように比較、入れ替えを昇順(15,23,34,46,54,61,87)になるまで行います。

選択ソート

配列の最小値(または最大値)をみつけて、並び替えを行う方法です。

(61,15,54,34,87,46,23)という配列を昇順に並べたい時は、

1. 61以外の要素の最小値を探す。最小値は15なので、61と15を入れ替える。これ以後、15は固定する。 (15,61,54,34,87,46,23)
2. 15,61以外の要素の最小値を探す。最小値は23なので、61と23を入れ替える。これ以後、23は固定する。 (15,23,54,34,87,46,61)
3. 15,23,54以外の要素の最小値を探す。最小値は34なので、54と34を入れ替える。これ以後、34は固定する。 (15,23,34,54,87,46,61)
4. 15,23,34,54以外の要素の最小値を探す。最小値は46なので、54と46を入れ替える。これ以後、46は固定する。 (15,23,34,46,87,54,61)
5. 15,23,34,46,87以外の要素の最小値を探す。最小値は54なので、87と54を入れ替える。これ以後、54は固定する。 (15,23,34,46,54,87,61)
6. 15,23,34,46,54,87以外の要素の最小値を探す。最小値は61なので、87と61を入れ替える。(15,23,34,46,54,61,87)　要素の最後まで到達し、ソート完了。

挿入ソート

ソート済みの配列の間に新たな要素を挿入することで、並び替えを行う方法です。

(61,15,54,34,87,46,23)という配列を昇順に並べたい時は、

1. 61に15を挿入する。61>15なので15が前にくる。 (15,61,54,34,87,46,23)
2. 54を61と15の間に挿入する。 (15,54,61,34,87,46,23)
3. 34を15と54の間に挿入する。 (15,34,54,61,87,46,23)
4. 87を61の後に挿入する。 (15,34,54,61,87,46,23)
5. 46を34と54の間に挿入する。 (15,34,46,54,61,87,23)
6. 23を15と34の間に挿入する。 (15,23,34,46,54,61,87)　要素の最後まで到達し、ソート完了。

クイックソート

要素の中で基準値(ピボット)を定め、ピボットより大きな値と小さな値の分割を繰り返し、並び替えを行う方法です。

(61,15,54,34,87,46,23)という配列を昇順に並べたい時は、

1. 61をピボットとして、並び替える。 (15,54,34,46,23,61,87)
2. 分割された2つの要素の中でピボットを定める。 (15,54,34,46,23,61,87)
3. それぞれの要素の中で入れ替える。 (15,54,34,46,23,61,87)
4. ピボットを定める。 (15,54,34,46,23,61,87)
5. 要素の中で入れ替える。 (15,34,46,23,54,61,87)
6. ピボットを定める。 (15, 34,46,23,54,61,87)
7. 要素の中で入れ替える。 (15,23,34,46,54,61,87)
8. 分割されたそれぞれの要素が1つなのでソート完了。 (15,23,34,46,54,61,87)

マージソート

ソート前の配列を2つに分割する作業を、1つ1つの要素がバラバラになるまで繰り返します。その後、分割と逆の順序でマージ(結合)作業を行います。この際、大きさに応じて並び替えを行います。

(61,15,54,34,87,46,23)という配列を昇順に並べたい時は、

1. 配列を2つに分割する。 (61,15,54,34),(87,46,23)
2. それぞれの配列を2つに分割する。 (61,15),(54,34),(87,46),(23)
3. それぞれの配列を2つに分割する。 (61),(15),(54),(34),(87),(46),(23)
4. 3で分割したものをマージする。 (15,61),(34,54),(46,87),(23)
5. 2で分割したものをマージする。 (15,34,54,61),(23,46,87)
6. 1で分割したものをマージする。 (15,23,34,46,54,61,87) マージが全て終わったので、ソート完了。

参考URL

アルゴリズム : アルゴリズムとデータ構造
一週間で身につくアルゴリズムとデータ構造|入門編2日目：アルゴリズムの基本