자료구조 - 정렬 7 (Bucket)

 

전체 정렬 개요의 설명은 여기를 참조
Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Radix 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조

 

 

1. Bucket Sort(버킷 정렬)

 

버킷 정렬은 전체 데이터가 특정 범위 안에 균등하게 분포되어 있다는 가정을 할 수 있을 때 매우 유용하게 쓰일 수 있는 정렬 알고리즘이다. 

예를 들어, 전체 데이터가 0.0 이상 1.0 미만의 범위 안에 있는데 이 데이터가 매우 소수점 자리수가 많고 균등하게 굉장히 많은 값들이 분포되어 있다고 가정하자.

그러면, 해당 데이터들을 정렬할 때 사용할 수 있는 방식은 기존에 포스팅한 비교를 기반으로 하는 Heap, Bubble, Insertion, Selection, Quick... 등이 있을 수 있다. 그러나 이러한 정렬은 아무리 좋은 성능을 내도 O(nlogn) 수준에서 그친다.

선형 시간 O(n) 수준으로 성능을 끌어올릴 수 없을까? Counting Sort(계수 정렬)은 어떨까? 물론 불가능한 것은 아니지만 데이터의 크기에 따라 영향을 받는 정렬이므로 적합하지 않을 수 있다.

Radix Sort(기수 정렬)은 어떨까? 이 또한 가능할 수 있다. 하지만 Radix Sort로 정렬하기 적합하도록 전체 데이터 중 가장 큰 길이가 어느 수준인지를 파악하기 위한 작업이 추가로 수반될 수 있다.

이 때는, Bucket Sort(버킷 정렬) 방식이 좀 더 적합하다.

 

버킷 정렬의 특징은 다음과 같다.

 

특성	설명
Not In-place 알고리즘	배열을 나누는 과정에서 나누어진 배열을 별도로 저장할 공간이 필요하다.
Stable 알고리즘	구현에 따라 다르나, 같은 값의 데이터의 기존 순서 유지를 보장할 수 있다.

 

버킷 정렬의 시간  / 공간 복잡도는 아래와 같다.

알고리즘	시간복잡도(최상)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
버킷 정렬	O(n)	O(n)	O(n)	O(n)

 

 

2. 정렬 과정

 

버킷 정렬의 정렬 과정을 살펴보기 위해 다음과 같은 소수점 배열이 있다고 생각해보자.

 

소수점 배열

 

이제, 각 데이터를 별도로 저장할 Bucket을 생성한다. Bucket은 LinkedList를 저장하는 배열로 기존 데이터의 배열과 크기가 동일해야 한다.

 

Bucket 배열

 

그럼 이제, 각 Bucket에 기존의 데이터를 10(n)씩 곱한 값의 1의 자리수에 해당하는 Index에 추가하여 넣는다. 다 추가하면 아래와 같이 된다. 이 때, 각 List에 추가하면서 Insertion Sort를 수행하며 집어넣는다.

 

버킷에 데이터를 삽입 하며 정렬

 

이 때, 삽입 정렬을 수행하는데 왜 전체 시간복잡도가 O(n)이 될 수 있느냐는 의문이 날 수 있는데, 버킷 정렬은 애초에 전체 데이터가 균등하게 분포되어 있다는 가정을 통해 수행한다.

따라서, 그러한 가정이 있다면 평균적으로 O(n)을 유지하여 삽입할 수 있게 된다.

 

꼭 삽입 정렬로 정렬하지 않아도 된다. 아래 코드에서는 JDK에서 제공하는 자료구조 정렬을 사용하여 구현하였다.

위와 같이 정렬이 완료되면, 각 버킷의 데이터를 빼서 기존 배열에 삽입하면 전체 정렬이 완료된다.

 

 

3. 코드로 구현

 

package com.test;

import java.util.Collections;
import java.util.LinkedList;

public class BucketSort {
    public static void main(String[] args){

        // 전체 크기는 30으로 제한
        double[] arr = new double[30];
        for(int i=0; i < arr.length; i++){
            // 값의 범위는 0 ~ 1 까지의 소수점 2자리까지로 제한
            arr[i] = Math.round(Math.random() * 100) / 100.0;
        }
        bucketSort(arr);
        // 출력
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }

    public static void bucketSort(double[] arr){
        int n = arr.length;
        if(n <= 0) return;

        // 1) n 크기의 빈 Bucket을 생성한다.
        LinkedList<Double>[] bucket = new LinkedList[n];

        for(int i=0; i < n; i++){
            bucket[i] = new LinkedList<>();
        }

        // 2) 기존 데이터 값에 n을 곱해 bucket에 넣는다.
        for(int i=0; i < n; i++){
            int idx = (int)(arr[i] * n);
            bucket[idx].add(arr[i]);
        }

        // 3) 각 Bucket을 정렬한다. 여기선 간단하게 기존 Library 사용
        for(int i=0; i < n; i++){
            Collections.sort(bucket[i]);
        }

        // 4) bucket에 저장한 값을 빼서 기존 배열에 다시 삽입
        int index = 0;
        for(int i=0; i < n; i++){
            for(int j=0; j < bucket[i].size(); j++){
                arr[index++] = bucket[i].get(j);
            }
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 댓글로 알려주시면 수정하겠습니다.

 

감사합니다.