「ソートアルゴリズム」の編集履歴（バックアップ）一覧に戻る

ソートアルゴリズム - (2011/02/12 (土) 19:30:38) のソース

*ソートアルゴリズム

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


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

#region(open, 説明)
例えば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;
     } 
 }
#endregion

***比較的有名なソートアルゴリズム
-[[バブルソート]]?
-[[挿入ソート]]?
-[[選択ソート]]?
-[[クイックソート]]?
-[[マージソート]]?

***マイナーなソートアルゴリズム
-[[ボゴソート]]?
-[[ボゾソート]]?
-[[シェーカーソート]]?
-[[コムソート]]?
-[[ノームソート]]?
-[[シェルソート]]?
-[[2分木ソート]]?
-[[ライブラリソート]]?
-[[ヒープソート]]?
-[[イントロソート]]?
-[[バケットソート]]?
-[[鳩の巣ソート]]?
-[[分布数えソート]]?
-[[逆写像ソート]]?












...