3つの線形ソートアルゴリズムのカウントソート、バケツソート、ベースソート

https://www.byvoid.com/zht/blog/sort-radix
[比較に基づいていないソート]
コンピュータ科学では、ソートは基礎的なアルゴリズム技術であり、多くのアルゴリズムがこれを基礎とし、異なるソートアルゴリズムは異なる時間オーバーヘッドと空間オーバーヘッドを持っている.並べ替えアルゴリズムには、比較に基づく並べ替えと呼ばれるため、私たちが最もよく使用する高速並べ替えやスタック並べ替えなどのアルゴリズムが非常に多くあります.
比較によるソートアルゴリズムはO(Nlogn)を突破できない.簡単な証明は次のとおりです.
N個の数はNがあります!個の可能な配列の場合、つまり比較した並べ替えアルゴリズムによる判定ツリーにNがある!個の葉の結点、比較回数は少なくともlog(N!)=O(Nlogn)(スターリング式).
カウントソート、バケツソート、それに基づいた基数ソートなどの比較に基づくソートではなく、O(Nlogn)時間の下限を突破することができる.ただし、比較に基づいていないソートアルゴリズムの使用には、要素のサイズ制限などの条件があり、逆に比較に基づいているソートにはこのような制限はありません(一定の範囲内).しかし,条件制限があるからといって比較に基づく並べ替えアルゴリズムが不要になるわけではなく,特定の場合に特殊な性質データを有し,比較に基づく並べ替えアルゴリズムでなければ非常に巧みに解決できる.
本論文では,カウントソート,バケツソート,基数ソートの3つの線形非比較に基づくソートアルゴリズムに重点を置いた.
[カウントソート]
まず、カウントソート(Counting Sort)から説明すると、要素の最小値が0より小さくなく、最大値がKを超えないソートされる整数シーケンスAがあると仮定する.長さKの線形テーブルCを作成し、各値より大きくない要素の個数を記録します.
アルゴリズムの構想は以下の通りである.

シーケンスAをスキャンし、Aの各要素の値をインデックスとして、出現した個数をCに記入する.このときC[i]は、Aの値がiの要素の個数を表すことができる.

は、Cを最初から加算し、C[i]がiの要素の個数より大きくないようにする.

統計値に従って結果を出力する.

線形テーブルCから並べ替えたデータを容易に求めることができ,Bをターゲットとするシーケンスを定義し,Order[i]がi番目の要素のAにおける位置であれば,以下の方法で統計することができる.

/*
 * Problem: Counting Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:27
 * State: Solved
 * Memo:     
*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
    int *C=new int[K+1];
    int i;
    memset(C,0,sizeof(int)*(K+1));
    for (i=1;i<=N;i++) // A        
        C[A[i]]++;
    for (i=2;i<=K;i++) //     i      
        C[i]+=C[i-1];
    for (i=N;i>=1;i--)
    {
        B[C[A[i]]]=A[i]; //       ，     B ，      Order 
        Order[C[A[i]]]=i;
        C[A[i]]--;
    }
}
int main()
{
    int *A,*B,*Order,N=15,K=10,i;
    A=new int[N+1];
    B=new int[N+1];
    Order=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //  1..K    
    printf("Before CS:
");
    for (i=1;i<=N;i++)
        printf("%d ",A[i]);
    CountingSort(A,B,Order,N,K);
    printf("
After CS:
");
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    printf("
Order:
");
    for (i=1;i<=N;i++)
        printf("%d ",Order[i]);
    return 0;
}

プログラムの実行効果は以下の通りです.
Before CS:2 8 5 1 10 5 9 9 3 5 6 6 2 8 2After CS:1 2 2 2 3 5 5 5 6 6 8 8 9 9 10Order:4 1 13 15 9 3 6 10 11 12 2 14 7 8 5
明らかに,カウントソートの時間的複雑度はO(N＋K),空間的複雑度はO(N＋K)であった.Kがあまり大きくない場合,これは非常に有効な線形ソートアルゴリズムである.さらに重要なのは,並べ替え後の同じ値の要素の元の相対位置が変化しない(Orderに現れる)安定した並べ替えアルゴリズムであり,これはカウント並べ替えの重要な性質であり,この性質に基づいて基数並べ替えに適用できることである.
[バケツソート]
カウントソートは、Cを統計したばかりの場合、C[i]はAの値がiの要素の個数を表すことができ、このとき、Cを直接順番にスキャンすると、ソート後の結果を求めることができることがわかります.確かにそうですが、この方法はカウントソートではなく、バケツソート(Bucket Sort)であり、正確にはバケツソートの特殊な状況です.
この方法では,プログラムを簡単に書くことができ,カウントソートよりも簡単であるが,安定したOrderを求めることはできない.

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:32
 * State: Solved
 * Memo:        
*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
void BucketSort(int *A,int *B,int N,int K)
{
    int *C=new int[K+1];
    int i,j,k;
    memset(C,0,sizeof(int)*(K+1));
    for (i=1;i<=N;i++) // A             
        C[A[i]]++;
    for (i=j=1;i<=K;i++,j=k) //          ，    B
        for (k=j;kint main()
{
    int *A,*B,N=1000,K=1000,i;
    A=new int[N+1];
    B=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //  1..K    
    BucketSort(A,B,N,K);
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    return 0;
}

この特殊な実装の方式は時間的複雑度がO(N+K)であり,空間的複雑度もO(N+K)であり,同様に各要素がKの範囲内であることが要求される.もっと一般的に、私たちのKが大きいと、O(K)の空間を直接開けられないのはどうでしょうか.
まずバケツを定義し、バケツはデータコンテナであり、バケツごとに1つの区間の数を格納します.要素の最小値は0より小さくなく、最大値はKを超えない順序付けされる整数シーケンスAが依然として存在する.M個のバケツがあると仮定し、i番目のバケツBucket[i]はiK/Mから(i+1)K/Mまでの数を格納し、以下のバケツソートの一般的な方法がある.

はシーケンスAをスキャンし、各要素の値が属する区間に応じて指定されたバケツに入れる(順番に置く).

は、各バケツ内の要素をソートし、どのソートアルゴリズムでも、例えば、高速ソートが可能である.

は、各バケツ内の要素を順次収集し、出力シーケンスに順次配置する.

このアルゴリズムを単純に解析すると、データが所望の平均分布である場合、各バケツ中の要素の平均個数はN/Mである.各バケツの要素のソートに使用されるアルゴリズムが高速ソートである場合、ソートごとの時間的複雑度はO(N/Mlog(N/M))である.合計時間複雑度はO(N)+O(M)O(N/Mlog(N/M)=O(N+Nlog(N/M))=O(N+NlogN-NlogM)である.MがNに近い場合,バケツ並べ替えの時間的複雑さはO(N)と近似できる.バケツが多ければ多いほど、時間効率が高くなりますが、バケツが多ければ多いほど、空間が大きくなり、時間と空間が矛盾する2つの側面であることがわかります.
バケツ中の要素の順序付けと順序付けの取り出しは必要であり、バケツの順序付けが安定した順序付けアルゴリズムであることを決定することができ、基数の順序付けに合わせてよく使用されるからである.

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo:        
*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct linklist
{
    linklist *next;
    int value;
    linklist(int v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
/*
    ，  A              ，               ，         。
*/
void BucketSort(int *A,int *B,int N,int K)
{
    linklist *Bucket[101],*p;//   
    int i,j,k,M;
    M=K/100;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i]/M; // A                  
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        i=j;
        for (p=Bucket[k];p;p=p->next)
            B[++j]=p->value; //         ，     B
        delete Bucket[k];
        qsort(B+i+1,j-i,sizeof(B[0]),cmp);
    }
}
int main()
{
    int *A,*B,N=100,K=10000,i;
    A=new int[N+1];
    B=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //  1..K    
    BucketSort(A,B,N,K);
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    return 0;
}

[基数ソート]
次に、私たちのメインイベント、基数ソート(Radix Sort)について説明します.上記の基数ソートとバケツソートは、1つのキーワードのソートを検討しているだけで、複数のキーワードのソート問題について議論します.
いくつかの二元グループ(a,b)があり、aを主なキーワードとし、bの二次キーワードのソートを行うと仮定します.まず、それらを最初のキーワードに従ってソートし、最初のキーワードと同じいくつかのスタックに分けることができます.次に、各スタックをサブキー値で個別にソートします.最後に、これらのスタックをつなぎ合わせて、最も重要なキーワードの小さいスタックを上に並べます.このような基数ソートはMSD(Most Significant Dight)ソートと呼ばれる.
2つ目の方法は、LSD(Least Significant Dight)ソートと呼ばれる最低有効キーワードからソートを開始することである.まず、すべてのデータを二次キーワードでソートし、すべてのデータを一次キーワードでソートします.使用するソートアルゴリズムは安定している必要があります.そうしないと、前回のソートの結果がキャンセルされます.スタックごとに個別にソートする必要がないため、LSD法はMSDよりも簡単でオーバーヘッドが小さいことが多い.以下で紹介する方法はすべてLSDによるものである.
通常、ベースソートはカウントソートまたはバケツソートに使用されます.カウントソートを使用する場合は、Order配列が必要です.バケツソートを使用する場合は、チェーンテーブルの方法でソート後の順序を直接求めることができます.次の手順は、バケツソートによる二元グループの基数ソートです.

/*
 * Problem: Radix Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo:          
*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct data
{
    int key[2];
};
struct linklist
{
    linklist *next;
    data value;
    linklist(data v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
    linklist *Bucket[101],*p;//   
    int i,j,k,M;
    M=K/100+1;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i].key[y]/M; // A                  
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        for (p=Bucket[k];p;p=p->next) j++;
        for (p=Bucket[k],i=1;p;p=p->next,i++)
            A[j-i+1]=p->value; //         
        delete Bucket[k];
    }
}
void RadixSort(data *A,int N,int K)
{
    for (int j=1;j>=0;j--) //         LSD
        BucketSort(A,N,K,j);
}
int main()
{
    int N=100,K=1000,i;
    data *A=new data[N+1];
    for (i=1;i<=N;i++)
    {
        A[i].key[0]=rand()%K+1;
        A[i].key[1]=rand()%K+1;
    }
    RadixSort(A,N,K);
    for (i=1;i<=N;i++)
        printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
    printf("
");
    return 0;
}

基数ソートは、従来のカードスルーマシンに使用されるアルゴリズムです.1枚のカードは80列あり、各列は12の位置のいずれかで穿孔することができる.並べ替え器は機械的に「プログラム化」されて、各反復カードの列を検査し、穿孔の位置に応じて12個の箱に分けることができる.これにより、オペレータはそれらを1つずつ集めることができます.ここで、第1の位置穿孔は最上部に配置され、第2の位置穿孔の次に、等が挙げられる.
1桁の有限な10進数に対して,高位から低位までのキーワードの重要度が順次減少する多重グループと見なすことができる.基数ソートを使用して、いくつかのビット数に制限された10進数をソートできます.
[3つの線形ソートアルゴリズムの比較]
全体的に,カウントソート,バケツソートはいずれも比較に基づくソートアルゴリズムではなく,その時間的複雑さはデータの範囲に依存し,バケツソートは空間のオーバーヘッドとデータの分布にも依存する.基数ソートは、カウントソートまたはバケツソートに使用される複数のグループのソートに有効な方法です.
高速ソート、スタックソートなど比較に基づくソートアルゴリズムに比べて、カウントソート、バケツソート、基数ソートの制限が多く、高速ソート、スタックソートなどのアルゴリズムの柔軟性が良い.しかし、逆に言えば、この3つの線形ソートアルゴリズムが線形時間に達することができるのは、ソートされるデータの特性を十分に利用しているためであり、高速ソート、スタックソートなどのアルゴリズムを硬く使用すると、これらの特性を浪費することに相当し、より高い効率に達することができないからである.
実際の応用では,基数ソートは接尾辞配列の倍増アルゴリズムに用いられ,時間複雑度をO(NlogNlogN)からO(N*logN)に低下させることができる.線形ソートアルゴリズムは,最適な効果を達成するためにデータの特殊な性質を十分に利用することが最も重要である.