비트 단위 연산을 사용하는 기수 정렬

Question

우선이 것은 숙제이며 같은 주제에 대해 다른 주제를 찾았지만 대답이 없습니다.

정렬 할 값이 정수 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; 
} 

Answer 1

우선 이미 저장되어 있기 때문에, 당신은 비트 정수로 변환 할 필요가 없습니다 비트. int은 일반적으로 4 바이트이므로 32 비트입니다. 비트 연산자를 사용하여 비트에 액세스 할 수 있습니다.

여기에 기수 정렬이 자세히 나와 있습니다. https://en.wikipedia.org/wiki/Radix_sort

이 예제에서는 기준 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 대신 10을 사용하는 약간 알고리즘을 바꿀 것 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++; 
... 
    } 
} 

이 종류의 단일 비트를 사용. 여러 비트를 사용하려면, 당신은 더 일반적인해야 할 것 : 그래서 4 버킷 00에 사용되는 2 비트, 01, 10, 11 3 비트를 사용

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

이 종류의 8 버킷을 사용합니다 (000, 001, 010, 011, 100, 101, 110, 111).

BITS를 늘리면 패스가 줄어들지 만 각 패스에서 수행되는 작업이 얼마나 커지는 지 알 수 있습니다.