Team TripleFalcon. http://www.triplefalcon.com/

概要

 データを小さい順、または大きい順に並べ替えることを整列(sort) といいます。ソートともいいます。 日本語でも、ソートという言い方の方が多いと思われます。データをソートする場合、データ同士の比較を行うソートと比較を行わないソートがあります。

 ソートは、重要性が高い処理であるため、非常に多くのアルゴリズムが提案されています。また、下記のアルゴリズムも調査すると様々な変種が存在することがわかります。

 比較によるソートは、最も速く実装できた場合比較回数のオーダーを最悪でも O(nlogn) に出来ます。

 以下に、比較を行う有名なアルゴリズムを列挙しました。

名称 計算時間 安定 概要
単純挿入法 O(n2) 少ないデータ、ほぼソートの終わったデータに有効
単純選択法 O(n2) 少ないデータ、ほぼソートの終わったデータに有効
バブルソート O(n2) 隣同士の比較、交換だけでソートする
シェルソート O(n3/2) × 計算量がまだ研究されている
ヒープソート O(nlogn) × どんな状況でもO(nlogn)で応用範囲が広い
マージソート O(nlogn)

分割統治法を応用:
シーケンシャルアクセスメディアに有効
クイックソート O(nlogn) ×

分割統治法を応用:
ソートされてないデータに有効

 上記計算時間は、最悪の時間量です。(クイックソートは平均の計算時間です。)クイックソートは、平均的に最も高速なソートでありながら、最悪では O(n2) の時間量になる可能性があります。

 以下では、n個の data 型配列 D[0],D[1],D[2], ... ,D[n-1] が定義されているとします。

 data 型に、全順序比較演算子 < が定義されているものとします。

Team TripleFalcon. http://www.triplefalcon.com/

単純挿入法

 最も基本的な方法です。ほぼ並べ替えが終わっているデータの場合は、おそらく他のどの方法よりも速くソートできます。 しかし、n データの単純挿入法による最悪の時間量は O(n2) です。

 アルゴリズムは、配列 D 上でセパレータ変数 s を 1 個ずつ後ろへ動かします。

 s より前の部分 D[0...s-1]既ソート、後の部分 D[s...n-1]未ソートと呼びます。簡単に言うと、未ソートの端から取り出して、既ソートの適切な場所に挿入(insertion) します。


void ins_sort(data D[],int n) {
    data tmp;  // テンポラリ
    // s を 1(先頭の次) から n-1(末尾) まで動かす
    for(int s=1;s<n;s++){ // s:セパレータ
        // D[0...s-1]:既ソート D[s...n-1]:未ソート
        tmp=D[s]; // 未ソートの端のデータを取る
        for(int i=s-1;i>=0;i--){ // 既ソートの適切な位置を探す
            if (D[i]>tmp) D[i+1]=D[i]; else break;
        }
        D[i]=tmp; // 適切な位置にセット
    }
}

Team TripleFalcon. http://www.triplefalcon.com/

単純選択法

 これも基本的な方法です。n データの単純挿入法による最悪の時間量は O(n2) です。

 アルゴリズムは、配列 D 上でセパレータ変数 s を 1 個ずつ後ろへ動かします。

 s より前の部分 D[0...s]既ソート、後の部分 D[s+1...n-1]未ソートと呼びます。簡単に言うと、未ソートの最小値(最大値)を選択(selection) して、既ソートの末尾にそれを加えます。

 (以下のアルゴリズムは不安定です。安定に直すことは可能です。)


void sel_sort(data D[],int n) {
    data min;  // 未ソートの最小値のindex
    // s を 0(先頭) から n-2(末尾の前) まで動かす
    for(int s=0;s<n-1;s++){ // s:セパレータ
        // D[0...s]:既ソート D[s+1...n-1]:未ソート
        min=D[s]; // 未ソートの端のデータを取る
        for(int i=s+1;i<n;i++){ // 未ソートの最小値を探す
            if (D[i]<min) swap( min,D[i] );
        }
        D[s]=min; // 既ソートの末尾に最小値(最大値)を加える
    }
}

Team TripleFalcon. http://www.triplefalcon.com/

バブルソート

 配列上で、隣り合うデータ同士を比較して大小比較をし、その結果によって入れ替えを行います。 これを繰り返すと並べ替えが終わります。n データによるバブルソートの最悪の時間量は O(n2) です。データ数が多い場合は手におえません。 様々な本に紹介されていますが、利点はあまり無いように思われます。おそらくどんな状況でも最悪のソートと思われます。

 一巡目に配列の左からアクセスし、二順目には右からアクセスするように向きを変えるように設計された変種も存在します。

 隣同士しか比較、交換をしないので、磁気テープ上の整列には向いているかもしれませんがそれでも有効に働くのはデータが少ない場合に限られると思います。

Team TripleFalcon. http://www.triplefalcon.com/

シェルソート

 配列上の k の倍数番目データだけからなる部分配列を単純挿入法でソートします。その後、kの値をいろいろに設定し、繰り返して同じアルゴリズムを適用します。本によっては単純挿入法の変種として紹介されています。

 k の値の決定法によって、様々な変種が存在します。

Team TripleFalcon. http://www.triplefalcon.com/

ヒープソート

 どのようなデータを与えても、ほぼ速いソートです。最悪の場合の速さでは、最も優れていると思われます。 配列上にヒープと呼ばれる木構造を作ります。

Team TripleFalcon. http://www.triplefalcon.com/

マージソート

 どのようなデータを与えても、ほぼ早いソートです。シーケンシャルアクセスのメディアに向いています。磁気テープは、一般にシーケンシャルアクセスに比べてランダムアクセスがとても遅いメディアです。メモリ上に乗らないデータを磁気テープ上でソートする場合、(例えば複数本の磁気テープを使える場合)はこのソート法が有利です。

Team TripleFalcon. http://www.triplefalcon.com/

クイックソート

 平均的には文句なく最も速いソートです。しかしながら、並べ替えがほぼ終わったデータをソートするときなど、計算時間が極端に遅くなる可能性があります。また、安定でないという欠点も持っています。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

整列(sort)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール