アルゴリズムとは主に数学やコンピュータの分野で使われる用語で、簡単に定義すると問題を解くための手順になります。つまり、ある目的を達成するために作られたコンピュータ・プログラムもまたアルゴリズムだと言えますね。今回はこのようなコンピュータ・プログラムを作る上で、知っておきたい有名なアルゴリズムを整理してみたいと思います。アルゴリズムの表現方法は様々ですが、読みやすくて動きも確認できるC言語を使うことにしました。

このポストも多分随時更新される予定です。

バブルソート

最初は実装が最も簡単なバブルソートから紹介します。全ての要素を隣接する要素と比較し、順番が逆であれば要素を入れ替える仕組みです。数を昇順にソートする場合、各ループで一番大きい数が最後に配置されるようになります。簡単ですが、比較と交換処理が多いため、効率は一番低いソートのアルゴリズムとなります。

#include <stdio.h>

int main(void) {
  int i, j, tmp;
  int ary[5] = {3, 5, 1, 4, 2};
  for (i = 0; i < 5; i++) {
    for (j = 0; j < 5 - i; j++) {
      if (ary[j] > ary[j + 1]) {
        tmp = ary[j];
        ary[j] = ary[j + 1];
        ary[j + 1] = tmp;
      }
    }
  }
  for (i = 0; i < 5; i++) {
    printf("%d  ", ary[i]);
  }
  return 0;
}
1  2  3  4  5

選択ソート

バブルソートと同じく実装が簡単なソートの一つです。バブルソートは隣接する全ての要素を比較しましたが、選択ソートでは最小値または最大値を配列の中で探索し、各ループごとに値を入れ替える仕組みとなります。入れ替えの処理がバブルソートより少ないので、選択ソートの方が少し早いソートとなります。

#include <stdio.h>

int main(void) {
  int i, j, min, tmp;
  int ary[5] = {3, 5, 1, 4, 2};
  for (i = 0; i < 5; i++) {
    min = i;
    for (j = i + 1; j < 5; j++) {
      if (ary[min] > ary[j]) {
        min = j;
      }
    }
    tmp = ary[i];
    ary[i] = ary[min];
    ary[min] = tmp;
  }
  for (i = 0; i < 5; i++) {
    printf("%d  ", ary[i]);
  }
  return 0;
}
1  2  3  4  5

挿入ソート

実装は簡単ですが、仕組みはバブルソートや選択ソートより複雑です。バブルソートと選択ソートは各ループで必ず1回以上の入れ替え処理が必要でしたが、挿入ソートは既にソートができている場合、入れ替え処理を行いません。説明よりも直接動作を確認する方が分かりやすいと思いますので、ループごとに出力処理を行いました。

#include <stdio.h>

int main(void) {
  int i, j, k, tmp;
  int ary[5] = {3, 5, 1, 4, 2};
  for (i = 0; i < 4; i++) {
    j = i;
    while (j >= 0 && ary[j] > ary[j + 1]) {
      tmp = ary[j];
      ary[j] = ary[j + 1];
      ary[j + 1] = tmp;
      j--;
    }
    for (k = 0; k < 5; k++) {
      printf("%d ", ary[k]);
    }
    printf("\n");
  }
  return 0;
}
3 5 1 4 2 
1 3 5 4 2 
1 3 4 5 2 
1 2 3 4 5 

クイックソート

一般的によく使われるソートの一つで、効率も良く名前通りに早いソートですが、データの並び順によっては挿入ソートよりも遅い時もあります。クイックソートはピボットという適当な数を選択して、ピボットより小さい数をピボットの前方に、大きい数を後方に移動して、二分割されたデータをソートします。より理解を深めるために、データ「3 5 4 1 2」のソートを例にします。

  1. 3をピボットとし、3の後方を探索します。
  2. 3より小さい1を発見したので、5と入れ替えます。
  3. データは「3 1 4 5 2」になりました。
  4. 続いて3より小さい2を発見したので、4と入れ替えます。
  5. データは「3 1 2 5 4」になりました。
  6. ピボットを最後に入れ替えした2と入れ替えます。
  7. データは「2 1 3 5 4」になりました。
  8. 新しく3をピボットに設定します。
  9. 3の前方と後方を二分割して同じ手順でソートします。

下記のプログラムでの変数runnerは探索対象のデータを最後まで探索するための変数で、chaserはピボットより小さい数が見つかった時にインクリメントされる変数です。上記の手順①の数5と、手順②の数4を指している変数だと理解してください。

#include <stdio.h>

void quickSort(int left, int right, int* ary) {
  int pivot = left;
  int chaser = left;
  int runner, tmp;
  
  if (left < right) {
    for (runner = left + 1; runner <= right; runner++) {
      if (ary[runner] < ary[pivot]) {
        chaser++;
        tmp = ary[chaser];
        ary[chaser] = ary[runner];
        ary[runner] = tmp;
      }
    }
    tmp = ary[pivot];
    ary[pivot] = ary[chaser];
    ary[chaser] = tmp;
    
    pivot = chaser;
    
    quickSort(left, pivot - 1, ary);
    quickSort(pivot + 1, right, ary);
  }
}

int main() {
  
  int ary[5] = {3, 5, 4, 1, 2};
  quickSort(0, 4, ary);
  for (int i = 0; i < 5; i++) {
    printf("%d ", ary[i]);
  }
  return 0;
}
1  2  3  4  5