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

配列であるとかリストであるとかに格納された多くのデータを処理する時に、その順序を何らかの規則で並べ替えておきたいことがあります。例えば数字のデータであれば小さい数字から大きな数字への順にするとかということですね。このように並べ替えることを「ソート」と呼びます。

ソートには代表的なアルゴリズムがいくつかあり、種類によって必要なメモリの量と処理にかかる時間が知られています。代表的なアルゴリズムとして、

• バブルソート

• シェルソート

• マージソート

• クイックソート

などがあります。

ソート

ソート - Wikipedia

ソートアルゴリズムは、いろいろなプログラミング言語の演習でだいたい出てきますし、やったやったと思い出す方も多いでしょう。しかしながら実際には大抵はライブラリ関数を呼べば済んでしまうので「どうやったっけ？」と、中身を覚えていない人も多いかもしれません。それぞれのソートの手順は、なかなか込み入っているのですが、一番手軽で余分なメモリも使わないのがバブルソートです。

バブルソート

バブルソート - Wikipedia

隣同士の大小関係を比較して、その結果が求める順序でなければ値を交換していくことで、全体をソートします。どうしてバブルという名前が付いているかは、不思議といえば不思議ではあるのですが、小さい順に並べ替える時に、後ろの方に小さいものがあると、その値がソートが進むに従って前の方にひとつずつ移動しているところが、泡が登っていくように思えたのでしょう。

#include <stdio.h>

void bubble_sort(int *array, unsigned int size) {
  for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        int temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

void main() {
  int data[] = {5, 3, 1, 2, 4};
  unsigned int size = sizeof(data) / sizeof(data[0]);

  bubble_sort(data, size);

  for (int i = 0; i < size; i++) 
    printf("%d ", data[i]);
  printf("\n");
}

実行すると、以下のように並べられ変えた出力が得られます。

1 2 3 4 5 

※ブラウザ環境でbubble_sortの最初の引き数の型を int[] にすると値が参照ではなくてコピーされるようで、思ったとおりに動作しませんので、ご注意を。

さて、大きい順に並べたい時はどうすれば良いのでしょうか。bubble_sort関数内で大小比較を行っている比較を “>” から “<” に変えれば良いだけです。今回は値の比較なので簡単ですが、比較すべきデータが単純に比較できないような型のこともあるので、このif文が肝になるのですね。

そこで、この比較関数を bubble_sort から追い出してしまいましょう。ここで前回に学んだ関数ポインタを使います。※関数ポインタを使うコードはブラウザ環境では動作しません。

#include <stdio.h>

int compare_value1(int i, int j) {
  return i > j;
}

int compare_value2(int i, int j) {
  return i < j;
}

typedef int(*FUNC)(int, int);

void bubble_sort(int array[], unsigned int size, FUNC f) {
  for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size - i - 1; j++) {
      if (f(array[j],array[j + 1])) {
        int temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

void main() {
  int data[] = {5, 3, 1, 2, 4};
  unsigned int size = sizeof(data) / sizeof(data[0]);
  int i;

  bubble_sort(data, size, compare_value1);

  for (i = 0; i < size; i++) 
    printf("%d ", data[i]);
  printf("\n");

  bubble_sort(data, size, compare_value2);

  for (i = 0; i < size; i++) 
    printf("%d ", data[i]);
  printf("\n");
}

ソート済みのデータを再利用してしまっていますが、そこは勘弁してください。

1 2 3 4 5 
5 4 3 2 1

これで小さい順でも大きい順でも同じソート関数を使い回すことができるようになるのです。

課題
文字列の配列をバブルソートで並べ替える関数を書いてください。文字列の大小比較は strcmp を使ってください。なお、文字列全体を入れ替えながらソートすると大変なので文字列へのポインタの配列を用意して、これをソートするようにしてください。

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

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