5

以下のように、バケットの並べ替えに関する私の分析を検討したいと思います。
バケットの並べ替えを実装する方法はたくさんあります。それらのいくつかは次のとおりです。
タイプ 1:
ソートする要素の範囲がわかっている場合は、考えられる要素ごとにバケットを設定し、要素を対応するバケットに放り込むだけです。次にバケットを順番に空にすると、結果はソートされたリストになります。このアルゴリズムの実装では、配列を使用してバケットを簡単に表すことができます。各配列インデックスの値は、対応するバケット内の要素の数を表します。[0..max] の範囲に整数がある場合、(max + 1) 整数の配列を設定し、すべての値をゼロに初期化します。次に、ソートされていない配列を順次処理し、各要素の値を読み取り、バケット配列内の対応するインデックスに移動し、そこで値をインクリメントします。

時間 : O(N)
空間: O(1)
タイプ 2:

例: 人の配列を年齢でソートする
年齢は、任意の整数によるソートとは多少異なります。そのため、[0 ～ 150] という小さな範囲になります (すべての人の年齢は 0 ～ 150 の間です)。したがって、並べ替える最も簡単な方法は、151 個のリンクされたリスト (バケットと呼びましょう) を割り当て、年齢に応じて各人のデータ構造をバケットに入れることです。

時間 : O(N+K)
空間: O(N+K)

Type 3 (ウィキペディアにある type2 のバリエーション)

関数 nextSort は、各バケットを並べ替えるための並べ替え関数です。最悪よりも挿入ソートを使用する場合は、O(n^2) またはマージソートを使用して、O(nlgn) よりも安定性を維持できるようにします。

  • 質問:
    1>線形ソートと見なされる理由は、タイプ 1 またはタイプ 2 によるものですか?
    2>WIkepedia のようなタイプ 3 を使用する場合、各バケットを効率的にソートするのはどのソートですか?
    挿入ソートが実際に使用される理由は、バケットが小さいと予想されるためであり、小さなリストの場合、挿入ソートは他の何よりもはるかに高速です。マージソートまたはクイックソートを実装する場合でも、リストが十分に小さくなると (たとえば、20 項目以下など)、挿入ソートが使用されます。
    3>タイプ 3 の場合、どの基準でバケットの範囲を決定できますか?
    これは重要です。たとえば、n よりもはるかに大きい多数のバケットを使用してバケット ソートを実行しようとすると、実際に使用したバケットを探すためにすべてのバケットをスキャンするのに必要な時間が実行時間の大半を占める可能性があるためです。それらのほとんどは空です。

以下に基づいて分析を行いました:
ウィキペディア
バケット ソートの複雑さはどのように O(n+k) になるのでしょうか?
アルゴリズムの設計と分析 1996 年 1 月 23 日の講義ノート
http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
http://cs.nyu.edu/courses/fall02/V22.0310-002/ lectures/lecture-23.html
連結リストを使ってバケットを実装した場合、バケット ソートの複雑さはどのように O(n+k) になりますか?
バケットソートの最悪のケースの複雑さは?

4

3 に答える 3

5

タイプ 1:
最初に説明したタイプは、実際にはバケット ソートではありません。実際には、ソートまたはキーインデックスのカウントをカウントしています。バケットソートのバリアントと見なされますが。その理由は、キー自体をバケットに格納するのではなく、実際には各キーの出現回数を数えているだけだからです。

参照: http://en.wikipedia.org/wiki/Counting_sort
参照: http://www.cs.princeton.edu/courses/archive/spr13/cos226/demo/51DemoKeyIndexedCounting.pdf

スペース: O(1)
考えられる要素ごとにバケットを設定できます。

これは矛盾していませんか？考えられるすべての要素に対してバケットを宣言し、それでも O(1) を維持するつもりですか? ;)

アルゴリズムを安定させたい場合は、入力配列も上書きできません。したがって、実際には、次のスペース要件 n + k が必要です。

  • 長さ 'n' の出力配列 (基本的に入力配列と同じサイズ)
  • 'k' バケット

並べ替えをカウントするための疑似コードを確認すると、最後のループが入力配列を再度調べて、すべての要素がどこに行く必要があるかを確認することがわかります。入力配列に表示される順序でこれを行うと、安定したソートが得られます。

PS:必ずしも整数をソートしているわけではないことに注意してください。入力が AZ 間の文字の配列である場合、このアルゴリズムも使用できます。

タイプ 2:

したがって、並べ替える最も簡単な方法は、151 個のリンクされたリスト (バケットと呼びましょう) を割り当て、年齢に応じて各人のデータ構造をバケットに入れることです。

必要なバケットをかなり簡単に見つけることができるため、最も簡単な方法かもしれませんが、必ずしも最速の方法ではありません。たとえば、10 年ごとにバケットを作成することもできます。

00 - 09
10 - 19
20 - 29
...

バケットに何かを挿入したい場合は、次のようにします。

  • 適切な位置を見つけるためのバケット (LinkedList など) のバイナリ検索
  • 要素を挿入する

この方法では、すべてが既にソートされているため、後でバケットをソートする必要もありません。それが良い考えだと言っているのではなく、可能性を指摘しているだけです。

質問:

  1. 簡単に言えば; 並べ替えには線形時間がかかるため、線形並べ替えです。タイプ 1 とタイプ 2 はどちらも O(n + k) を取ります。考慮すべきもう 1 つの重要な要素は、個々のバケットをソートするためにバケット ソートで使用されるサブアルゴリズムです。クイックソートを使用すると、たとえばバブルソートと比較して、別の下限になります。境界が異なる非比較サブアルゴリズムを選択することもできます。サブアルゴリズムの適切な選択とバケットへの分散により、bucketsort が O(n(log n)) 下限に制限されなくなります。O表記は速度を保証するものではなく、成長率を保証するものであることに注意してください。入力サイズが 'N' から '2N' に 2 倍になった場合、線形時間アルゴリズムは、たとえばバブルソートのような O(n^2) (最悪の場合) アルゴリズムよりもうまく処理できます。

  2. 挿入ソートは確かに小さな配列に対して効率的であり、それが主に選択された理由です。さらに、安定しているという事実。安定したアルゴリズムを使用してバケット自体をソートしないと、アルゴリズム全体 (バケットのソート) が安定しないためです。

  3. 言いにくい。私の意見では、それはデータに依存します。100 万個の 32 ビット整数をソートする必要がある場合、それらのために 2^32 個のバケットを作成することはありません。その場合、基本的に 9 つのバケット (各桁に 1 つ) を作成する他のアルゴリズム (LSD 基数ソートなど) を検討するとよいでしょう。

于 2013-05-23T14:02:03.343 に答える