ボックスソート(Bin Sort)
3843 ワード
分配並べ替えの基本思想:並べ替え過程はキーワードを比較する必要はなく、「分配」と「収集」過程を通じて並べ替えを実現する.それらの時間的複雑さは線形次数:O(n)に達することができる.ボックスソート(Bin Sort)1、ボックスソートの基本思想ボックスソートはバケツソート(Bucket Sort)とも呼ばれ、その基本思想は、いくつかのボックスを設け、ソートされるレコードR[0]、R[1],...,R[n-1]を順次スキャンし、キーワードがkに等しいレコードをすべてk番目のボックスに入れ(割り当て)、各空でないボックスの先頭と末尾を順番に接続(収集)することである.【例】混洗した52枚のトランプを点数A<2<…
バケツソート
ボックスソートの変種.上記のボックスソートと区別するために、一応バケツソートと呼ぶ(実際にはボックスソートとバケツソートは同義語である).
1、桶の並べ替えの基本思想
バケツソートの考え方は、[0,1]をn個の大きさの同じサブ区間に分割し、各サブ区間がバケツである.その後、n個のレコードを各バケツに割り当てる.キーワードシーケンスは均一に分布する[0,1]に記載されているため、同一バケットに記録されるものは多くない.同一バケットに記録されるものはキーワードが異なるため、キーワード比較のソート方法(通常は挿入ソート)を用いて各バケットをソートし、各非空きバケットに記録を順次接続(収集)しなければならない.
注意:
このソート思想は、入力されたn個のキーワードシーケンスが区間[0,1)の上にランダムに分布していると仮定する.キーワードシーケンスの値範囲が当該区間でない場合、その値が負でない限り、我々は常にすべてのキーワードをある適当な数で割って、キーワードを当該区間にマッピングすることができる.ただし、マッピング後のキーワードが均一に分布していることを保証する[0,1]にあります.
2、バケツ並べ替えアルゴリズム
疑似コードアルゴリズムは次のとおりです.
注意:
実装には、n個のバケツを表すポインタベクトルB[0..n−1]を設定する必要がある.ただし、いずれのレコードR[i]のキーワードも、0≦R[i]を満たす.key<1(0≦i≦n-1)であるため、R[i]を必要とする.keyをBの下付き区間[0,n−1)にマッピングしてこそ、R[i]をバケツに入れることができ、これは、└n*(R[i].key)┘によって実現することができる.
3、バケツの並べ替え例
R[0.9]のキーワードは(0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68)であり、アルゴリズムBucketSortでソートするプロセスである.
分析:
ここでn=10であるため、B[0.9]の10個のバケツで表されるサブ区間は、それぞれ[0,0.1),[0.1,0.2),...,[0.9,1)である.
収集プロセスは,B[0],B[1],...,B[9]の順に各非バケツの首尾をリンクするか,R[0..9]に出力すればよい.
4、バケツ並べ替えアルゴリズム分析
バケツ配列の平均時間複雑度は線形,すなわちO(n)であった.しかし、最悪の場合、O(n)である可能性があります.
2).
ボックスソートは、キーワードの値範囲が小さい場合にのみ適用されます.そうしないと、必要なボックスの数mが多すぎて、ストレージスペースと計算時間が無駄になります.
【例】n=10、並べ替えられたレコードキーワードk
i値範囲が0から99までの整数(36,5,16,98,95,47,32,36,48)の場合、100個の箱で1箱ソートします.(即ちm=n
2の場合、ボックスソートの時間O(m+n)=O(n
2))
バケツソート
ボックスソートの変種.上記のボックスソートと区別するために、一応バケツソートと呼ぶ(実際にはボックスソートとバケツソートは同義語である).
1、桶の並べ替えの基本思想
バケツソートの考え方は、[0,1]をn個の大きさの同じサブ区間に分割し、各サブ区間がバケツである.その後、n個のレコードを各バケツに割り当てる.キーワードシーケンスは均一に分布する[0,1]に記載されているため、同一バケットに記録されるものは多くない.同一バケットに記録されるものはキーワードが異なるため、キーワード比較のソート方法(通常は挿入ソート)を用いて各バケットをソートし、各非空きバケットに記録を順次接続(収集)しなければならない.
注意:
このソート思想は、入力されたn個のキーワードシーケンスが区間[0,1)の上にランダムに分布していると仮定する.キーワードシーケンスの値範囲が当該区間でない場合、その値が負でない限り、我々は常にすべてのキーワードをある適当な数で割って、キーワードを当該区間にマッピングすることができる.ただし、マッピング後のキーワードが均一に分布していることを保証する[0,1]にあります.
2、バケツ並べ替えアルゴリズム
疑似コードアルゴリズムは次のとおりです.
void BucketSon(R)
{ // R[0..n-1] ， 0≤R[i].key<1(0≤i<n)
for(i=0，i<n;i++) // ．
R[i] B[「n(R[i].key)」] ；//
for(i=0;i<n;i++) //
B[i] B[i] ；
for(i=0，i<n；i++) //
B[i] ， B[i] R ；
}注意:
実装には、n個のバケツを表すポインタベクトルB[0..n−1]を設定する必要がある.ただし、いずれのレコードR[i]のキーワードも、0≦R[i]を満たす.key<1(0≦i≦n-1)であるため、R[i]を必要とする.keyをBの下付き区間[0,n−1)にマッピングしてこそ、R[i]をバケツに入れることができ、これは、└n*(R[i].key)┘によって実現することができる.
3、バケツの並べ替え例
R[0.9]のキーワードは(0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68)であり、アルゴリズムBucketSortでソートするプロセスである.
分析:
ここでn=10であるため、B[0.9]の10個のバケツで表されるサブ区間は、それぞれ[0,0.1),[0.1,0.2),...,[0.9,1)である.
収集プロセスは,B[0],B[1],...,B[9]の順に各非バケツの首尾をリンクするか,R[0..9]に出力すればよい.
4、バケツ並べ替えアルゴリズム分析
バケツ配列の平均時間複雑度は線形,すなわちO(n)であった.しかし、最悪の場合、O(n)である可能性があります.
2).
ボックスソートは、キーワードの値範囲が小さい場合にのみ適用されます.そうしないと、必要なボックスの数mが多すぎて、ストレージスペースと計算時間が無駄になります.
【例】n=10、並べ替えられたレコードキーワードk
i値範囲が0から99までの整数(36,5,16,98,95,47,32,36,48)の場合、100個の箱で1箱ソートします.(即ちm=n
2の場合、ボックスソートの時間O(m+n)=O(n
2))