Chapter 7ソート(Sort)

51853 ワード

DataStructure

文書ディレクトリ

1. ソートの概念とそのアルゴリズム性能

1.1概念

1.2並べ替えアルゴリズムの性能評価

1.3ソートテーブルのクラス定義

2. 挿入ソート

2.1直接挿入ソート

2.1.1実装コード

2.1.2性能評価

2.2二分法挿入ソート

2.2.1実装コード

2.2.2性能評価

2.3ヒルソート

2.3.1実装コード

2.3.2性能評価

3. クイックソート

3.1実装コード

3.2性能評価P 407

4. 選択ソート

4.1直接選択ソート

4.1.1コード実装

4.1.2性能評価P 414

4.2スタックソート

4.2.1コード実装

4.2.2性能評価

5. 集計ソート

5.1コード実装

5.2性能評価

6. その他のソート

6.1カウントソート

6.2基数ソート

6.3バケツソート

1.並べ替えの概念とそのアルゴリズム性能
1.1概念
データテーブル(dataList)ソート対象要素の有限集合です
ソートコード(key)は、通常、データ要素には複数の属性ドメイン、すなわち複数のデータメンバーからなり、1つの属性ドメインがソートの根拠として要素を区別するために使用され得る.ドメインはソートコードです.
ソートの正確な定義ソートとは、ソートコードの増加または減少の順序に基づいて、データ要素を順番に並べて、任意に並べられた要素のセットを、そのソートコードによって線形に秩序化された要素のセットにすることである.
ソートアルゴリズムの安定性要素シーケンスに2つの要素R i R_がある場合イRiとR j R_j Rj,それらのソートコードK i==K j K_i==K_j Ki==Kjであり、ソート前に要素R i R_イRiはR j R_に並ぶj Rjの前.ソート後、要素R i R_i RiはまだR j R_にいるj Rjの前では,このソートアルゴリズムが安定している,そうでなければこのソートアルゴリズムが不安定であると呼ぶ.
内部ソートと外部ソートのソートアルゴリズムは、ソート中にデータ要素が完全にメモリにあるかどうかによって、内部ソートと外部ソートの2つのクラスに分けられます.
1.2並べ替えアルゴリズムの性能評価
ソートアルゴリズムの時間オーバーヘッドは、アルゴリズム実行中のデータ比較回数とデータ移動回数で測定できます.アルゴリズム実行時間コストの大まかな推定は一般的に平均的に推定され、要素ソートコードシーケンスの初期配列や要素個数の影響が大きい場合は、最良の状況と最悪の状況で推定する必要がある.
1.3ソート・テーブルのクラス定義
2.ソートの挿入
2.1並べ替えの直接挿入
2.1.1実装コード

/**                                                                                                                                     
 *       
 */

#include 

using namespace std;

void Insert_Sort(int []);

int main(){
    int num[14] = {3,1,9,5,8,6,20,12,56,33,39,0,11,34};
    for (int i = 0; i < 14; i++){
        cout << num[i] << " ";
    }
    cout << endl;
    cout << endl;
    Insert_Sort(num);
    return 0;
}

void Insert_Sort(int n[]){
    int temp;
    for(int i = 1; i < 14; i++) {
        if (n[i] < n[i-1]){
            temp = n[i];
            int j = i-1;
            do {
                n[j+1] = n[j];
                
                ////////    
                for(int i = 0; i < 14; i++){
                    cout << n[i] << " ";
                }
                cout << endl;
                ////////
                
                j--;
            }while(j >= 0 && temp < n[j]);
            n[j+1] = temp;
            
            ////////    
            for(int i = 0; i < 14; i++){
                cout << n[i] << " ";
            }
            cout << endl;
            cout << endl;
            ////////
        }
    }
    cout << endl;
    for(int i = 0; i < 14; i++){
        cout << n[i] << " ";
    }
    cout << endl;
}

2.1.2性能評価
並べ替えられる要素の個数をn n nとすると、このアルゴリズムのメインプログラムは、並べ替えコードの比較回数と要素の移動回数が要素並べ替えコードの初期配列に関係するため、n−1 n−1 n−1回実行する.

最良の場合、ソートコード比較回数KCN KCN KCNとRMN RMN RMNは、それぞれ、KCN=n−1 KCN=n−1 KCN=n−1 RMN=0 RMN=0

である

最悪の場合、ソートコード比較回数KCN KCN KCNとRMN RMN RMNは、それぞれ、KCN=Σi=1 n−1 i=n(n−1)2≒n 2 KCN=sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}\approx\frac{n^2}{2} KCN=i=1∑n−1i=2n(n−1)≈2n2 R M N = ∑ i = 1 n − 1 ( i + 2 ) = ( n + 4 ) ( n − 1 ) 2 ≈ n 2 2 RMN=\sum_{i=1}^{n-1}(i+2)=\frac{(n+4)(n-1)}{2}\approx\frac{n^2}{2} RMN=i=1∑n−1(i+2)=2(n+4)(n−1)≈2n2

以上の議論から,並べ替えを直接挿入する実行時間は,並べ替えられる要素の元の並べ替え順序と密接に関連していることが分かった.並べ替えられる要素シーケンスに種々の可能な配列が現れる確率が同じであれば、上述した最良最悪の場合の平均をとることができる.平均した場合のKCN KCN KCNとRMN RMN RMNはn 2 4frac{n^2}{4}4 n 2程度であった.従って,直接挿入ソートの時間的複雑さはO(n 2)O(n^2)O(n 2)であった.直接挿入ソートは安定したソートアルゴリズムです.
2.2二分法挿入ソート
2.2.1実装コード

/**                                                                                                                                     
 *        （      ）
 */

#include 

using namespace std;

void Binary_Insert_Sort(int n[]);

int main(){
    int num[14] = {3,1,9,5,8,6,20,12,56,33,39,0,11,34};
	for (int i = 0; i < 14; i++){
        cout << num[i] << " ";
    }
    cout << endl;
    cout << endl;
    Binary_Insert_Sort(num);
    return 0;
}

void Binary_Insert_Sort(int n[]){                                                                                                       
    int temp,low,high,middle;
    for (int i = 1; i < 14; i++){
        temp = n[i];
        low = 0; //    
        high = i-1;  //    
        while (low <= high){
            middle = (low+high)/2;
            if (temp < n[middle])
                high = middle-1;
            else
                low = middle+1;
        }
        for (int k = i-1; k >= low; k--){
            n[k+1] = n[k];
        }
        n[low] = temp;
    }

    cout << endl;
    for(int i = 0; i < 14; i++){
        cout << n[i] << " ";
    }
    cout << endl;
}

2.2.2性能評価
半角検索はシーケンス検索よりも速いので、二分挿入ソートは、直接挿入ソートよりも平均性能が速い.これに必要なKCNKCNは、並べ替えられる要素のシーケンスの初期配列とは無関係であり、要素の個数にのみ依存する.i番目のi個目の要素を挿入する場合は、⌊l o g 2 i⌋+1lfloor log_2 irfloor+1⌊log 2 i⌋+1次ソートコードを比較して、挿入すべき位置を決定します.従って、n個の元素(導出の便宜上n=2 kn=2^kn=2 kとする)を折半挿入で並べ替えたKCN KCNは、KCN=Σi=1 n−1(⌊l o g 2 i⌋+1)=(1+2+2 2 2+2 2+..+2 k−1)+(2+2 2 2+2+...+2 k−1)KCN=sum_1となる{i=1}^{n-1}(\lfloor log_2i\rfloor +1)=(1+2+2^2+...+2^{k-1})+(2+2^2+...+2^{k-1}) KCN=i=1∑n−1(⌊log2i⌋+1)=(1+2+22+...+2k−1)+(2+22+...+2k−1) = k ⋅ 2 k − 2 k + 1 = n ⋅ l o g 2 n − n + 1 ≈ n ⋅ l o g 2 n =k\cdot 2^k-2^k+1=n\cdot log_2n-n+1\approx n\cdot log_2 n=k⋅2 k−2 k+1=n⋅log 2 n−n+1≒n⋅log 2 n nが大きい場合、総KCN KCNは直接挿入ソートの最悪の場合よりもはるかに良いが、その最良の場合よりも劣る.したがって、エレメントの初期シーケンスがソートコードで並べられているか、またはほぼ順序付けされている場合、直接挿入ソートは、折半挿入ソートで実行されるKCN KCNよりも少なく、折半挿入ソートのRMNは、直接挿入ソートと同様に、エレメントの初期配列に依存する.折りたたみ挿入ソートは安定したソート方法です.
2.3ヒルソート
2.3.1実装コード

/**
 *     
 */

#include 

using namespace std;

void Shell_Sort(int n[],const int,const int);

int main(){
    int num[14] = {3,1,9,5,8,6,20,12,56,33,39,0,11,34};

    for (int i = 0; i < 14; i++){
        cout << num[i] << " ";
    }   
    cout << endl;
    cout << endl;
    Shell_Sort(num,0,13);
    return 0;
}

void Shell_Sort(int n[],const int left,const int right){
    int gap = right-left+1;
    int temp;
    do {
        gap = gap/3+1;
        
        /*        */
        for(int i = left+gap; i <= right; i++){
            if(n[i] < n[i-gap]){
                temp = n[i];
                int j = i-gap;
                do {
                    n[j+gap] = n[j];
                    j -=gap;
                }while(j >= left && temp < n[j]);
                n[j+gap] = temp;
            }

        }
        ////////
        for(int i = 0; i < 14; i++){
            cout << n[i] << " ";
        }
        cout << endl;
        cout << endl;
        ////////
    }while(gap > 1);

	cout << endl;
    for(int i = 0; i < 14; i++){
        cout << n[i] << " ";
    }
    cout << endl;   
}

2.3.2性能評価
ヒルソートの時間的複雑さの解析は困難であり,特定の場合にはKCN KCN KCNとR MN RMN RMNを正確に推定できるが,KCN KCN KCNとR MN RMNと増分選択との依存関係を明らかにし,完全な数学的解析を与えることはできない.Knuthは大量の実験統計資料を利用して、n n nが大きい時、並べ替えコードの平均比較回数と元素の平均移動回数は約n 1.25 n^{1.25}n 1であることを得た.25~1.6 n 1.25 1.6 n^{1.25}1.6 n 1.25の範囲内です.これは,サブシーケンスソートアルゴリズムとして直接プラグを用いた場合に得られる.
ヒルソートは,規模の大きいシーケンス(n≦1000 nleq 1000 n≦1000 n)に対しても高い効率を有する.また、ヒルソートアルゴリズムのコードは簡単で実行しやすいため、多くのソートアプリケーションがヒルソートを選択しています.ヒルソートは不安定なソートアルゴリズムである.
3.クイックソート
3.1実装コード
クイックソートは、分割法を用いてソートする交換を区別する方法です.

/**
 *     
 */

#include 
                                                                                                                                        
using namespace std;

void Quick_Sort (int n[],const int,const int);
int partition(int n[], const int low,const int high);

int main(){
    int num[14] = {3,1,9,5,8,6,20,12,56,33,39,0,11,34};

    for (int i = 0; i < 14; i++){
        cout << num[i] << " ";
    }   
    cout << endl;
    cout << endl;
    Quick_Sort(num, 0, 13);
    return 0;
}

void Quick_Sort (int n[], const int left, const int right){
    if(left < right){
        int pivotpos = partition(n, left, right); //  
        Quick_Sort(n, left, pivotpos-1);
        Quick_Sort(n, pivotpos+1, right);
    }   

    cout << endl;
    for(int i = 0; i < 14; i++){
        cout << n[i] << " ";
    }
    cout << endl;
}

int partition(int n[], const int low,const int high){
    int pivotpos = low;
    int pivot = n[low];                 //    
    for(int i = low+1; i <= high; i++)  //      ，    
        if (n[i] < pivot){
            pivotpos++;
            if (pivotpos != i) swap(n[pivotpos], n[i]); //           
        }
    n[low] = n[pivotpos];
    n[pivotpos] = pivot;
    return pivotpos;
}

3.2性能評価P 407
関数Quick_Sortの平均計算時間もO(nl o g 2 n)O(nlog 2 n)O(nlog 2 n)O(nlog 2 n)であり,平均計算時間については,我々が議論したすべての内部ソートアルゴリズムの中で最も優れている.
メモリオーバーヘッドO(l o g 2 n)O(log_2 n)O(log 2 n)
最悪の場合、すなわち、ソート対象要素シーケンスがそのソートコードに従って小さい順にソートされている場合、その再帰ツリーは単一ツリーであり、合計ソートコード回数はΣi=1 n−1(n−i)=1 2 n(n−1)≒n 2 2 2sum_に達する{i=1}^{n−1}(n−i)=frac{1}{2}n(n−1)approxfrac{n^2}{2}i=1Σn−1(n−i)=21 n(n−1)≒2 n 2はその並べ替え速度が単純な並べ替えレベルに劣化し,直接挿入並べ替えよりも遅い.
(未完待機)
4.ソートの選択
4.1直接選択ソート
4.1.1コード実装

/**
 *       
 */

#include 

using namespace std;

void Select_Sort(int n[], const int, const int);                                                                                        
int main(){
    int num[14] = {3,1,9,5,8,6,20,12,56,33,39,0,11,34};
    
    for (int i = 0; i < 14; i++){
        cout << num[i] << " ";
    }   
    cout << endl;
    cout << endl;
    Select_Sort(num, 0, 13);

    return 0;
}

void Select_Sort(int n[],const int left, const int right){
    for (int i = left; i <= right; i++){
        int k = i;
        for (int j = i+1; j <=right; j++){
            if(n[j] < n[k]) 
                k = j;
        }
        if (k != i)
            swap(n[i], n[k]);
    }

    cout << endl;
    for(int i = 0; i < 14; i++){
        cout << n[i] << " ";
    }
    cout << endl;   
}

4.1.2性能評価P 414
直接選択ソートのソートコード比較回数は、要素シーケンスの初期配列に関係します.この要素のセットの初期状態がそのソートコードによって小さいから大きいまで秩序がある場合、要素移動回数R MN=0 RMN=0 RMN=0 RMN=0;最悪の場合は1回ごとに交換され,合計のR MN=3(n−1)RMN=3(n−1)RMN=3(n−1)RMN=3(n−1)である.それでも、他のソートアルゴリズムに比べて、ソートされる要素シーケンスの秩序性は、ソートを選択する実行時間にあまり影響しません.
また、重要な要素シーケンスのクラスに対して効率的です.これは、要素の規模が大きく、ソートコードが小さいシーケンスです.このシーケンスをソートするため、移動操作にかかる時間は比較操作よりもずっと大きく、他のアルゴリズムの移動操作の回数は選択ソートよりもずっと多い.直接選択ソートは不安定なソート方法です.
4.2ヒープ・ソート
4.2.1コード実装

4.2.2性能評価
5.集計ソート
5.1コード実装
5.2性能評価
6.その他のソート
6.1カウントソート
6.2基数ソート
6.3バケツソート

docker概要

Docker初心者が「なんとなく理解した」レベルになるまでの記事まとめ