BucketSort 알고리즘 작동 방법

Question

C++에서 bucketsort 알고리즘을 만들려고하는데 전혀 작동하지 않습니다. 매번 실행하면 많은 새로운 수를 추가합니다. 수십억에 이르는 수 많은 수의 수를 배열에 추가합니다. 아무도 이것이 왜 있는지 압니까? 여기에 코드가 있습니다. (0부터 ~ 37000까지의 임의의 숫자로 배열 100을 전달한다는 점에 유의하십시오. 그리고 삽입 정렬 함수는 완전히 기능적이며 여러 번 테스트되었습니다.)

크게 감사하겠습니다. 누군가 잘못 된 것을 지적 할 수 있다면.

void bucketSort(int* n, int k) 
{ 
    int c = int(floor(k/10)), s = *n, l = *n; 
    for(int i = 0; i < k; i++) { 
     if(s > *(n + i)) s = *(n + i); 
     else if(l < *(n + i)) l = *(n + i); 
    } 
    int bucket[c][k + 1]; 
    for(int i = 0; i < c; i++) { 
     bucket[i][k] = 0; 
    } 

    for(int i = 0; i < k; i++) { 
     for(int j = 0; j < c; j++) { 
      if(*(n + i) >= (l - s)*j/c) { 
       continue; 
      } else { 
       bucket[j][bucket[j][k]++] = *(n + i); 
       break; 
      } 
     } 
    } 

    for(int i = 0; i < c; i++) { 
     insertionSort(&bucket[i][0], k); 
    } 
} 

Answer 1

이 줄은 컴파일되지 않습니다. int bucket[c][k + 1];

나는 문제가 당신과 함께 버킷 인덱스라고 생각합니다. 그것은 하나의 인덱스를 끊으

insert n[i] into bucket[ bucketIndexFor(n[i]) ] 

첫째 :이 부분은 여기

for(int j = 0; j < c; j++) { 
    if(*(n + i) >= (l - s)*j/c) { 
     continue; 
    } else { 
     bucket[j][bucket[j][k]++] = *(n + i); 
     break; 
    } 
} 

는에 해당하지 않습니다. 그 때문에 마지막 버킷의 번호에 대한 중단도 놓치게됩니다. 인덱스 계산에서 [s,l] 대신 [0,l-s] 범위를 사용하기 때문에 작은 오류가 발생합니다. 이는 s이 0 인 경우에만 동일합니다. 나뿐만 bucketIndex 쓸 때

는 :

int bucketIndex(int n, int c, int s, int l) 
{ 
    for(int j = 1; j <= c; j++) { 
     if(n > s + (l-s)*j/c) { 
      continue; 
     } else { 
      return j-1; 
     } 
    } 
    return c-1; 
} 

과 같은 알고리즘의 주요 부분을 다시 작성 :

std::vector< std::vector<int> > bucket(c); 

for(int i = 0; i < k; i++) { 
    bucket[ bucketIndex(n[i], c, s, l) ].push_back(n[i]); 
} 

내가 제대로 자신의 버킷에 삽입 된 항목을 얻을.