第26回、第27回でソートについて取りあげたところ、書いたコードがどのアルゴリズムであるのかで大いに盛り上がってしまいました。

毎回、答案を寄せていただいている Akio van der Meer さんが興味深い記事を投稿されたました。

（蛇足編、その３）C言語教室 第26回 - いろいろなソート - バブルソート、選択ソート、挿入ソート、シェルソート、マージソート、クイックソート

教室の方は、まだバブルソートとマージソートしかやっていないのですが、こちらの投稿では、名だたるソートアルゴリズムについて、そのコードと性能についてまとめられています。

ここに至るまでにも、ソースコードをAIに見せて、アルゴリズムの種類を判定させてみたり、交換回数を数えてみたりして、コードからアルゴリズムの種類を判定しようとしているのですが、ループの回し方を変えると、あれあれという動き方をすることもあって、思ったよりも難しいということに気が付きました。

そこで、同じデータに対して、何回の大小比較をし、何回の移し替えをやっているかを数えることで、コードを見なくてもアルゴリズムの判定ができないかと考えて、判定用のコードを書いてみました。ソート関数自身は先の投稿にあったものを少しだけ修正して使わせていただきました。少しばかり長いので、最後にコードは載せますが、悪い癖が出て回数を数えたり、複数の関数を順に呼ぶのに凝ったことをしてしまいました(関数ポインタ使いまくり)。

これで自分で書いた関数も同じように呼び出して回数を数えればいいかもしれないとは思ったのですが、アルゴリズムによっては比較や代入の回数の基準が少し恣意的であることに気が付きました。この場所をうまく処理しないと回数が違ってしまうので、方法としてはもうひとつのところでした。もう少し工夫ができるところにお気づきでしたらご指摘ください。

そうそうソートをビジュアル化した動画を見つけました。お楽しみください(音が出ます)。

15 Sorting Algorithms in 6 Minutes

コードは以下の通り。

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

#define LINES 5
#define COLS 10

int testdata[LINES][COLS] = {
  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
  { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0},
  { 5, 1, 2, 3, 4, 7, 0, 6, 8, 9},
  { 3, 9, 0, 2, 8, 4, 7, 1, 5, 6},
  { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
};

unsigned int move;
void swap(int *x, int *y) {
  move += 2;
  int temp = *x;
  *x = *y;
  *y = temp;
}

unsigned int comp;
int order(int x, int y) {
  comp++;
  return x > y;
}
int(*judge)(int,int) = order;

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

void selection_sort (int array[], size_t size) {
  int min;

  for (int i = 0; i < size - 1; i++) {
    min = i;
    for (int j = i + 1; j < size; j++) {
      if (judge(array[min],array[j])) 
        min = j;
    }
    if (min != i) 
      swap(&array[i], &array[min]);
  }
}

void insertion_sort(int array[], size_t size) {
  for (int i = 1; i < size; i++) {
    if (judge(array[i - 1],array[i])) {
      int j = i;
      int tmp = array[i];
      do {
        array[j] = array[j - 1];
move++;
        j--;
      } while (comp++, j > 0 && array[j - 1] > tmp);
      array[j] = tmp;
move++;
    }
  }
}

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

  for (h = 1; h <= size / 9; h = 3 * h + 1);
  for ( ; h > 0; h /= 3) {   			
    for (i = h; i < size; i++) {
      j = i;
      while ((j > h - 1) && (judge(array[j - h],array[j]))) {
        swap(&array[j - h], &array[j]);
        j -= h;
      }
    }
  }
}

void merge(int array[], int left, int right) {
  int mid, i, j, k;
  int temp[right];
	
  if (left >= right)
    return;
  mid = (left + right) / 2;
  merge(array, left, mid);
  merge(array, mid + 1, right);

  for (i = left; i <= mid; i++) {
move++;
    temp[i] = array[i];
  }
  for (i = mid + 1, j = right; i <= right; i++, j--) {
move++;
    temp[i] = array[j];
  }
  i = left;
  j = right;

  for (k = left; k <= right; k++) {
comp++;
move++;
    if (temp[i] <= temp[j]) {
      array[k] = temp[i++];
    } else {
      array[k] = temp[j--];
    }
  }
}

void merge_sort(int array[], size_t size) {
  merge(array, 0, size-1);  
}

void quick(int array[], int left, int right) {
  int i, j;
  int pivot;

  i = left; 
  j = right;

  pivot = array[(left + right) / 2]; 
  while (1) {
    while (array[i] < pivot) {
      i++;
    }
    while (pivot < array[j]) {
      j--;
    }

    if (i >= j)
      break;

    if (judge(array[i],array[j])) 
      swap(&array[i], &array[j]);

    i++;
    j--;
  }

  if (left < i - 1)
    quick(array, left, i - 1);
  if (j + 1 <  right)
    quick(array, j + 1, right);
}

void quick_sort(int array[], size_t size) {
  quick(array, 0, size-1);
}

void prepare(int *data, int *org, size_t size) {
  for (int i = 0; i < size; i++)
    *data++ = *org++;
  comp = 0;
  move = 0;
}

void result(int work[], size_t size) {
  printf("(%3d|%3d) ", comp, move);
}

void main() {
  size_t datasize = COLS;
  int *work = (int*)malloc(datasize * sizeof(int));

  struct {
    char *name;
    void(*func)(int[],size_t);
  } functbl[] = {
    {"bubble   ", bubble_sort},
    {"selection", selection_sort},
    {"insertion", insertion_sort},
    {"shell    ", shell_sort},
    {"merge    ", merge_sort},
    {"quick    ", quick_sort},
  };
  
  for (int fs = 0; fs < sizeof(functbl) / sizeof(functbl[0]); fs++) {
    printf("%s:", functbl[fs].name);
    for (int i = 0; i < LINES; i++) {
      prepare(work, testdata[i], datasize);
      (*functbl[fs].func)(work, datasize);
      result(work, datasize);
    }
    printf("\n");
  }

  free(work);
}

このデータでの実行結果、数字はそれぞれのデータに対する比較回数と代入回数(交換だと2回分)。

bubble   :( 45|  0) ( 45| 38) ( 45| 22) ( 45| 42) ( 45| 90)
selection:( 45|  0) ( 45| 14) ( 45|  6) ( 45| 14) ( 45| 10)
insertion:(  9|  0) ( 28| 24) ( 20| 17) ( 30| 29) ( 54| 54)
shell    :( 15|  0) ( 29| 38) ( 22| 22) ( 25| 26) ( 21| 26)
merge    :( 34| 68) ( 34| 68) ( 34| 68) ( 34| 68) ( 34| 68)
quick    :(  0|  0) (  7| 14) (  3|  6) (  9| 18) (  5| 10)

ソートに関する良さげなページを見つけたので、貼り付けておきます。

基本的なソートアルゴリズム

基本的なソートアルゴリズム11個まとめ

基本的なソートアルゴリズムまとめて可視化GIFで解説

ヘッダ画像は、Bing Image Creator で作成しました。

#C言語 #プログラミング講座 #ソート #ソート比較