効率よくデータを並べ換える方法を勉強してみた!

プログラムを開発していて、配列はよく使うが、効率よく並べ換えるアルゴリズムに「クイックソート」がある。
アルゴリズムは知っているが、プログラムにおこすとなると少し難易度が上がる。

「クイックソート」アルゴリズムとは?

クイックソートは、配列を整列するアルゴリズムの一種。
概要は、
配列の適当な要素を基準値にして、より小さい要素が前、より大きい要素が後ろになるように移動する。
基準値の前側の部分配列と、後ろ側の部分配列で、同じ処理を繰り返し行う。
である。

プログラムに落とし込むのは少し困難

クイックソートのプログラムを書くポイントは、基準値との大小関係において、配列を2つの部分配列に分けることにあるが、
これだけでプログラムに表現していくことは困難。よって、ここではこの書き方を習得していく。

書き方には複数のバリエーションがあるが、ここでは簡単な方法を書く。

そのために…

  • 適当な要素とは何番目の要素なのか?
  • 前側や後ろ側に移動するにはどうしたらよいか?
  • 基準値と同じ値の要素の処理はどうすればいいか?

という疑問が残る

これらの疑問を解決しよう!

適当な要素とは?

配列の先頭の要素を基準値にすればいい!!
残りの"要素を先頭+1"(先頭の次)、および末尾から1つずつチェックして、大小関係に応じて両者を入れ替えれば、要素の移動ができる。
この際に「より小さい」「より大きい」ではなく。「以下」「以上」で比較すれば、基準値と同じ値の要素も処理できる。

変数leftは、配列の要素を先頭+1からたどるループカウンタ。変数rightは、配列の要素を末尾からたどるループカウンタ。

ループの終了条件は、"left>= right"となる。
"left > right"ならチェックが終わっているが、最終的にleftとrightが同じ要素を示す場合もあり得るため、left>=rightという終了条件になる。

処理の最後に、rightが示す要素と基準値を入れ替えることにも注意。

ループ終了時のrightは、基準値以下の要素を指す。基準値は、rightが指す要素より大きい場合があるので入れ替える。

この手順を"arrangerArray"関数にまとめると以下のようになる。

あとでクイックソートを行う際に、繰り返し適応するので、部分配列の先頭の要素を引数"head"、末尾の要素を引数"tail"で指定する。

int arrangerArray(int a[], int head, int tail) {
    int pivot, left, right, temp;

    pivot = a[head];    //基準値
    left = head + 1;    //先頭+1からたどるループカウンタ
    right = tail;       //末尾からたどるループカウンタ

    //大小関係に応じて要素を入れ替える
    while(-1) {
        //配列を先頭+1からたどる
        while (left < tail && pivot > a[left]) left++;

        //配列の末尾からたどる
        while (pivot < a[right]) right--;

        //ループの終了
        if (left >= right) break;

        //leftとrightが刺す要素を入れ替える
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;

        //次の要素チェックに進む
        left++;
        right--;
    }

    //最後に基準値とrightが指す要素を入れ替える
    a[head] = a[right];
    a[right] = pivot;

    //部分配列を区切る要素の番号を返す
    return right;
}

クイックソートを行う関数を作成してみる

部分配列に繰り返しarrangeArray関数を適応する処理は、再帰呼び出しを使って書くと容易。

quickSort関数の引数startとendには、ソートを行う配列の先頭と末尾の要素番号を指定する。
最初にquickSort関数を呼び出すときには、これらの引数に配列全体の先頭と末尾の要素番号を指定する。
quickSort関数が再帰呼び出しされる時、これら引数に部分配列の先頭と末尾の要素b何号が指定される。

void quickSort(int a[], int start, int end) {
    int p;  //部分配列を区切る要素番号

    //要素が2つ以上ある配列なら処理を行う
    if (start < end) {
        //基準値と大小関係に応じて2つの部分配列に分ける
        p = arrengeArray(a, start, end);

        //前側の部分配列に同じ処理を適応する
        quickSort(a, start, p - 1)

        //後側の部分配列に同じ処理を適応する
        quickSort(a, p + 1, end);
    }
}

あらかじめ"arrangeArray"関数を作っておいたので、quickSort関数を作成したため、
"quickSort"関数の処理をスッキリ書けた。

"arrangerArray"関数で行なっている処理が、クイックソートのポイント。