버킷 정렬 (bucket sort) 알아보기

반응형

이번 포스팅도 정렬에 관한 내용입니다. 기왕 정렬에 관해 적는 것을 시작했으니 다 훑어보는게 좋겠다는 생각이 들었습니다. 사실 정렬은 방법이 워낙 다양합니다. 저 역시도 모르는 정렬 방법이 많죠. 그러나 기본적인 정렬 방법 몇 가지와 nlogn 방법 몇 가지, 그리고 버킷 정렬과 계수 정렬 정도 알고 있다면 현업이나 코딩 테스트에서는 전혀 문제되지 않는다고 생각합니다. 저 역시도 현재까지 알고 있는 정렬 방법으로 현업에서 잘 사용하고 있습니다.

 

제가 생각하는 중요 정렬 방법 중 한 가지인 버킷 정렬은 개념적으로는 이해하기 쉽습니다. 프로그래밍 문제 풀이에 익숙하지 않던 시절에는 버킷 정렬에 관한 설명을 보고 '읭?' 스러웠던 기억이 있습니다. 분명 설명대로 따라하면 정렬이 되는 것 같긴 한데 이것 자체로 정렬이 되는 것은 아니다 보니 이게 방법이라고 구분지어 말할만 한 것인지 의문이 들었죠. 그러나 버킷 정렬은 분명 강력한 정렬 방법 중 하나이고 코딩 테스트에서도 종종 활용되는 개념이기 때문에 중요합니다. '버킷'이라는 개념을 머릿 속에 넣는 것 자체로도 버킷 정렬이 갖는 중요도는 충분한 것 같습니다.

 

버킷이란

우선 버킷에 대해 알아보겠습니다. 버킷은 문자 그대로 양동이라는 뜻입니다. 어떤 수열이나 문자의 집합 등이 있다고 할 때 이것을 나눈다고 가정해 보겠습니다. 이 때 양동이를 여러 개를 두고 기준에 따라 양동이에 수나 문자열을 집어 넣는다고 생각할 수 있습니다. 만약 양동이에 넣는 것이 숫자라면 숫자의 크기에 따라 양동이를 구분지어 넣을 수 있을 것이고, 문자열을 대상으로 한다면 알파벳 첫 글자에 따라 양동이를 구분 지어 문자열을 구분할 수 있을 것입니다.

 

버킷 정렬

버킷 정렬은 수열을 적절한 범위로 나누어 버킷의 범위를 정하고, 그 범위에 따라 숫자를 버킷에 할당하여 정렬하는 방법입니다. 여기서 알 수 있는 사실은 버킷의 크기를 결정하는 것이 중요한 요소라는 것입니다. 적절한 버킷의 크기는 문제에 따라 달라지기 때문에 사용자가 적절한 수준을 정해야 한다는 특징이 있습니다. 일반적으로 숫자를 정렬한다고 하면 버킷을 0 부터 9까지 총 10개로 설정하고, 그 값에 따라 수를 버킷에 할당하면 됩니다. 만약 수의 범위가 크다면 50 이나 100 단위로 묶어서 버킷에 담을 수 있습니다.

 

버킷 정렬을 처음 보시는 분들이라면 여기서 의문이 들 수 있는 점이 있을 것입니다. 만약 버킷에 여러 수가 할당된다면 그 안에서는 어떻게 정렬을 할까요? 이러한 의문이 들었다면 버킷 정렬을 올바르게 이해하고 있는 것입니다 ^^ 버킷에 2개 이상의 값이 있는 경우에는 그 안에서 다시 정렬을 해야 합니다. 이 때는 지난 포스팅에서 알아본 간단한 방식의 정렬 방법 (버블, 선택, 삽입 정렬 등)을 활용하여 정렬합니다. 버킷으로 수열을 작게 나눠 놓았으니 n^2 속도의 정렬 방법을 사용하더라도 크게 느리지는 않을 거라는 생각입니다.

 

버킷 정렬은 모든 버킷에 골고루 수가 할당될 수 있게끔 버킷의 크기를 잘 설정하는 것이 중요하다고 말씀드렸지만, 기본적으로 수의 분포가 어느정도 일정하게 퍼져 있어야 사용하기에 용이합니다. 만약 특정 버킷에 대부분의 수가 몰려 있다면 전체 수열을 정렬하는 것과 크게 다르지 않게 됩니다. 이 때는 버킷의 크기를 조금 더 작게 설정하여 한 곳에 몰린 수열을 퍼뜨리는 것이 중요합니다.

 

이상적으로 버킷 정렬의 시간복잡도는 O(n) 입니다. 수열을 한번만 훑어서 버킷에 할당시키고, 각 버킷에 수들이 적은 개수로만 존재한다면 거의 선형 시간만으로 정렬을 시킬 수 있게 됩니다. 하지만 앞서 언급한 최악의 경우에는 그냥 버킷 정렬을 사용하지 않고 정렬하는 것과 동일하게 걸릴 수도 있습니다.

 

 

버킷 정렬의 구현 방법

버킷 정렬을 구현하는 방법은 크게 두가지를 소개드릴 수 있을 것 같습니다. 첫 번째로는 배열을 활용하는 방법입니다. 이 경우 각 버킷에 들어갈 숫자의 적당한 개수를 파악해야 배열을 선언할 때 메모리를 낭비하지 않을 수 있게 됩니다. 두 번째 방법으로는 링크드 리스트를 활용하는 방법입니다. 각 버킷에 속한 수를 링크드 리스트로 연결하고 그 수들을 대상으로 정렬을 시킬 수 있습니다.

 

버킷 정렬은 다음 포스팅에서 다뤄볼 계수 정렬의 일반화된 형태라고 할 수 있습니다. 사용자의 선택 사항에 따라 성능이 좌우될 수 있는 방법인 만큼 문제 상황에 따라 적절한 버킷을 설정하는 연습이 필요한 방법입니다. 다양한 상황을 가정해보고 버킷 정렬을 구현해보면서 감각을 익히면 좋을 것 같습니다.