ソートアルゴリズム、これだけおさえとく

ソートアルゴリズム習得のPOINT

・ソートにはいろいろなアルゴリズムがあることを知る
・アルゴリズムの実装が必要になったときに調べる、暗記は不要
・アルゴリズムにより効率には天と地ほどの差があることを知る
・アルゴリズム採用時にはワーストケースを考える
・その高速化は本当に意味があるのか、必要なのか考える
・先人の知恵を有効活用する

ソートとは

配列などのデータを何らかの順に並べ変えること。
以下に代表的なソートアルゴリズムを紹介します。
なお、ここではソート対象の要素を左から右へ向かって昇順にソートすることにします。
昇順とは右に行くに従ってだんだん要素の値が大きくなっていくという意味です。

バブルソート

最初の2要素に注目し、左＞右ならひっくり返す、
次は1個ずれた2要素に注目し、左＞右ならひっくり返す・・・を延々と繰り返すと最大の要素が右端に移動。あとは残りの配列に対して同じことを繰り返せばソートが終了します。
小さな値が泡のように左側に移動してくるのが名前の由来みたいです。計算量はO(N^2)。
例) 配列A[6]={3, 2, 5, 4, 1} でソートの動作を確認
→2 3 4 1 ⑤
→2 3 1 ④ ⑤
→2 1 ③ ④ ⑤
→1 ② ③ ④ ⑤
→① ② ③ ④ ⑤
※丸数字はソート完了の意味

シェーカーソート(双方向バブルソート)

バブルソートの改良版。左から右に走査した後、次は右から左に走査。これを繰り返す。
しかしシェーカーソートによって得られる高速化は大したことなく、プログラムは結構複雑になるので実用的ではない。
例) 配列A[6]={3, 2, 5, 4, 1} でソートの動作を確認
→2 3 4 1 ⑤
→① 2 3 4 ⑤
→① 2 3 ④ ⑤
→① ② 3 ④ ⑤
→① ② ③ ④ ⑤
※丸数字はソート完了の意味

(単純)選択ソート

全体でもっとも小さなものを選んで、それを左端にもっていく。
左端に持って行った値はソート済み扱いとする。
未ソートの中でこれを繰り返してすべての数字がソート済みになるまで実行する。
例) 配列A[6]={3, 2, 5, 4, 1} でソートの動作を確認
→① 3 2 5 4
→① ② 3 5 4
→① ② ③ 5 4
→① ② ③ ④ 5
→① ② ③ ④ ⑤
※丸数字はソート完了の意味

挿入ソート

最初は左端の値を一つの要素とみなします。まず、要素全体をソート済みの部分と未ソートの部分に分けます。あとはそのソート済み配列の適切な個所に、未ソートの部分の要素を順次挿入していきます。
例) 配列A[6]={3, 2, 5, 4, 1} でソートの動作を確認
→③ 2 5 4 1
→② ③ 5 4 1
→② ③ ⑤ 4 1
→② ③ ④ ⑤ 1
→① ② ③ ④ ⑤
※丸数字はソート完了の意味

ヒープソート

ヒープ構造の特徴である「根(配列の先頭、N[0])に必ず最大値が来る」という点を利用する｡
続きはWebで。

クイックソート

現在もっとも高速と言われているソート法です。
対象とする配列の中からまず、ピボットと呼ばれる値をひとつ選択します。
そして配列をピボットより小さな要素の配列と大きな要素の配列に分離する。
これを再帰的に繰り返す。計算量はO(Nlog2N)
手順は下記。
1.左端からピボットより大きなデータがないか検索する
2.右端からピボットより小さなデータがないか検索する
3.双方ともに見つかればその2者を交換する
4.上記の操作を左端から検索している添字と右端から検索している添字が衝突するまで繰り返す

マージソート

クイックソートが大きな配列を徐々に分割しながらソートをするのに対し、
マージソートは小さなソート済みの配列を併合しながらソートする方法です。
続きはWebで。

どのソートが一番速いのか

今回紹介するソートについて50000件の
ランダムなデータをソートするのに要した時間が下表です。

アルゴリズム	所要時間(ms)
バブルソート	13,262
シェーカーソート	9,513
選択ソート	5,242
挿入ソート	5,192
ヒープソート	40
クイックソート	24
マージソート	46

POINT
・アルゴリズムにより処理効率に天と地ほどの差がある
・クイックソートでも使い方次第では遅くなることもある（元々ソートされて、かつピボットの選択が左端など）

C言語ではqsort()が用意されてる

数回しか使わないプログラムの処理時間を1分縮めるために何か月もかけた（しかも完成できなかった）という逸話があるみたいです。
また、プログラムを最初に書いている段階では高速化のために凝ったアルゴリズムを採用するより、実装の簡単なアルゴリズムでとにかく書いてしまうことが重要な場合も多いと思います。
ここではそんなときのためにqsortの使用例を紹介します。

void qsort(void *base, size_t num, size_t size, 
           int (*compare)(const void*, const void*))

#include <stdlib.h>

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;// ★b-aにすると降順
}

int main(void)
{
    int data[] = {4, 2, 3, 6, 3, 2, 1, 3, 5, 7};
    int i;
    qsort(data, 10, sizeof(int), compare_int);
    for (i = 0; i < 10; i++) {
        printf("%3d", data[i]);
    }
    printf("\n");
    return 0;
}

実行結果
  1  2  2  3  3  3  4  5  6  7