문제 : 버킷정렬은 정렬하기 위해 하는 양의 정수를 가지는 1차원 배열, 0부터 9까지의 첨자를 사용하는 행과 0부터 n-1까지의 첨자를 사용하는 열로 구성되는 2차원 정수 배열을 사용한다. 여기서 n은 정렬할 배열에 있는 값의 수다. 2차원 배열의 각 행을 버킷(bucket)이라고 한다.

정수형 배열과 배열의 크기를 인수로 받아들이고 다음을 수행하는 함수 bucketSort를 작성하라.

 

a) 1차원 배열의 각 값을 1의 자리 값을 기준으로 버킷 배열의 행에 저장한다. 예를 들어 97은 행 7에 저장하고 3은 행 3에 저장하고 100은 행 0에 저장한다. 이것을 \'분배 과정\'이라고 한다.

b) 버킷 배열을 행 단위로 반복하면서 값을 원래 배열에 다시 복사한다. 이것을 \'수집 과정\'이라고 한다. 앞에서 저장한 1차원 배열의 값의 순서는 이제 100, 3, 97이 된다.

c) 나머지 자리(10의 자리, 100의 자리 등)에 대해서도 이 과정을 반복한다. 

 

두번째 반복에서 100은 행 0에 위치되고 3은 행 0에 위치되고 97은 행 9에 위치된다. 10의 자리를 기준으로 하므로 3은 10의 자리가 없으므로 행 0에 위치되는 것이다. 이제 수집 과정을 거치고 나면 1차원 배열의 값의 순서는 100, 3, 97이 된다. 세 번째 반복에서는 100 자리를 기준으로 하므로 100은 행 1에 위치되고 3은 행 0에 위치되고 97은 행 0에서 3 다음에 위치된다. 수집 과정 후의 원래 배열은 이제 정렬된 상태로 존재한다.

버킷으로 사용되는 2차원 배열이 정렬하기 원하는 정수 배열의 10배 크기라는 것에 주목하기 바란다. 그래서 이 정렬 기법은 삽입 정렬보다 나은 성능을 제공하지만 훨씬 많은 양의 메모리를 사용한다. 삽입 정렬은 하나의 추가 데이터 요소에 대한 공간을 필요로 했다. 이것은 공간과 시간 타협(space-time trade-off)의 예다. 버킷 정렬은 삽입 정렬보다 많은 양의 메모리를 사용하지만 훨씬 더 효율적이다. 여기서는 한 번 반복할 때마다 모든 데이터를 원래 배열에 다시 복사했었다. 다른 한가지 방법은 두 번째 2차원 버킷 배열을 생성하고 두 버킷 배열 사이에서 데이터를 반복적으로 교환하는 것이다.

 

답 :

void bucketSort(int data[], int size){

 int *bucket[10];
 int count = 0;
 int multi = 1;

 for(int i=0; i<10; i++){
  bucket[i] = new int[size];
 }

 for(int i=0; i<5; i++){
  
  multi*=10;

  for(int i=0; i<10; i++){
   for(int j=0; j<size; j++){
    bucket[i][j] = -1;
   }
  }
  
  for(int i=0; i<size; i++){
   
   int index = data[i]/(multi/10) - data[i]/multi*10;

   while(true){
   
    if(bucket[index][count] == -1){
     bucket[index][count] = data[i];
     break;
    } else {
     count++;
    }
   }
   count = 0;
  }

  for(int i=0; i<10; i++){
   for(int j=0; j<size; j++){
    if(bucket[i][j] != -1){
     data[count] = bucket[i][j];
     count++;
    }
   }
  }

  count = 0;
 }
 
 delete[]* bucket;
}

int main(){

 const int size = 15;

 //int data[size] = {2, 8, 14, 28, 1, 5, 41, 7, 23, 20, 18, 36, 11, 61, 22};
 int data[size] = {41, 111, 81, 31, 121, 131, 1, 71, 61, 141, 101, 11, 21, 51, 91};

 cout << \"정렬 전 : \";

 for(int i=0; i<size; i++){
 
  cout << data[i] << \" \";
 }

 cout << endl;

 bucketSort(data, size);

 cout << \"정렬 후 : \";

 for(int i=0; i<size; i++){
 
  cout << data[i] << \" \";
 }
 
 cout << endl;
 
 return 0;
}