기수 C++을 사용하여 정렬

Question

숫자가 있다고 가정합니다. 우선 가장 중요한 숫자를 해당 버킷에 넣어야합니다. 예 : 530, 먼저 양동이 0에 넣어야합니다. 숫자 61의 경우 버킷 1에 넣어야합니다.

이렇게하려면 다차원 배열을 사용하려고했습니다. 그래서 NROWS 2 dimenional 배열, (I 목록이 얼마나 큰 모르기 때문에)와 NCOLUMNS (0 ~ 9) 999999 10입니다 작성 :

int nrows = 10; 
    int ncolumns = 999999; 

    int **array_for_bucket = (int **)malloc(nrows * sizeof(int *)); 
     for(i = 0; i < nrows; i++) 
      array_for_bucket[i] = (int *)malloc(ncolumns * sizeof(int)); 

    left = (a->value)%10; 
    array_for_bucket[left][?? ] = a->value; 

은 그 때 나는 하나 개의 노드를 생성 전화. 이 노드 a에는 값 50이 있습니다. 어느 버킷을 넣을 지 알아 보려면 "왼쪽"을 계산하고 0을 얻습니다. 그래서이 버킷 0에이 값을 넣고 싶습니다.하지만 이제는 붙어있어. 이 값을 양동이에 넣으려면 어떻게해야합니까? 이 작업을 수행하려면 포인터 배열을 사용해야합니다.

오랫동안 생각했지만 여전히 좋은 방법을 찾지 못했습니다. 그러니 나와 함께 아이디어를 공유하십시오. 고맙습니다!

Answer 1

이렇게하는 것이 훨씬 쉬운 방법이며, radix*nkeys 대신에 nkeys 크기의 버퍼 만 있으면됩니다.

nkeys 키에 맞는 두 번째 버퍼를 할당하십시오. 이제 데이터를 처음으로 통과하고 각 버킷에서 몇 개의 키가 끝날지 계산하십시오. radix 크기 포인터 배열을 만들 수 있습니다. 각 포인터는 출력 버퍼에서 해당 버킷의 시작 위치에 있습니다. 마지막으로, 데이터가 키를 이동하지만 두 번째 패스. 키를 움직일 때마다 해당 버킷 포인터를 증가시킵니다.

void radix_sort(int *keys, int nkeys) 
{ 
    int *shadow = malloc(nkeys * sizeof(*keys)); 

    int bucket_count[10]; 
    int *bucket_ptrs[10]; 
    int i; 

    for (i = 0; i < 10; i++) 
     bucket_count[i] = 0; 

    for (i = 0; i < nkeys; i++) 
     bucket_count[keys[i] % 10]++; 

    bucket_ptrs[0] = shadow; 
    for (i = 1; i < 10; i++) 
     bucket_ptrs[i] = bucket_ptrs[i-1] + bucket_count[i-1]; 

    for (i = 0; i < nkeys; i++) 
     *(bucket_ptrs[keys[i] % 10]++) = keys[i]; 

    //shadow now has the sorted keys 

    free(shadow); 
} 

하지만 질문을 오해 할 수 있습니다

다음은 C++로 만들기 위해 몇 가지 C 코드입니다. 기수 정렬과 다른 약간의 일을한다면, 몇 가지 세부 사항을 추가하십시오.

Answer 2

포인터를 저장하려면 부스트 Pointer containers 라이브러리를보십시오.

Answer 3

C++은 나의 장점이 아니지만 wikipedia-Raidx Sort의이 코드는 매우 포괄적이며 아마도 지금까지 구현 한 것보다 더 많은 C++입니다. 도움이되기를 바랍니다.

Answer 4

이것은 C++이므로 더 이상 malloc을 사용하지 않습니다. 우리는 컨테이너를 사용합니다. 2 차원 배열은 벡터의 벡터입니다.

vector<vector<int> > bucket(10); 
left = (a->value)%10; 
bucket[left].push_back(a->value);