【アルゴリズム解説】挿入ソートとは

今回は、アルゴリズムの整列問題「挿入ソート」について書き溜め
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

概要

挿入ソート

ソート済み枠を右に拡大していく

挿入ソートとは、ソート(整列問題)に関するアルゴリズムの一つです。
整列してある配列に追加要素を適切な場所に挿入して整列させていきます。

左からソート済みの要素数を増やしていく感じ。

挿入ソートアルゴリズム

挿入ソートのアルゴリズムはWikipediaを参照する。

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。
次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。
この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。
このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

名著「アルゴリズムイントロダクション」では挿入ソートの例として
トランプの手札の並び替えを挙げていた。

挿入ソートの計算量は

データ数nのときのアルゴリズム計算量はO(n^2)である。

O(n^2)なので遅いアルゴリズムではあるが、
バブルソートより比較回数の面で高速である。

挿入ソートの改良版として、「シェルソート」がある。

挿入ソートをPython3で実装する

挿入ソートをPython3実装すると下記のようになる。

arr = [8, 3, 4, 10, 2, 7, 5, 6];
print(arr)
print("====START====")
i = 1
while i < len(arr):
  j = i-1
  x = arr[i]
  while (j >= 0 and arr[j] > x):
    arr[j+1] = arr[j]
    j -= 1
  arr[j+1] = x
  i+=1
print("====END====")
print(arr)

arr = [8, 3, 4, 10, 2, 7, 5, 6];

print(arr)

print("====START====")

i = 1

while i < len(arr):

j = i-1

x = arr[i]

while (j >= 0 and arr[j] > x):

arr[j+1] = arr[j]

j -= 1

arr[j+1] = x

i+=1

print("====END====")

print(arr)

(*天才御仁方による指摘はいつでも受け付けている)

挿入ソートをJavaで実装する

挿入ソートをJava実装すると下記のようになる。

class InsertionSort {
  public static void main(String[] args){
    int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };
    System.out.println("start");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);
    System.out.println("");

    for (int i=1; i< arr.length; i++) {
        int j;
        int x=arr[i];
        for (j= i-1; j>= 0 && arr[j]>x; j--){
            arr[j+1]= arr[j];
        }
        arr[j+1]=x;
    }
    System.out.println("");
    System.out.println("end");
    for (int i=0; i<arr.length; i++) System.out.print(arr[i]);
    System.out.println("");
  }
}

class InsertionSort {

public static void main(String[] args){

int[] arr = { 8, 3, 4, 10, 2, 7, 5, 6 };

System.out.println("start");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

System.out.println("");

for (int i=1; i< arr.length; i++) {

int j;

int x=arr[i];

for (j= i-1; j>= 0 && arr[j]>x; j--){

arr[j+1]= arr[j];

}

arr[j+1]=x;

}

System.out.println("");

System.out.println("end");

for (int i=0; i<arr.length; i++) System.out.print(arr[i]);

System.out.println("");

}

(*天才御仁方による指摘はいつでも受け付けている)

挿入ソートを説明しプログラムを書いてください。

さて、先程の説明を読んだ人は、挿入ソートを説明できますね。
余裕の有る方は、好きな言語で挿入ソートを実装してみてください。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

じゃあね〜〜〜。