挿入ソート

Posted on Saturday, September 6th, 2014 17:27:31

挿入ソートとは

今回は人間にとって大変分かりやすいアルゴリズムです。まず、配列の最初の2つを取り出してソートします。次に、3つ目の値をソート済みした2つの値と順番に比較して、適切な位置に挿入します。以降も同様にソート済みの配列の適切な位置に新しい値を挿入していくだけです。

とかいう説明をするとややこしいですが、トランプの大富豪なんかをやる時に、配られた手札を並び替えますよね。多くの人は挿入ソートアルゴリズムによって並び替えると思います。

例えば、4, 3, 10, 7, 8 という5枚の手札が配られたとします。(どんだけ大人数だ) まず、左の 3 と 4 を入れ替えます。

3, 4, 10, 7, 8

次は、10 ですがソート済みの 3 と 4 と比べると今の順序で問題ないのでパスします。まあ、私の場合ここで 10 を右端に持ってきますが。次に 7 を見ると、4 と 10 の間の数値なので、その場所に挿入します。

3, 4, 7, 10, 8

最後は右端の8です。ソート済みの4枚を見ると、 7 と 10 の間なので、その場所に挿入します。

3, 4, 7, 8, 10

これが、挿入ソートアルゴリズムです。

サンプル

ソースプログラム

実行結果

ソート関数の解説

変数i のループで2つ目から最後まで順に処理していきます。処理の内容は、ソート済みの配列に対して適切な位置までスワップを繰り返しています。適切な位置までスワップを繰り返すということは、ソート前のデータが既に整列されていればされているほど、比較回数も交換回数も少なくて済むので高速だということです。

つまり、配列の要素数を n としたとき、最悪計算時間は O(n²) なのに対して、最良計算時間は O(n) となります。また、データが連結リストで格納されている場合は、スワップを繰り返す擬似的挿入ではなく、文字通りの”挿入”を行うことができるため、交換回数を大幅に減少することができます。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

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