第26回、第27回、そして余談2 で、いろいろなソートについて説明してきましたが、今回が最後です。

C言語教室 第26回 - いろいろなソート

C言語教室 第27回 いろいろなソート(続)

C言語教室 余談2 - ソートアルゴリズムを比較してみる

ソートアルゴリズムは実に多くの種類があり、取り上げなかったものもたくさんありますが、今回は最後の大本命、クイックソートを説明します。

クイックソート

クイックソートは、その名前からしても何だか速そうに聞こえますし、データの状態によっては必ずしも最速ではないものの、平均的には最も速いことになっていますし、大抵はライブラリ関数も用意されていて、ソートするといえば何も考えずにクイックソートを使うことが多いです。

クイックソートは、分割統治法と呼ばれる考え方で、データを分割し、それぞれのデータに対して再帰的に処理を進めて、最終的に全体がソートされるというのですが、よくよく考えないと、処理がどう進んでいくか分かりにくい手順でもあります。

分割統治法

何はともあれコードを見てみましょう。

#include <stdio.h>

void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int *arr, int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return (i + 1);
}

void quick_sort(int *arr, int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
  }
}

void print_array(int *arr, int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", *arr++);
  printf("\n");
}

void main() {
  int arr[] = {10, 7, 8, 9, 1, 5};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  print_array(arr, n);

  quick_sort(arr, 0, n - 1);

  printf("Sorted array  : ");
  print_array(arr, n);
}

このデータでは以下の出力が得られます。

Original array: 10 7 8 9 1 5 
Sorted array  : 1 5 7 8 9 10 

partition() では配列内の要素をピボット(基準値)と比較し、ピボットを基準に配列を分割します。ピボットより小さい要素は左側に移動し、ピボットより大きい要素は右側に移動します。この関数はピボットのインデックスを返します。また quick_sort() で、配列を再帰的に分割し、各部分配列をソートします。具体的には、配列の最後の要素をピボットとして選び、分割関数を使用してピボットより小さい要素と大きい要素に分割します。その後、各部分配列に対して再帰的に同じ手順を実行します。

クイックソートでは、再帰呼び出しのために、最悪の場合、要素の数だけ自身を呼び出すことになり、かなりのメモリを消費することになります。行ってみれば処理の回数を取るか、メモリを沢山使うことを選ぶかという選択で、後者の方法を選んでいるということも言えます。ですから、とても大きな配列をソートする場合には、スタックサイズが不足することもありえます。これを回避するのは少しばかり面倒なので、いろいろな工夫が行われるところでもあるのですが、まずはメモリをたくさん使うんだよというところだけは覚えておいてください。

さて、クイックソートはライブラリ関数に用意されています。関数の形式を確認すると何やら不思議な型の引き数が並びます。

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

これはいろいろな型(サイズ)の配列をソートすることが出来るようにするためで、最初の引き数にソートしたい配列の先頭のアドレスを渡し、次の引き数にひとつの要素の大きさを渡します。これで2バイトの値でも8バイトの値でも、この関数が使えるわけです。最後の関数が曲者で、ここで関数ポインタが登場します。

この関数は２つの値の大小を整数で返す関数へのポインタで、値はポインタで渡されます。例えば整数の大小を比べるのであれば、以下の関数を用意して、この関数へのポインタを渡せばよいのです。

int compare(const void *p1, const void *p2) {
  const int a = *((int*)p1);
  const int b = *((int*)p2);
  if ( a == b ) return 0;
  else if ( a < b ) return -1;
  else return 1;
}

必ずしも等号の判定はしなくても動くので、少し端折ることも可能ではあります。また、ここは最適化に大きく関係するので、ちゃんと const をつけた方が効果が出ます。さて、ライブラリ関数を使ってソートするコードを見てみましょう。

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

int compare(const void *p1, const void *p2) {
  const int a = *((int*)p1);
  const int b = *((int*)p2);
  if ( a == b ) return 0;
  else if ( a < b ) return -1;
  else return 1;
}

void print_array(int arr[], size_t size) {
  for (size_t i = 0; i < size; i++)
    printf("%2d ", arr[i]);
  printf("\n");
}

void main() {
  int arr[] = {53, 32, 12, 52, 87, 43, 93, 23};
  const size_t size = sizeof(arr) / sizeof(arr[0]);
  print_array(arr, size);
  qsort(arr, size, sizeof(int), compare);
  print_array(arr, size);
}

※関数ポインタをつかうので、ブラウザ環境は諦めてください。

実行結果は以下です。

53 32 12 52 87 43 93 23
12 23 32 43 52 53 87 93

やはりライブラリを呼んで済ます方が楽ちんです。関数ポインタの便利さが実感できましたか？

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

#C言語 #プログラミング講座 #ソート #クイックソート #関数ポインタ