도수 정렬이란?
도수 정렬이란? 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 다른 말로는 계수 정렬이라고도한다.
영문으로는 Counting Sort로 불린다.
도수 정렬은 가장 큰 데이터에 따라 효율이 달라지는 특징이 있다.
도수 정렬의 시간 복잡도
도수 정렬의 시간복잡도는 O(n + k) 이다. 여기서 k는 데이터의 최댓값을 의미한다. k의 값에 전적으로 성능을 의지하기에 k의 값이 작다면 선형시간을 기대할 수 있다.
k의 값이 천만~억단위가 넘어가면 메모리도 굉장히 많이 사용하며, 성능도 엉망이 되기에 모든 자료에 범용적으로 사용할 수 있는 알고리즘은 아니다.
도수 정렬 알아보기
거의 모든 정렬 알고리즘은 두 요소의 키값을 비교해야했다. 하지만 이 절에서 다루는 도수 정렬은 요소를 비교할 필요가 없다. 10점 만점의 테스트에서 학생 9명의 점수를 예로 들어 도수 정렬 알고리즘을 살펴보자.
도수 정렬 알고리즘은 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 등 4단계로 이루어져있다.
1단계: 도수분포표 만들기
먼저 배열 a(9명 학생의 점수)를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표를 작성하자. 도수 분포표를 저장하기 위해 배열f를 사용한다. 먼저 배열 f(도수분포표)의 모든 요솟값을 0으로 초기화한다. 그런 다음 배열 a를 처음부터 스캔하면서 도수분포표를 만든다. a[0]은 5점이므로 f[5]를 1 증가시켜 1로만든다. a[1]은 7점이므로 f[7]을 1증가시켜 1로 만든다.
int[] a = {5,7,0,2,4,10,3,1,3}; // 각 index의 학생이 받은 점수. 0~10점 가능
int[] f = new int[11]; // 0을 포함한 10점이 최대이기에 length = 11로 만들자.
// 모르는 사람은 없겠지만 배열의 모든 요소는 0으로 초기화된다.
for (int i = 0; i < a.length; i++) {
f[a[i]]++; // f[a[0]]++; → f[5]++ → f[5] = f[5] + 1;
}
// 실행 후 f배열 {1,1,1,2,1,1,0,1,0,0,1};
// f배열의 4번째 요소가 2인것으로 보아 3점맞은 학생이 2명임.2단계: 누적도수분포표 만들기
이제 '0점부터 n점까지 몇 명의 학생이 있는지' 누적한 값을 나타내는 누적도수분포표를 만들어보자.
누적도수분포표란? 각각의 값 이하의 요소가 모두 몇 개 있는가?
int[] f = {1,1,1,2,1,1,0,1,0,0,1}; // 위 예제 그대로임.
for (int i = 1; i <= max; i++) {
// max는 점수의 최대값인 10으로 설정됨.
// 어차피 f[0]이하의 요소는 f[0]밖에 없으므로 패스해도되기에 1부터 시작.
// ex) f[1] = f[0] + f[1] --> f[1] = 2, f[2] = f[1] + f[2] --> f[2] = 3
f[i] += f[i - 1];
}위의 방식으로 배열f의 누적도수분포표를 만든 값은 아래와 같다.
int[] f = {1,2,3,5,6,7,7,8,8,8,9};3단계: 목표 배열 만들기
각각의 점수를 받은 학생이 몇 번째에 위치하는지 알 수 있으므로 이 시점에서 정렬은 거의 끝마쳤다고 할 수 있다.
int[] b = new int[a.length];
for (int i = a.length-1; i >= 0; i--)
b[--f[a[i]]] = a[i];위 반복문을 사용해서 만들예정인데, 복잡해 보이지만 한번 이해하면 쉽다.
거의 다 왔다. 남은 작업은 배열 a의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열을 만드는 일이다.
이 작업은 배열 a와 같은 요솟수를 갖는 작업용 배열 b가 필요하다.
a를 스캔해서 배열 f와 대조해보자.
- 요소 a[8]
마지막 요소인a[8]의 값은 3이다. 누적도수를 나타내는 배열 f[3]값이 5이므로, 0~3점 사이에 5명이 있음을 알 수 있다.
int[] a = {5,7,0,2,4,10,3,1,3};
int[] f = {1,2,3,4,6,7,7,8,8,8,9};
// f[3]의 값을 5에서 1로 감소시켜 4로 업데이트한다. 이유는 아래.
int[] b = {0,0,0,0,3,0,0,0,0};
// 3점은 5번째 값이므로 5번째 위치인 b[4]에 값 3을 저장한다.이 작업을 할 때 f[3]값을 5에서 1로 감소시켜 4로 업데이트 한다. 그 이유는 아래에서 설명한다.
- 요소 a[7]
a[8]의 바로앞 요소a[7]의 값은 1이다. 누적도수를 나타내는 f[1]값은 2로 0~1점 사이에 2명이 있다는 것을 의미한다.
따라서 작업용 목표 배열 b[1]에 1을 저장한다.
int[] a = {5,7,0,2,4,10,3,1,3};
int[] f = {1,1,3,4,6,7,7,8,8,8,9};
// f[1]의 값을 2에서 1로 감소시켜 1로 업데이트한다. 이유는 아래.
int[] b = {0,1,0,0,3,0,0,0,0};
// 1점은 2번째 값이므로 2번째 위치인 b[1]에 값 1을 저장한다.- 요소 a[6]
다음 요소인 3을 선택한다. a[8]도 3이었기에 2번째는 다르게 진행되어야 한다. 앞에서 a[8]의 값인 3을 b배열에 넣을 때, f[3]을 1감소시켜 4로 저장했었다. 이렇게 미리 값을 감소시켰기에 중복되는 3을 목표 배열의 4번째 요소b[3]에 저장하기 매우 편리하다.
int[] a = {5,7,0,2,4,10,3,1,3};
int[] f = {1,1,3,3,6,7,7,8,8,8,9};
// f[3]의 값을 4에서 3으로 감소시킨다. 필요없지만 생략이 불가능한 부분.
int[] b = {0,1,0,3,3,0,0,0,0};
// 3점은 4번째 값이므로 4번째 위치인 b[3]에 값 3을 저장한다.위의 작업을 a[0]까지 진행하면 배열 a의 모든 요소를 배열 b의 알맞은 윛치에 저장 가능하다.
4단계: 배열 복사하기
b는 작업용 배열로 만들었기에 a에 b의 값을 그대로 옮겨주자.
for (int i = 0; i < a.length; i++) {
a[i] = b[i];
}도수 정렬 예제 코드
public class CountingSort {
// 도수 정렬(0 이상 max 이하의 값을 입력)
static void countingSort(int[] a, int n, int max) {
int[] f = new int[max + 1]; // 누적 도수
int[] b = new int[n]; // 작업용 목표 배열;
for (int i = 0; i < n; i++) f[a[i]]++; // 1단계
for (int i = 1; i <= max; i++) f[i] += f[i - 1]; // 2단계
for (int i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i]; // 3단계
for (int i = 0; i < n; i++) a[i] = b[i]; // 4단계
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 :");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
} while (x[i] < 0); // 0이상의 수만 정렬가능.
}
int max = x[0];
for (int i = 0; i < x.length; i++) // 배열중 최댓값 구해서 max에 대입해 두기.
if (x[i] > max) max = x[i];
countingSort(x, x.length, max);
System.out.println("도수 정렬 완료");
for (int i = 0; i < x.length; i++)
System.out.println("x[" + i + "]= " + x[i]);
}
}위 메서드는 배열의 요소들이 0이상이어야 정렬 가능하다.
do-while문을 제외하고 음수를 넣게되면 아래처럼 오류가 발생할 수 밖에 없는 구조이다..
정리
배열 f는 인덱스로 0~max가 필요하므로 총 요솟수는 max + 1이다. 그리고 목표 배열 b는 정렬 결과를 임시로 저장하는 배열이므로 요솟수는 배열 a와 같다(n). 그리고 여기서의 max가 위의 시간 복잡도 설명의 k이다.
도수 정렬 알고리즘은 데이터를 비교, 교환하지않으며, 다중 for문을 사용하지 않고 재귀호출도 없어 매우 빠른 알고리즘이다. 다만 데이터의 최솟값과 최대값을 미리 알고 있어야 한다.
각 단계에서 배열의 요소를 건너뛰지 않고 순서대로 스캔하기에 같은 값의 순서가 바뀌는 일이 없으므로 안정적인 정렬이라 할 수있으나, 3단계 과정에서 배열a를 뒤→앞에서 스캔하지 않고, 앞→뒤로 스캔하게되면 안정적이지 않게된다.
