基数、カウント、およびバケットソートの定義を読んでいますが、それらはすべて以下のコードにすぎないようです:
public static void sort(int[] a, int maxVal){
int [] bucket=new int[maxVal+1];
for (int i=0; i<bucket.length; i++){
bucket[i]=0;
}
for (int i=0; i<a.length; i++){
bucket[a[i]]++;
}
int outPos=0;
for (int i=0; i<bucket.length; i++){
for (int j=0; j<bucket[i]; j++){
a[outPos++]=i;
}
}
}
私は正しくないことを知っているので、何が欠けているのでしょうか? Java または C での説明に役立つと思われる場合は、コードを示してください。
C の方が説明しやすいので、C でコードを書き直すことから始めましょう。それでは、コメントを付けてコードを思い出してみましょう。
int
counting_sort(int a[], int a_len, int maxVal)
{
int i, j, outPos = 0;
int bucket_len = maxVal+1;
int bucket[bucket_len]; /* simple bucket structure */
memset(bucket, 0, sizeof(int) * bucket_len);
/* one loop bucket processing */
for (i = 0; i < a_len; i++)
{
bucket[a[i]]++; /* simple work with buckets */
}
for (i=0; i < bucket_len; i++)
{
for (j = 0; j < bucket[i]; j++)
{
a[outPos++] = i;
}
}
return 0;
}
この男にいくつかの現実的なデータを提供しましょう。
[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]
出力では、
[126、171、201、223、316、343、348、432、556、670]
すべてが大丈夫だと思われますか？まだ。maxVal を見てみましょう。670 です (!) ここで 10 要素の配列をソートするために、670 要素の配列、主にゼロを使用しました。ひどい。並べ替えをカウントするこの問題を処理するために、2 つの一般化方法が考えられます。
1) 最初の方法 -- 桁ごとに並べ替える。これは基数ソートと呼ばれます。カウントソートコードにできるだけ近づけるように、いくつかのコードを示してみましょう。もう一度コメントを見てください：
int
radix_sort(int a[], int a_len, int ndigits)
{
int i;
int b[a_len];
int expn = 1;
/* additional loop for digits */
for (i = 0; i != ndigits; ++i)
{
int j;
int bucket[10] = {0}; /* still simple buckets */
/* bucket processing becomes tricky */
for (j = 0; j != a_len; ++j)
bucket[ a[j] / expn % 10 ]++;
for (j = 1; j != 10; ++j)
bucket[j] += bucket[j - 1];
for (j = a_len - 1; j >= 0; --j)
b[--bucket[a[j] / expn % 10]] = a[j];
for (j = 0; j != a_len; ++j)
a[j] = b[j];
expn *= 10;
}
}
N に近い乗数をメモリと交換しています。利益？多分。しかし、場合によっては、N に近い乗数が非常に重要になります。プログラム、1 日作業と 1 週間作業は、両方がそれぞれ 1*O(N) と 7*O(N) で動作する場合でも、ユーザー ビューとは大きく異なります。そして、2 番目の一般化に進みます。
2) 2 番目の方法 -- バケットをより洗練されたものにする。これはバケットソートと呼ばれます。
いくつかのコードから始めましょう。私は哲学的な議論の前に、より多くのコードを好む. それでもコメントを見てください。それらは不可欠です。
int
bucket_sort(int a[], int a_len, int maxVal)
{
int i, aidx;
typedef struct tag_list {
int elem;
struct tag_list *next;
} list_t, *list_p;
list_p bucket[10] = {0}; /* sophisticated buckets */
/* one loop simple processing with one more inner loop
to get sorted buckets (insert-sort on lists, Cormen-style) */
for (i = 0; i != a_len; ++i)
{
int bnum = (10 * a[i]) / maxVal;
list_p bptr = bucket[bnum];
list_p belem = malloc(sizeof(list_t));
belem->elem = a[i];
if (bptr == 0)
{
bucket[bnum] = belem;
belem->next = 0;
continue;
}
else if (a[i] <= bptr->elem)
{
belem->next = bptr;
bucket[bnum] = belem;
continue;
}
else
{
while (bptr != 0)
{
if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
{
belem->next = bptr->next;
bptr->next = belem;
break;
}
bptr = bptr->next;
}
}
}
/* one loop (looks as two) to get all back */
aidx = 0;
for (i = 0; i != 10; ++i)
{
list_p bptr = bucket[i];
while (bptr)
{
list_p optr = bptr;
a[aidx] = bptr->elem;
aidx += 1;
bptr = bptr->next;
free(optr);
}
}
return 0;
}
では、ここには何がありますか？洗練されたバケット構造と、動的に割り当てられたメモリの要件を交換していますが、静的メモリと、平均で N に近い乗数を獲得しています。
ここで、コードで見たものを思い出してみましょう。
したがって、基数ソートとバケット ソートは、カウント ソートの 2 つの有用な一般化です。それらは並べ替えを数えたり、お互いに多くの共通点がありますが、いずれの場合も何かを失い、何かを獲得しています。ソフトウェア エンジニアリングは、これらの機会のバランスを取ることです。
基数ソート vs カウンティングソート vs バケットソート。違いは何ですか？
バケット ソートは、ソートするキーまたは要素をバケットに配置します。それらをバケットに配置する方法は任意であり、複合キーの一部および任意のディストリビューションにすることができます。個々のバケットをさらにソートする必要がある場合があります。
メモリ内での並べ替えは、ディスク上での並べ替えよりも高速です。ただし、メモリに収まらないほど多くのデータがある場合は、別のオプションが必要です。できることは、バケットがメモリに収まるほど小さいバケット ソートです。つまり、各バケットに多数のエントリがあります。これらは、個別にすばやく並べ替えることができます。
基数ソートは、特定のタイプのバケット ソートです。上位の n ビットまたは n 桁から開始し、すべてのエントリがソートされるまで、基数ソートなどを使用してこれらのバケットをソートできます。
カウントソートは、値全体を使用することを除いて、基数ソートを使用するのと似ています。各オブジェクトを記録する代わりに、オブジェクトごとにバケットがあり、発生回数をカウントするだけです。これは、可能なキーの数が限られており、多くの重複がある場合にうまく機能します。
Geekviewpointによると：
基数: http://www.geekviewpoint.com/java/sorting/radixsort
基数ソートは、カウンティング ソートやバケット ソートと同様に、整数ベースのアルゴリズムです (つまり、入力配列の値は整数であると見なされます)。したがって、基数ソートは、理論上、最も高速なソート アルゴリズムの 1 つです。基数ソートの特別な違いは、各暗号 (数字) ごとにバケットを作成することです。そのため、バケット ソートと同様に、基数ソートの各バケットは、異なるキーを受け入れる拡張可能なリストである必要があります。
バケット: http://www.geekviewpoint.com/java/sorting/bucketsort
ソートのカウントが合理的にその上限を表していることを考えると、バケットソートは実際には非常に優れています。また、ソートのカウントは非常に高速です。バケット ソートの特別な違いは、ハッシュ関数を使用して入力配列のキーを分割し、複数のキーが同じバケットにハッシュされることです。したがって、各バケットは実質的に拡張可能なリストでなければなりません。基数ソートに似ています。
カウント: http://www.geekviewpoint.com/java/sorting/countingsort
ソートのカウントの特定の違いは、値ごとにバケットを作成し、各バケットにカウンターを保持することです。次に、入力コレクションで値が検出されるたびに、適切なカウンターがインクリメントされます。ソートのカウントでは値ごとにバケットが作成されるため、入力配列の最大値が事前にわかっているという制限が課せられます。
彼らのサイトで詳しく説明しています。
編集：
基数ソートを使用していて数値が 10 進数の場合、0 から 9 までの各桁に 1 つずつ、合計 10 個のバケットが必要です。
カウントソートを使用している場合は、入力の一意の値ごとにバケットが必要です (実際には、0 から最大までの値ごとにバケットが必要です)。
バケットソートを使用している場合、使用するバケットの数はわかりません。使用しているハッシュ関数によって、バケットの数が決まります。
あなたのコードは、データなしでキーだけの並べ替えをカウントする単純なバリアントです。
基数ソートは、この方法に基づくソートです。並べ替えをカウントする際の問題は、メモリ要件です: int [] bucket=new int[maxVal+1];. 基数ソートはこの問題を解決します。アイデアは、カウントソートを数回使用することです。最初は下位の桁で、次に上位の桁です。たとえば、32 ビット整数を並べ替えるには、次のようにします。
sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key
カウントソートは安定しているため、機能します-等しいキーでデータの順序を維持します。スプレッドシートでの並べ替えに似ていsort by B; sort by Aます。要素が A で並べ替えられ、A が等しい場合は B で並べ替えられます。
バケットソートは、カウンティングソートを一般化したものです。(0,1)これを使用して、予測可能な確率分布 (例: uniform )から実数を並べ替えることができます。アイデアは、カウント ソート (floor(x*N_BUCKETS)キーとして使用) を使用し、各バケットのみを個別にソートすることです。
最初に、Radix Sort と Bucket Sort の違いを見てみましょう。アイデアは同じように見えるため、一般的に混乱を招くからです。次に、これら 2 つのプライマリ バージョンのようなカウント ソートと、他の 2 つが使用される原因となるカウント ソートの問題を見ていきます。
基数とバケットの両方の並べ替えの最初のパスは同じです。要素は「バケット」、つまり 0 ～ 10、11 ～ 20 などに配置されます。基数。ただし、次のパスでは、バケット ソートはこれらの「バケット」を上に並べ、それらを 1 つの配列に追加します。ただし、基数ソート方法では、それ以上ソートせずにバケットを追加し、数値の 2 桁目 (10 の位) に基づいてバケットを「再バケット化」します。したがって、バケット ソートは「密な」配列に対してより効率的ですが、基数ソートは疎な配列を適切に処理できます。バケットソートは次のように考えてください
それぞれが 1 から k までの数値であるキーを持つ n 個のレコードのリストがあるとします (問題を少し一般化するため、k は必ずしも n に等しいとは限りません)。
リンクされたリストの配列を作成することで、これを解決できます。各入力レコードを配列の適切な位置にあるリストに移動し、すべてのリストを順番に連結します。
bucket sort(L)
{
list Y[k+1]
for (i = 0; i <= k; i++) Y[i] = empty
while L nonempty
{
let X = first record in L
move X to Y[key(X)]
}
for (i = 0; i <= k; i++)
concatenate Y[i] onto end of L
}
k が大きい場合はどうするか? 数値の 10 進数表現について考えてみましょう x = a + 10 b + 100 c + 1000 d + ... ここで、a、b、c などはすべて 0..9 の範囲です。これらの数字は、バケット ソートを行うのに十分なほど簡単に小さくなります。
radix sort(L):
{
bucket sort by a
bucket sort by b
bucket sort by c
...
}
またはもっと簡単に
radix sort(L):
{
while (some key is nonzero)
{
bucket sort(keys mod 10)
keys = keys / 10
}
}
重要度の低い桁を最初にソートするのはなぜですか? さらに言えば、最後のソートがすべてを適切に配置するものであるのに、なぜ複数のバケットソートを行うのでしょうか? 回答: 手作業でソートしようとしている場合は、別のことを行う傾向があります。最初にバケット ソートを実行し、次に共通の最初の数字を共有する値を再帰的にソートします。これは機能しますが、問題が多くのサブ問題に分割されるため、効率が低下します。対照的に、基数の並べ替えでは、リストが分割されることはありません。同じリストにバケットの並べ替えを数回適用するだけです。基数ソートでは、バケットソートの最後のパスが全体の順序に最も影響を与えます。したがって、最も重要な数字を使用するものにしたいと考えています。以前のバケットの並べ替えパスは、最後のパスで 2 つのアイテムが同じキー (mod 10) を持つ場合に対処するためだけに使用されます。
これで、すべての Counting sort が行うことの邪魔にならないようになりました。それは、すべて 0 に初期化された k 個の要素を持つ補助配列 C を保持することです。
入力配列 A を 1 回通過させ、A の要素 i ごとに、C[i] を 1 ずつ増やします。A の n 個の要素を反復処理して C を更新すると、C のインデックス j の値が対応します。 j が A に出現した回数に依存します。このステップでは、A を反復処理するのに O(n) 時間かかります。C を取得したら、C を反復処理し、C[j] の合計 ja の各要素を挿入することによって、A のソート済みバージョンを構築できます。回を新しいリスト (または A 自体) に追加します。C の反復には O(k) 時間がかかります。最終結果はソートされた A であり、合計で O(n + k) 時間かかりました。
カウントソートの欠点は、要素の範囲が大きすぎる場合、あまり実用的ではない可能性があることです。たとえば、ソートする必要がある n 個の要素の範囲が 1 から n 3 の場合、単純に補助配列 C を作成すると O(n^3) の時間がかかり、ソートのカウントは挿入ソートよりも漸近的に悪化します。これは、これまでに学習した他のソート アルゴリズムで使用されるスペースよりも大幅に大きい O(n^3) スペースも必要とします。基数ソートは、要素を桁ごとにソートすることでこの問題を解決するのに役立ちます
注：回答とさらに読むための情報源：
http://htmltolatex.sourceforge.net/samples/sample4.html
最初の回答:バケット ソートと基数ソートの違いは何ですか?
基数ソートは、サブルーチンとしてカウントソートの形式を使用します（使用できますが、ほとんどの場合、カウントソートになります）。
kasavbereが答えたように、カウンティングソートはバケットソートの特別な形式です。
そして Bucketsort はキーをバケットに分割し、バケットを個別にソートします。
count sortを使用して配列をソートするには：
#define MAX_INPUT 1000
void sort(int arr[100], int n)
{
static int hash[MAX_INPUT], i, j;
memset(hash, 0, sizeof hash);
for (i = 0; i < n; ++i) ++hash[arr[i]];
j = 0;
for (i = 0; i < MAX_INPUT; ++i)
while (hash[i]--)
arr[j++] = i;
}
これは単なるO(MAX_INPUT)、したがって線形時間での並べ替えです。バケットソートの場合、それは非常に異なります。これが実装です