ソートアルゴリズム - 秋田大学ICPC対策室@wiki

ソートアルゴリズム

ソート(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;
    } 
}

比較的有名なソートアルゴリズム

• バブルソート?
• 挿入ソート?
• 選択ソート?
• クイックソート?
• マージソート?

マイナーなソートアルゴリズム?

• ボゴソート?
• ボゾソート?
• シェーカーソート?
• コムソート?
• ノームソート?
• シェルソート?
• 2分木ソート?
• ライブラリソート?
• ヒープソート?
• イントロソート?
• バケットソート?
• 鳩の巣ソート?
• 分布数えソート?
• 逆写像ソート?

...