クイックソート C/C++ Trackback() Comment(0)

よく使うクイックソートのプログラムを一応張っておく。もう憶えたけど念のため。

void QuickSort(int data[], const int low, const int high){
    if(low < high){
        // ピボットの決定
        int x = (data[low] + data[high] + data[(low+high)/2])/3;

        int left = low - 1, right = high + 1;
        while(left <= right){
            while(data[++left] < x);
            while(data[--right] > x);
            if(left < right) Swap(&data[left], &data[right]);
        }
        QuickSort(data, low, right);
        QuickSort(data, left, high);
    }
}

アルゴリズムは「クイックソート：アルゴリズム」に分かりやすい説明がある。

C++ならSTLのalgorithmを利用したほうが早い。

#include <algorithm>

int main(){
    int array[10] = { 1, 6, 4, 3, 5, 9, 8, 2, 7, 0};
    std::sort(array, array+10);
    for(int i = 0; i < 10; ++i){
        std::cout << array[i] << ", ";
    }
    std::cout << std::endl;
    return 0;
}

ちなみに、降順にソートするには、

sort(array, array+10, greater<int>());

のようにすればいいらしい（参考）。