Radix сортировка с использованием побитовых операций

Question

Radix сортировка с использованием побитовых операций

Прежде всего, это домашнее задание, и я нашел еще одну тему, посвященную той же теме, но ответа не было. Вот проблема:

Сортировка по битам основана на предположении, что значения, подлежащие сортировке, представляют собой биты 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;
}

0

c++radix sorting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Прежде всего, вам не нужно преобразовывать целое число в биты, потому что оно уже хранится в виде битов. int обычно 4 байта, поэтому 32 бита. Вы можете получить доступ к битам, используя битовые операторы.

Корень сортировки показан здесь подробно. https://en.wikipedia.org/wiki/Radix_sort

Этот пример сортируется на основе 10 основных цифр.

Чтобы отсортировать по битам, вы должны немного изменить алгоритм, чтобы использовать 2 вместо 10 во всех местах:

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++;
...
}
}

Это сортировка с использованием двух битов, поэтому 4 сегмента используются для 00, 01, 10 и 11. 3 бита будут использовать 8 сегментов (000, 001, 010, 011, 100, 101, 110, 111).

Вы можете видеть, как увеличение BITS сделает меньше проходов, но работа, выполняемая за каждый проход, больше.

5