【C言語】挿入法（又は挿入ソート）による配列データの整列

ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム（ソート）の実装があります。

この記事では、挿入法（挿入ソートとも呼ばれる）を用いた配列データの整列をプログラムに実装する方法について解説しています。

挿入法（挿入ソート）の概要

プログラムを実装する前に、挿入法（又は挿入ソート）についての簡単な説明を行います。

選択法とは、配列データの要素を整列させる整列アルゴリズム（ソート）の一つです。

アルゴリズム

挿入法（挿入ソート）では、整列対象の配列の要素を順にチェックし、それぞれの要素を最適な位置に挿入することで配列内の要素を整列させます。

なお、要素の挿入を行うには他の要素を一つ分ずらす作業が必要です。

計算量

対象の配列の長さをNとすると、挿入法では1、2…N-1番目の要素の挿入に際してそれぞれ最大で1、2…N-1回他の要素をずらす操作が必要です。

比較を行う回数の合計は(N(N-1)/2)回となり、O記法での計算量はO(N^2)となります。

ただし、入力配列が整列された状態に近い場合は他の要素をずらす操作も少なくなり、効率よく処理を行うことが可能です。

実際にプログラムを作成してみる

早速ですが、実際にプログラムを作成していきます。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。使用する言語はC言語です。

#include <stdio.h>

int main(void){
  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n, i, j, temp;

  /* 整列前のデータを表示する */
  printf("---insertion sort---\nBefore : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  /* 挿入法（挿入ソート）を用いてデータを整列する */
  i = 1;
  while(i < n){
    temp = data[i];
    j = i - 1;
    while(j >= 0 && temp < data[j]){
      data[j+1] = data[j];
      j = j - 1;
    }
    data[j+1] = temp;
    i = i + 1;
  }

  /* 整列後のデータを表示する */
  printf("\nAfter  : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

---insertion sort---
Before : 9 8 7 6 5 4 3 2 1 
After  : 1 2 3 4 5 6 7 8 9 

この出力結果から無事に挿入法（挿入ソート）が実装できていることがわかります。

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】