（蛇足編）C言語教室 第26回 - いろいろなソート - バブルソート、選択ソート、シェルソート

バブルソート、選択ソートの話が盛り上がったので、効果の違いをみてみようと思い立ちました。ついでに、ネットで見つけたシェルソートのアルゴリズムとの違いについてもみていきましょう。

検証プログラム

ランダムに発生させたsize個の配列を作成して、同じものを他に２つコピーして用意しておきます。同じ条件で、バブルソート、選択ソート、シェルソートを実行して、値の交換回数をカウントします。
最後に、並べ替えた結果を比較して、全く同じであることを確認します。

/**********************************************************************
	lesson26-extra　
　　　　　Comparison of bubble sort, selection sort and shell sort algorithms
		by Akio van der Meer

[変更履歴]
 (無印)  記事初投稿時のコード
 r2.2.2 プログラムの引数でサンプル数を指定、引数の妥当性チェック、
　　　　　出力の3桁カンマ編集、乱数のシード値の変更
**********************************************************************/

#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

long int counter;
char e_string[14]; // 編集した文字列

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

  counter++;
}

void bubble_sort (int array[], int array_size) {
  for (int i = 0; i < array_size -1; i++) {
    for (int j = 0; j < array_size - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        swap(&array[j], &array[j + 1]);
      }
    }
  }
}

void selection_sort (int array[], int array_size) {
  for (int i = 0; i < array_size -1; i++) {
    for (int j = i + 1; j < array_size; j++) {
      if (array[i] > array[j]) {
        swap(&array[i], &array[j]);
      }
    }
  }
}

void shell_sort (int array[], int array_size) {
  int i, j, h;

  for (h = 1; h <= array_size / 9; h = 3 * h + 1) {}
  for ( ; h > 0; h /= 3) {   
    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;
      }
    }
  }
}

char * comma_edit(long x) {
  char s_string[11]; // 文字列化した入力数値
  int  ptr_s_string = 0; // s_string[]のポインタ
  int  ptr_e_string = 0; // e_string[]のポインタ
  int  len; // 入力した数値の桁数
  int  dgt; // 一度に処理する桁数

  sprintf(s_string, "%ld", x);

  len = strlen(s_string);
  dgt = len % 3;
  if (dgt == 0) dgt = 3; // 3で割り切れる桁数の場合は、一度に3桁処理する
  if ((dgt == 1) && (x < 0)) dgt = 4; // マイナス符号の直後は、カンマ編集しない

  while (len > 0) {
    for (int i = 0; i < dgt; i++) {
        e_string[ptr_e_string++] = s_string[ptr_s_string++];
        len--;
    }

    if (len > 0) {
      e_string[ptr_e_string++] = ','; // 残りの桁が3桁以上あるので、カンマを追加する
      dgt = 3; // 次回以降は3桁ごとに、処理する
    }
  }

  e_string[ptr_e_string++] = '\0'; // 文字配列の最後にNULLを追加する
  return e_string;
}

int main(int argc, char* argv[]) {
  unsigned int size = atoi(argv[1]);
  
  if (size > 100000) {
    printf("[ERROR] over 100,000 specified.\n");
    exit(-1);
  }  

  if (size == 0) {
    printf("[ERROR] unexpected argument specified.\n");
    exit(-1);
  }  

  int i;

  int* array_1;
  int* array_2;
  int* array_3;
  srand((unsigned int)time(NULL));

  array_1 = (int*)malloc(sizeof(int) * size);
  if (array_1 == NULL) exit(0);

  array_2 = (int*)malloc(sizeof(int) * size);
  if (array_2 == NULL) exit(0);

  array_3 = (int*)malloc(sizeof(int) * size);
  if (array_3 == NULL) exit(0);

  for (i = 0; i < size; i++) {
    array_1[i] = rand() % size;
    array_2[i] = array_1[i];
    array_3[i] = array_1[i];
  }

  printf("Sample size = %s\n", comma_edit(size));
  time_t t1 = time(NULL);


//Bubble sort ---------
  counter = 0;
  bubble_sort(array_1, size);
  time_t t2 = time(NULL);
  printf("  bubble sort ---- # swapped = %s", comma_edit(counter));
  printf(" (elapsed second = %ld)\n", t2 - t1);


//Selection sort --------
  counter = 0;
  selection_sort(array_2, size);
  time_t t3 = time(NULL);
  printf("  selection sort - # swapped = %s", comma_edit(counter));
  printf(" (elapsed second = %ld)\n", t3 - t2);


//Shell sort --------
  counter = 0;
  shell_sort(array_3, size);
  time_t t4 = time(NULL);
  printf("  shell sort ----- # swapped = %s", comma_edit(counter));
  printf(" (elapsed second = %ld)\n", t4 - t3);


//confirmation of results ----
  int res = 0;
  for (i = 0; i < size; i++) {
    if (array_1[i] != array_2[i]) {
      printf("(array_1[%d] = %d) is NOT equal to array_2\n", i, array_1[i]);
      res++;
    }
    if (array_1[i] != array_3[i]) {
      printf("(array_1[%d] = %d) is NOT equal to array_3\n", i, array_1[i]);
      res++;
    }
  } 

  if (res == 0) {printf("each sorted results are same.\n");}


  free(array_1);
  free(array_2);
  free(array_3);

  return 0;
}

lesson26.r2.2.2.c

4.33 KB

ファイルダウンロードについて

ダウンロード

実行結果例

jm3nrhMac-mini-:c akio$ ./a.out 100
Sample size = 100
  bubble sort ---- # swapped = 2,514 (elapsed second = 0)
  selection sort - # swapped = 1,949 (elapsed second = 0)
  shell sort ----- # swapped = 484 (elapsed second = 0)
each sorted results are same.

100個のサンプルで、バブルソートは2,514回、選択ソートは1,949回、シェルソートは484回、値の置換が発生しています。

jm3nrhMac-mini-:c akio$ ./a.out 10000
Sample size = 10,000
  bubble sort ---- # swapped = 25,214,872 (elapsed second = 0)
  selection sort - # swapped = 18,549,387 (elapsed second = 0)
  shell sort ----- # swapped = 161,092 (elapsed second = 0)
each sorted results are same.

10,000個のサンプルだと、バブルソート（25,214,872）と選択ソート（18,549,387）で1.34倍、シェルソート（161,092）では156倍もの差が出ました。わーお。

jm3nrhMac-mini-:c akio$ ./a.out 100000
Sample size = 100,000
  bubble sort ---- # swapped = 2,497,088,639 (elapsed second = 24)
  selection sort - # swapped = 1,834,673,614 (elapsed second = 23)
  shell sort ----- # swapped = 2,813,337 (elapsed second = 0)
each sorted results are same.

100,000個のサンプルだと、バブルソート（2,497,088,639）と選択ソート（1,834,673,614）で1.36倍、シェルソート（2,13,337）では888倍もの差が出ました。
バブルソートと選択ソートでは、置換数の比率は大体1.3-1.4 対 1程度で、サンプル数増加による変化は緩やかですが、バブルソートとシェルソートは比率が大きくなります。

これくらいになると流石に、実行時間の差が大きく出てきますね。

※サンプル数を実行時の引数で受け取るようにするにはどうするんだったっけ？これからちょっと外出なので、帰ってから考えます。

ここまで読んでいただき、有難うございました。