5

「 BrainF*** の最速の並べ替え」に取り組んでいるときに、このアルゴリズムを発見しました。これは O(N*k) で、k は入力の最大値です。O(N) の追加ストレージが必要です。

物理的なアナロジーは、N スタックのトークンがあることです。スタックの高さは、並べ替える値を表します。(各トークンはビットを表します)。別の N スタック用にスペースを確保します。トークンを持っている各スタックの一番上からトークンを 1 つ取り、手札が空になるまで、新しいセットの各スタックに右から左に 1 つ追加します。すべての元のスタックが空になるまで繰り返します。これで、新しいセットが左から右に昇順にソートされます

C:

 void sort(int A[], int N)
 {
    int *R = calloc(N,sizeof(int));
    do {
      int i,count=0; 
      for (i=0;i<N;i++) if A[i] { count++; A[i]--;}
      for (i=0;i<count;i++) R[i]++;
    } while (count);
    memcpy(A,R,N);  //A is now sorted descending.
    free(R);
 }

このアルゴリズムに名前はありますか? Bead Sortに似ているように見えますが、まったく同じではないと思います。

4

2 に答える 2

7

結局、私は怠​​け者ではなかったことがわかりました。ビーズソートです。元の論文の定義は次のとおりです（PDFリンク）：

n 個の正の整数の集合Aを考えてみましょう。. . すべての a in Aについて、1 番目のロッドから 1 番目のロッドまで、ロッドに沿ってビーズ (ロッドごとに 1 つのビーズ)をドロップします。最後に、 n番目のレベルから最初のレベルまでレベルごとに見られるビーズは、昇順でAを表します。

この実装は、そのアルゴリズムを次の 2 つの方法で変換します。

  1. ラインを越えて機能している「フレーム」を反映しy=xます。これにより、各列の「ビーズ」の数が降順でソートされた出力を表すように結果が変更されます。元のアルゴリズムでは、各行の「ビーズ」の数は、昇順でソートされた出力を表します。
  2. 「フレーム」をブール値の 2 次元配列として表すのではなく、整数の 1 次元配列として表します。配列の各スロットは「ロッド」に対応し、その値はそのロッドのビーズの数を表します。この 2 番目のビットは自然な変換です。「ビーズ」は空中に浮くことができないため、ロッド上のビーズの数を記録するだけで、ビーズがどのように配置されているかを知る必要があることを認識しているだけです。対応する番号をインクリメントして、ロッドにビーズを配置します。

最初の点について、論文の 2 ページ目の図から直接引用した説明を次に示します。アルゴリズムが最初に実装されているため、配列 [3, 2, 4, 2] は次のようなグリッドで表されます。

* * *
* *
* * * *
* *

ビーズを落とすと、次のものが生成されます。

* *
* *
* * *
* * * *

[2, 2, 3, 4] という出力を得るには、行を上から下に読み取る必要があります。降順で結果を返すバージョンでは、代わりにこれを効果的に行っています。

  *          *
  *   *      * *
* * * *  ->  * * * *
* * * *      * * * *
于 2012-01-26T18:25:22.000 に答える
0

O(n*K) の複雑さの 1 つの代表として、Radix Sort を知っています。

http://en.wikipedia.org/wiki/Radix_sort

于 2012-01-26T15:24:16.313 に答える