0

まず、これは宿題で、同じテーマについて話している別のトピックを見つけましたが、答えはありませんでした. 問題は次のとおりです。

ソートされる値が B ビット (したがって 0 と 2B-1 の間) でコード化された整数であるという仮定に基づくビットによるソート。

主な問題は、この種の並べ替えをどのようにするかです。各整数をビットに変換して比較する必要がありますか? 解決方法のヒントや説明だけを私に与えないでください。ご協力いただきありがとうございます ！[編集] インターネットでこのスクリプトを見つけましたが、その仕組みがわかりませんでした:

#include <cstdlib>
#include <iostream>
#include <string>
#include <cctype>
#include<algorithm>
#include<string>
#include <iterator>
using namespace std;

// Radix sort comparator for 32-bit two's complement integers
class radix_test
{
    const int bit; // bit position [0..31] to examine
public:
    radix_test(int offset) : bit(offset) {} // constructor

    bool operator()(int value) const // function call operator
    {
        if (bit == 31) // sign bit
            return value < 0; // negative int to left partition
        else
            return !(value & (1 << bit)); // 0 bit to left partition
    }
};

// Least significant digit radix sort
void lsd_radix_sort(int *first, int *last)
{
    for (int lsb = 0; lsb < 32; ++lsb) // least-significant-bit
    {
        std::stable_partition(first, last, radix_test(lsb));
    }
}

// Most significant digit radix sort (recursive)
void msd_radix_sort(int *first, int *last, int msb = 31)
{
    if (first != last && msb >= 0)
    {
        int *mid = std::partition(first, last, radix_test(msb));
        msb--; // decrement most-significant-bit
        msd_radix_sort(first, mid, msb); // sort left partition
        msd_radix_sort(mid, last, msb); // sort right partition
    }
}

int main(int argc, char *argv[])
{

    int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };

    lsd_radix_sort(data, data + 8);
    // msd_radix_sort(data, data + 8);

    std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

    system("PAUSE");
    return EXIT_SUCCESS;
}
4

1 に答える 1

6

まず、整数は既にビットとして格納されているため、整数をビットに変換する必要はありません。Anintは通常 4 バイトなので、32 ビットです。ビット演算子を使用してビットにアクセスできます。

ここでは、基数ソートについて詳しく説明します。https://en.wikipedia.org/wiki/Radix_sort

この例では、基数 10 の数字に基づいて並べ替えます。

ビットに基づいてソートするには、アルゴリズムを少し変更して、すべての場所で 10 ではなく 2 を使用します。

void radixsort(int *a, int n) {
...
  while (m / exp > 0) {
    int bucket[2] = { 0 };
    for (i = 0; i < n; i++)      bucket[a[i] / exp % 2]++;
    bucket[1] += bucket[0];
    for (i = n - 1; i >= 0; i--) b[--bucket[a[i] / exp % 2]] = a[i];
    for (i = 0; i < n; i++)      a[i] = b[i];
    exp *= 2;
...
  }
}

しかし、代わりにビットごとの演算子を使用する必要がある場合は、2 で割ったものは単純>> 1に 、2 を掛ける<< 1と 、モジュロ 2 は であることがわかり&1ます。ビット位置に置き換えるexpと、次のように書き換えることができます。

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], bit = 0;
  for (i = 0; i < n; i++) if (a[i] > m) m = a[i];

  while ((m>>bit) > 0) {
    int bucket[2] = { 0 };
    for (i = 0; i < n; i++)      bucket[(a[i]>>bit) & 1]++;
    bucket[1] += bucket[0];
    for (i = n - 1; i >= 0; i--) b[--bucket[(a[i]>>bit) & 1]] = a[i];
    for (i = 0; i < n; i++)      a[i] = b[i];
    bit++;
...
  }
}

これは、単一ビットを使用してソートします。複数のビットを使用するには、より一般的なものにする必要があります。

#define BITS 2
void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], pos = 0;
  int buckets=1<<BITS;
  int mask=buckets-1;
  for (i = 0; i < n; i++) if (a[i] > m) m = a[i];

  while ((m>>(pos*BITS)) > 0) {
    int bucket[1<<BITS] = { 0 };
    for (i = 0; i < n; i++)       bucket[(a[i]>>(pos*BITS)) & mask]++;
    for (i = 1; i < buckets; i++) bucket[i] += bucket[i - 1];
    for (i = n - 1; i >= 0; i--)  b[--bucket[(a[i]>>(pos*BITS)) & mask]] = a[i];
    for (i = 0; i < n; i++)       a[i] = b[i];
    pos++;
...
  }
}

これは 2 ビットを使用してソートするため、4 つのバケットが 00、01、10、および 11 に使用されます。3 ビットは 8 つのバケット (000、001、010、011、100、101、110、111) を使用します。

BITS を増やすとパスが少なくなることがわかりますが、各パスで行われる作業は大きくなります。

于 2013-06-11T12:13:14.593 に答える