Help us understand the problem. What is going on with this article?

C言語でシェルソート

More than 1 year has passed since last update.

シェルソートとは

挿入ソートの改良版。挿入ソートを何度か繰り返すことで高速化を実現

手順:
  1. 適当な間隔$h$を決め、この間隔だけ離れた要素同士だけで挿入ソートを行う。
  2. 間隔$h$を少し狭めて、同様にその間隔だけ離れた要素同士だけで挿入ソートを行う。
  3. これを繰り返し、最後に$h=1$で挿入ソートを行う。
なんで速くなるのか:
  • $h=1$の時点で、データ全体がかなり整列済み
  • 挿入ソートは、整列済みの部分が多いほど高速になる
間隔hについて:
  • 一般的には$h_{n+1}=3h_n+1$を使う。
    • これがいいっていう証明は困難
    • ただし、例えば$h=4,2,1$とすると偶数同士、奇数同士の要素で組を作ってしまうからよくない(ので、$3h+1$を使う)
    • 具体的には$h=1,4,13,40,121,\cdots$
  • 大体、要素数$/9$を超えないように$h$を選ぶ
    • 要素数が$100$の時に$h=40$にすればいいかというと、そうでもない
    • あまりにも遠く離れた要素同士のソートは効果が薄い

サンプルコード

ここでは、int型の配列を、シェルソートを用いて整列する。
下の例では要素数が10個しかないのでただの挿入ソートになってる

shell_sort.c
#include<stdio.h>

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

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

/* シェルソート */
void shell_sort (int array[], int array_size) {
  int i, j, h;

  for (h = 1; h <= array_size/9; h = 3*h + 1);   // 間隔hを決める
  for ( ; h > 0; h /= 3) {   // hを狭めていく
    /* 以下、挿入ソートとほぼ同じ */
    for (i = h; i < array_size; i++) {
      j = i;
      while ((j > h - 1) && (array[j-h] > array[j])) {
        swap(&array[j-h], &array[j]);
        j -= h;
      }
    }
  }
}

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");

  shell_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

性能

  • 挿入ソートでは、最悪$O(n^2)$
  • シェルソートの場合、$h$個ずつ飛ばして探すので、比較回数が少なく、一度の移動量が大きい
  • $n^{3/2}$以上に比較されることはない
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした