シェルソート (Shell Sort)

C 言語による実装

shellsort.c

/*
  シェルソート (Shell Sort):
  シェルソートは挿入が改良された整列アルゴリズム.
  リストにおいて予め離れている要素を交換しておき, 最終的に挿入ソートを
  実行する.
  挿入ソートが整列済みのリストに強いことを利用した効率の良い整列アルゴリズム.
*/

/*
  アルゴリズム分析:
  挿入ソートでは隣り合う要素で比較, 交換が行われる, シェルソートは H ずつ離れた
  要素を [比較/交換]をする.
  H - ソートとも言える.
  シェルソートでは H の数を小さくしてゆくことで最終的に単純な挿入ソート (H = 1)
  になる頃には [ほぼ整列している] 状態が出来上がっているのでもう一回 H = 1 の
  挿入ソートを実行すれば, 完全に整列できる.
*/

/*
  **********************************************************
  H - ソート の H を表しているのが Decrement である.
  Decrement は (4, 2, 1), (1), (0), と 減少するので, 注意し
  なければならない. H = 1 を 2 回実行することにも要注意!!!!!
  **********************************************************
*/
 
#include <stdio.h>

void shellsort(int nums[], int array_size);

int main(void){
  int i;
  
  /* unsorted list */
  int list[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
  
  shellsort(list, 9);
  
  for(i = 0; i < 9; i++){
    printf("%d ", list[i]);
  }
  printf("\n");
  
  return 0;
}

void shellsort(int nums[], int array_size){
  int i, j;
  int decrement;
  int temp;

  decrement = 4;
  while(decrement > 0){
    for(i = 0; i < array_size; i++){
      j = i;
      temp = nums[i];

      /* 昇順: > */
      /* 降順: < */
      while( (j >= decrement) && (nums[j-decrement] > temp) ){
	nums[j] = nums[j-decrement];
	j -= decrement;
      }
      nums[j] = temp;
    }
    if( (decrement/2) != 0 )
      decrement = decrement / 2;
    else if(decrement == 1)
      /* 終了条件として H = 1 を 第 2 回目実行したら decrement = 0 となる */
      decrement = 0;
    else
      /* H = 1 を 実行してから 第 2 回目 H = 1 を実行し始める */
      decrement = 1;
  }
}

shellsort.c の実行結果は:

[cactus:~/code_c/ad]% ./shellsort
1 2 3 4 5 6 7 8 9