挿入ソート (Insertion Sort)

C 言語による実装

insertionsort.c

/*
  挿入ソート (Insertion Sort):
  挿入ソートはリストの整列済みの部分に対して新たな要素を適切な位置に
  挿入することで整列を行うアルゴリズム.
  整列済みのリストの後ろにいくつかの要素を追加して再び整列させるという
  場合や, 一方の整列済みリストに整列されていない他方のリストを追加しな
  がら整列させたい時に威力を発揮する.
*/

/*
  アルゴリズム分析:
  1. 整列済みのインデックス 'A' を決定する
  2. 'A' の次の要素 'B' を整列されていない部分とする
  3. 'B' を 'A' に挿入する
     ・ 'A' と 'B' の値を比較して 'B' の値が小さければ 'A' と交換する
  4. 'A' と 'B' が整列された部分になる
  5. 'B' の次の要素 'C' を整列されていない部分とする
  6. 整列済みの部分 'A', 'B' に 'C' を挿入する
     ・ 'C' と 'B' の値を比較して 'C' の値が小さければ 'B' と交換する
     ・ 'C' と 'A' の値を比較して 'C' の値が小さければ 'A' と交換する
*/

/*
  注意:
  挿入ソートは常に隣り合う要素で比較, 交換を行う. 交換が発生した場合には
  比較元となる整列されていなかった要素はリストの先頭へ移動 (挿入) される
*/

/*
  特徴:
  挿入ソートは整列されている部分が多ければ多いほど計算量がへり, 処理速度は
  向上する.
  反対に, [昇順に整列されたものを降順に並び替える] というように, 逆順のリスト
  を対象とした場合にもっとも遅くなる.
*/
 
#include <stdio.h>

void swap(int *x, int *y);
void insertionsort(int nums[], int array_size);

int main(void){
  int i;
  
  /* unsorted list */
  int list[10] = {10, 8, 15, 20, 10, 35, 25, 70, 6, 9};
  
  insertionsort(list, 10);
  
  for(i = 0; i < 10; i++){
    printf("%d ", list[i]);
  }
  printf("\n");
  
  return 0;
}

void swap(int *x, int *y){
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

void insertionsort(int nums[], int array_size){
  int i, j;
  
  for(i = 1; i < array_size; i++){
    j = i;
    /* 昇順: > */
    /* 降順: < */
    while( (j > 0) && (nums[j-1] > nums[j]) ){
      swap(&nums[j-1], &nums[j]);
      j--;
    }
  }
}

insertionsort.c の実行結果は:

[cactus:~/code_c/ad]% ./insertionsort
6 8 9 10 10 15 20 25 35 70