ソートのアルゴリズム

http://www.geocities.jp/ky_webid/cpp/library/019.html

ソート関係の関数をいくつか。

その名もsort関数。内部実装としてはクイックソートであることが多いようです。ちなみにC言語にはqsortという標準関数がありましたね。

とりあえず使ってみます。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> data;
    
    data.push_back(4);
    data.push_back(2);
    data.push_back(3);
    data.push_back(1);
    
    // 昇順ソート
    sort(data.begin(),data.end());
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
1
2
3
4

簡単ですね。ただしこのsort関数は安定ソートではないので注意が必要です。

では安定ソートしたい場合はどうするか。stable_sort関数を使います。

使い方はsortとまったく一緒です。

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main () {
    vector<int> data;
    
    data.push_back(4);
    data.push_back(2);
    data.push_back(3);
    data.push_back(1);
    
    // 降順ソート
    stable_sort(data.begin(),data.end(),greater<int>());
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
4
3
2
1

ちなみに降順ソートでやってみました。greaterというのは前にも出てきましたね。これをつかうことで降順にソートすることができます。