1

次の基数ソートプログラムのロジックを知りたいと思いました。

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

typedef unsigned uint;
#define swap(a, b) { tmp = a; a = b; b = tmp; }
#define each(i, x) for (i = 0; i < x; i++)

/* sort unsigned ints */
static void rad_sort_u(uint *from, uint *to, uint bit)
{
    if (!bit || to < from + 1) return;

uint *ll = from, *rr = to - 1, tmp;
while (1) {
    /* find left most with bit, and right most without bit, swap */
    while (ll < rr && !(*ll & bit)) ll++;
    while (ll < rr &&  (*rr & bit)) rr--;
    if (ll >= rr) break;
    swap(*ll, *rr);
}

if (!(bit & *ll) && ll < to) ll++;
bit >>= 1;

rad_sort_u(from, ll, bit);
rad_sort_u(ll, to, bit);
}

/* sort signed ints: flip highest bit, sort as unsigned, flip back */
static void radix_sort(int *a, const size_t len)
{
size_t i;
uint *x = (uint*) a;

each(i, len) x[i] ^= INT_MIN;
rad_sort_u(x, x + len, INT_MIN);
each(i, len) x[i] ^= INT_MIN;
}

static inline void radix_sort_unsigned(uint *a, const size_t len)
{
rad_sort_u(a, a + len, (uint)INT_MIN);
}

int main(void)
{
int len = 16, x[16], i;
size_t len = 16, i;
each(i, len) x[i] = rand() % 512 - 256;

radix_sort(x, len);

each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n');

return 0;
}

while(1) ループをよく理解していないため、行き詰まっています。

これまでのところ、私が知っていることは次のとおりです。

INT_MIN=-2147483648

bitこれはinの値と同じですrad_short_u()

私はプログラムをデバッグしましたがrand() % 512-256、いくつかの -ve 値も生成されます。

最初のパスでは、すべての -ve 値を (最初から) 片側にスワップし、その後 +ve を次のパスから左に 1 ビットシフトするため、ビットの値は 1073741824 になり、1 配列になるまで同じままです。

プログラムのロジックを理解するのを手伝ってください。

4

2 に答える 2

3

このプログラムを理解するには、クイックソートと最上位ビット基数ソートの両方を理解する必要があります。

クイックソートと同様に、配列をパーツに分割し、再帰的にパーツを並べ替えます。最初に、最上位ビットの値に基づいて分割します。次に、両方の半分で再帰します。しかし今回は、半分ごとに、最上位から 2 番目のビットに基づいて分割されます。次に、再び分割し、1/4 ごとに、3 番目の最上位ビットで分割します...

「1/2」、「1/4」などと言っていますが、通常、配列を正確に 1/2、1/4 などに分割するわけではないことに注意してください。各分割のサイズは、配列内の数値の分布。通常のクイックソートの場合、各分割のサイズは「ピボット」として選択された要素に依存しますが、この「基数クイックソート」には当てはまりません。「ピボット」の順序は固定されています。

また、2次になり、特定の入力で非常に遅くなる可能性がある通常のクイックソートとは異なり、この「クイックソート」は一定数のパスで完了することが保証されていることに注意してください。実際には、入力に関係なく、必要なパスの数は一定です。(これは基数ソートの典型的な特性です。パフォーマンスは入力に影響されない傾向があります。)

もう 1 つの興味深い特性: 通常のクイックソートでは、配列が 3 つの部分 (ピボットよりも小さい部分、等しい部分、大きい部分) に分割されます。しかし、この「クイックソート」は常に、各パスでその入力を正確に 2 つの部分に分割します。つまり、テスト対象の位置にビットが 0 のものとビットが 1 のものです。

このアルゴリズムの名前は、実際には「バイナリクイックソート」だと思います。

于 2012-06-28T20:07:06.697 に答える
0

ループwhile(1)は、符号なし整数に対してビット単位で動作します。各ビットについて、リストの上部と下部から開始し、ビットが上部ではなく下部に設定されている整数の最初のペアを見つけて、それらを交換します。これにより、そのビットでのこれらの値の順序が修正されます。

上/下が出会うまでこれを続けます。最終的に、ループを通過するたびに、while(1)そのビットが設定されていないすべての数値がリストの下部にあり、そのビットが設定されているすべての数値がリストの上部にあるリストが作成されます。

リストはビットごとに並べ替えられ、MSB から始まり、2 番目の MSB、...、最後に LSB の順に並べられます。符号付き整数の値INT_MINは負ですが、2 の補数の MSB に対応します。

これらのx[i] ^= INT_MIN行により、基数ソートで負の数を正しく処理できるようになります。符号付き整数は 2 の補数で格納されます。これは事実上、負の数に MSB が設定されていることを意味します。

単純に基数ソートを符号付き整数に適用すると、正の数が負の数よりも低いインデックスになるようにソートされます。

x[i] ^= INT_MINは MSB を反転させ、この問題を解決します。2 番目x[i] ^= INT_MINはビットを反転させます。

于 2012-06-28T20:21:04.087 に答える