【C言語】シェルソートによる配列データの整列

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

この記事では、シェルソートを用いた配列データの整列をプログラムに実装する方法について解説しています。

シェルソートの概要

プログラムを作成する前に、シェルソートについての簡単な説明を行います。

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

アルゴリズム

シェルソートのアルゴリズムは挿入ソートという別の整列アルゴリズムが基になっています。

挿入ソートについては以下の記事で解説しているので参考にして下さい。

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

挿入ソートでは、「各要素を整列が完了した領域の適切な位置に挿入する」という操作を行い、対象の配列が整列された状態に近い時に効率が良くなるという特徴があります。

シェルソートはこの特徴を利用し、対象の配列を大まかに整列された状態にしてから徐々に完全な整列状態に近づいていきます。

具体的には、対象の配列から一定間隔で抜き出した要素間で挿入ソートによる整列を行い、要素を抜き出す間隔を狭めながらこれを繰り返します。

なお、要素を抜き出す間隔stepは互いに素であると効率が良いとされており、一般的にstep=step*3+1の式が用いられるケースが多いです。

計算量

シェルソートの計算量は配列から要素を抜き出す間隔stepの決め方に依存しています。

例えば、stepの値をstep=step*2+1の式で求める場合はO記法で計算量がO(N^1.5)程度、step=step*3+1の場合はO記法で計算量がO(N^1.2)程度です。

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

前述のアルゴリズムに従ってプログラムを作成します。

プログラム作成の手順

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

実装例

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

#include <stdio.h>

void shell_sort(int data[], int n){
  int i, j, step, temp;
  step = 1;
  while(step < n/9){
    step = step * 3 + 1;
  }
  while(step > 0){
    i = step;
    while(i < n){
      temp = data[i];
      j = i - step;
      while(j >= 0 && temp < data[j]){
        data[j + step] = data[j];
        j -= step;
      }
      data[j + step] = temp;
      i++;
    }
    step /= 3;
  }
}

int main(void){

  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n;

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

  /* シェルソートを用いてデータを整列する */
  shell_sort(data, n);

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

  return 0;
}

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

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

この出力結果から無事にシェルソートが実装できていることがわかります。

おすすめの記事

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

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