C言語とRubyのクイックソート

クイックソートの流れを簡単に説明すると

1. ある適当な値（文字・数）を決めて、それよりも大きいものは後ろへ、小さなものは前へ移動する。
2. 2つに分けたそれぞれのグループの中で、また適当な値を決めて、それよりも大きいものは後ろへ、小さなものは前へ移動する。
3. またそれぞれの...、と1,2の操作を繰り返す。
4. それ以上ブループ分けできなくなったら終了。

本書に載っているC言語による実装を引用する（処理の意図が分かりやすいように、一部コメントは追記した）。

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

#define N 10 // データ件数

int sort[N];

void QuickSort(int bottom, int top, int *data) {
    int lower, upper, div, temp;
    if (bottom >= top) {
        return;
    }

    // 先頭の値を「適当な値」とする (これをピボット、と言う)
    div = data[bottom];

    for (lower = bottom, upper = top; lower < upper;) {
        while (lower <= upper && data[lower] <= div) {
            // ピボットより大きい値を左から探す
            lower++;
        }
        while (lower <= upper && data[upper] > div) {
            // ピボット以下の値を右から探す
            upper--;
        }
        if (lower < upper) {
            // 見つかった値を入れ替え（ピボット以下は前、ピボットより大きい値は後の方へ集まる）
            temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
        }
    }
    // 最初に選択した値を中央に移動する
    temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;

    // ピボットより前部分と後部分を同様にソート
    QuickSort(bottom, upper - 1, data);
    QuickSort(upper + 1, top, data);
}

int main(void) {
    int i;

    srand((unsigned int)time(NULL));

    printf("ソート準備\n");
    for (i = 0; i < N; i++) {
        // ランダムな値を配列に格納
        sort[i] = rand();
        printf("%d ", sort[i]);
    }

    printf("\nソート開始\n");
    QuickSort(0, N - 1, sort);

    for (i = 0; i < N; i++) {
        printf("%d ", sort[i]);
    }
    printf("\nソート終了\n");

    return EXIT_SUCCESS;
}

正直、初見では処理を追って理解するのに少し時間がかかった。

クイックソートをRubyで書くとどうなるのか。

class Array
  def quick_sort
    return self if self.length <= 1
    pivot = shift
    left, right = partition { |e| e < pivot }
    left.quick_sort + [pivot] + right.quick_sort
  end
end

C言語よりも遥かに処理を理解しやすい。人間の頭に優しい。

[4] pry(main)> ary = ('a'..'z').to_a.shuffle
=> ["r", "b", "u", "d", "h", "s", "m", "x", "e", "i", "k", "a", "j", "v", "o", "t", "z", "n", "c", "f", "w", "g", "y", "q", "l", "p"]
[5] pry(main)> ary.quick_sort
=> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

参考：

Rubyでクイックソート - Qiita