C++로 구현된 기수 정렬

Question

나는 1에서 10^6 사이의 많은 숫자를 사용하는 프로그램을 만들어 C++를 개선하려고 합니다.각 패스의 숫자를 저장할 버킷은 노드 배열입니다(여기서 노드는 값과 다음 노드 속성을 포함하여 제가 만든 구조체입니다).

가장 중요하지 않은 값에 따라 숫자를 버킷으로 정렬한 후 한 버킷의 끝이 다른 버킷의 시작 부분을 가리킵니다(순서를 방해하지 않고 숫자를 빠르게 저장할 수 있도록).내 코드에는 오류(컴파일 또는 런타임)가 없지만 나머지 6개의 반복을 어떻게 해결해야 할지에 관해 벽에 부딪혔습니다(숫자 범위를 알고 있기 때문에).

내가 겪고 있는 문제는 처음에 숫자가 int 배열 형태로 radixSort 함수에 제공되었다는 것입니다.첫 번째 정렬 반복 후 이제 숫자가 구조체 배열에 저장됩니다.7번의 반복에 대해 하나의 for 루프만 갖도록 코드를 재작업할 수 있는 방법이 있습니까? 아니면 한 번 실행되는 하나의 for 루프가 필요하고 그 아래에 완전히 정렬된 결과를 반환하기 전에 6번 실행되는 또 다른 루프가 필요합니까? 목록?

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new node;
    item->value=value;
    item->next=NULL;
    end[n]=item;
    if(bucket[n]->next==NULL)
    {
        cout << "Bucket " << n << " is empty" <<endl;
        bucket[n]->next=item;
        ptr[n]=item;
    }
    else
    {
        cout << "Bucket " << n << " is not empty" <<endl;
        temp=bucket[n];
        while(temp->next!=NULL){
            temp=temp->next;
        }
        temp->next=item;
    }
}

bool isBucketEmpty(int n){
    if(bucket[n]->next!=NULL)
        return false;
    else
        return true;
}
//print the contents of all buckets in order
void printBucket(){
    temp=bucket[0]->next;
    int i=0;
    while(i<10){
        if(temp==NULL){
            i++;
            temp=bucket[i]->next;                       
        }
        else break;

    }
    linkedpointer=temp;
    while(temp!=NULL){
        cout << temp->value <<endl;
        temp=temp->next;
    }
}

void radixSort(int *list, int length){
    int i,j,k,l;
    int x;
    for(i=0;i<10;i++){
        bucket[i]=new node;
        ptr[i]=new node;
        ptr[i]->next=NULL;
        end[i]=new node;
    }
    linkedpointer=new node;

    //Perform radix sort
    for(i=0;i<1;i++){
        for(j=0;j<length;j++){          
            x=(int)(*(list+j)/pow(10,i))%10;            
            append(*(list+j),x);
            printBucket(x); 
        }//End of insertion loop
        k=0,l=1;

        //Linking loop: Link end of one linked list to the front of another
        for(j=0;j<9;j++){
            if(isBucketEmpty(k))
                k++;
            if(isBucketEmpty(l) && l!=9)
                l++;
            if(!isBucketEmpty(k) && !isBucketEmpty(l)){
                end[k]->next=ptr[l];
                k++;
                if(l!=9) l++;   
            }

        }//End of linking for loop

        cout << "Print results" <<endl;
        printBucket();

        for(j=0;j<10;j++)
            bucket[i]->next=NULL;                       
        cout << "End of iteration" <<endl;
    }//End of radix sort loop
}

int main(){
    int testcases,i,input;
    cin >> testcases;
    int list[testcases];
    int *ptr=&list[0];
    for(i=0;i<testcases;i++){
        cin>>list[i];
    }

    radixSort(ptr,testcases);
    return 0;
}

Answer 1

솔루션을 심하게 복잡하게 복잡하게 생각합니다. 입력에서 수신 한 단일 배열을 사용하여 Radix를 구현할 수 있으며, 각 단계의 버킷은 입력 배열에서 각 버킷의 시작 인덱스를 표시하는 인덱스 배열로 표시됩니다.

사실, 당신은 그것을 재귀 적으로 할 수도 있습니다.

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

물론 buckets[i+1] - buckets[i] 버퍼 오버플로가 발생합니다 i 9 세이지만 추가 점검이나 가독성을 생략했습니다. 나는 당신이 그것을 처리하는 방법을 알고 있다고 믿습니다.

그것으로, 당신은 그냥 전화해야합니다 radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) 배열을 정렬해야합니다.

Answer 2

더 나은 메모리 관리로 프로세스 속도를 높이려면 배열에 대한 단일 패스를 만들어 인덱스로 변환되는 개수에 대한 행렬을 만듭니다.원래 배열과 동일한 크기의 두 번째 임시 배열을 할당하고 배열이 정렬될 때까지 두 배열 사이에 기수 정렬을 수행합니다.홀수 기수 정렬 패스가 ​​수행되면 마지막에 임시 배열을 원래 배열로 다시 복사해야 합니다.

프로세스 속도를 더욱 높이려면 기수 정렬에 기본 10 대신 기본 256을 사용하십시오.행렬을 생성하는 데는 1개의 스캔 패스만 필요하고 정렬을 수행하려면 4개의 기수 정렬 패스만 필요합니다.예제 코드:

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

Answer 3

귀하의 값은 0 ... 1,000,000 범위의 int이므로

크기 1,000,001의 int 배열을 만들 수 있고 두 번의 패스로 모든 일을 할 수 있습니다.

두 번째 배열을 모든 0에 시작하십시오.

입력 배열을 통과하고 값을 첨자로 사용하여 두 번째 배열에서 값을 증가시킵니다.

일단 그렇게하면 두 번째 패스는 쉽습니다. 두 번째 배열을 걸어 가면 각 요소는 원래 배열에 그 숫자가 몇 배나 나타 났는지 알려줍니다. 해당 정보를 사용하여 입력 배열을 다시 채 웁니다.