C言語で挿入ソート

挿入ソートとは

先頭からi番目までが整列済みの時、i+1番目の要素を、正しい位置に挿入する。
整列済みのデータに新しいデータを追加し、再び整列するときなどに便利。

サンプルコード

ここでは、int型の配列を、挿入ソートを用いて小さい順に並べ替える。

insertion_sort.c

#include<stdio.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/* 挿入ソート */
void insertion_sort (int array[], int array_size) {
  int i, j;

  for (i = 1; i < array_size; i++) {   // 先頭から順にソート
    j = i;
    while ((j > 0) && (array[j-1] > array[j])) {   //整列済みの場合は処理しない
      swap(&array[j-1], &array[j]);   // 整列されていない要素を交換
      j--;
    }
  }
}

int main (void) {
  int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int i;

  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  insertion_sort(array, 10);

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  return 0;
}

実行結果

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

性能

• 最悪の場合：逆順にソート済み
  • while文の比較回数：約$n^2/2$
  • while文の実行回数：約$n^2/4$
  • 比較+実行=$O(n^2)$
• 最善の場合：ほぼ整列済み
  • while文の比較回数：$n-1$
  • while文の実行回数：$0$
  • 計算量はほぼ線形時間$O(n)$