[C code] 버킷 정렬 (Bucket Sort)

버킷 정렬 또는 버킷 소트(Bucket sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬 알고리즘이다

(통에 담듯이)

각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다

 

버킷의 정렬은 다음과 같이 이루어진다:

 

1) 처음에 비어있는 버킷들의 배열을 배치한다

2) 분산 : 원래의 배열을 살펴보고 각 객체를 버킷에 담는다

3) 비어있지 않은 각 버킷을 정렬한다

4) 수집 : 순서대로 버킷을 방문하여 모든 요소를 원래의 배열에 위치시켜 놓는다.

 

아래 코드는 그림과 달리 소수 첫째자리로 구분하였다

 

#include <stdio.h>
#include <stdlib.h>

// Bucket Sort
void BucketSort(float arr[], int n)
{
    float bucket_arr[10][n] ;
    int count[10] = { 0, };
    int which_bucket, cnt=0;

    //bucket_arr에 정렬하기
    for(int i=0 ; i<n ; i++)
    {
        which_bucket = arr[i]/1;    //정수부분으로 나누기
        bucket_arr[which_bucket][count[which_bucket]] = arr[i];
        count[which_bucket]++;
    }

    //정렬된 bucket을 arr에 대입하기
    which_bucket = 0;
    while(which_bucket<10 && cnt<5)
    {
        for(int j=0 ; j<count[which_bucket] ; j++)
        {
            if(bucket_arr[which_bucket][j] != 0)
            {
                arr[cnt] = bucket_arr[which_bucket][j];
                cnt++;
            }
        }
        which_bucket++;
    }
}

// 배열 출력함수
void PrintArray(float arr[], int size)
{
   printf("\n**********************\n");
   for(int i=0 ; i<size ; i++)
   {
       printf("%10.3f", arr[i]);
   }
}

// 테스트 코드
int main()
{
    float array[5];
    int i = 0;

    // 10 미만 정수 5개 입력
    while(i<5)
    {
        printf("Put your %d floats ( < 10 ) : ", i);
        scanf("%f", array+i);
        if(array[i]>=0 && array[i]<10)
            i++;
    }

    int n = sizeof(array)/sizeof(array[0]);
    PrintArray(array, n);
    BucketSort(array, n);
    PrintArray(array, n);

    return 0;
}

 

버킷정렬은 범위의 입력된 값들이 균등하게 분포했을 때 주로 쓰인다

​

값을 비교하여 정렬하는 기법인 comparison sort의 계산복잡성은 최소 O(nlog⁡n) 이다

버킷 정렬은 분석 대상 데이터의 분포 특성을 활용해 계산복잡성을 O(n) 수준으로 개선시키려는 것을 목적으로 하고 있다

버킷 정렬은 데이터가 특정 범위 내에 확률적으로 균등하게 분포한다고 가정할 수 있을 때 적용할 만한 기법이다

​

이와 같은 코드를 반복 또는 합쳐 사용하면, 보다 정확한 정렬 알고리즘이 완성된다

​

- GeeksforGeeks

- ratsgo's blog

- 위키