秋田大学ICPC対策室@wiki

ソートアルゴリズム

最終更新：2012年02月09日 17:44

akitaicpc

- view

メンバー限定登録/ログイン

ソートアルゴリズム

ソート(sort)とは、データの集合を一定の規則に従って並べることのことです。日本語では整列(せいれつ)といいます。
単にソートというと、値を小さい順に並べる昇順（しょうじゅん、ascending order）を指すことが多いみたいです。
その反対に値を大きい順から並べることを降順（こうじゅん、descending order）といいます。

C++では<algorithm>ヘッダをインクルードすることでsort関数を使えるので、便利です。
つまりソートのアルゴリズムを知らなくてもソートできるということです。
しかし、ソートのアルゴリズムを知りたい人もいると思うので、
各ソートのアルゴリズムとコードを載せておきます。

例えばvector<int> vc;に対してvcの要素のすべてを昇順にソートしたいなら

sort( vc.begin() , vc.end() );

と書くだけでソートが完了します。
数値だけでなく、文字列(std::string)であれば辞書順にソートされます。

次がソートの例です。

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

int main(){
    int n,a;
    vector<int> vc;

    cin >> n;
    for(int i=0 ; i<n ; i++ ){
        cin >> a;
        vc.push_back( a );
    }
    sort( vc.begin() , vc.end() );
    cout << "ソートしました" << endl;
    for(int i=0 ; i<vc.size() ; i++ ){
         cout << "a[" << i << "] : " << a[i] << endl;
    } 
}