도수 정렬
요소들의 대소관계를 직접 비교하지 않고 빠르게 정렬할 수 있는 알고리즘.
도수정렬의 경우 정렬기준에 따른 요소들 사이의 직접적인 비교를 할 필요가 없다.
총 4단계 과정을 통하여 요소들을 정렬할 수 있다.
- 도수분포표 만들기
- 만들어진 도수분포표를 활용하여 누적 도수분포표 만들기
- 목표 배열 만들기
- 배열 복사하기
위에 4개의 단계를 전체적인 코드를 통하여 부분적으로 확인해보고자 한다.
//도수정렬
static void countionSort(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]]++;
for(int i = 1 ; i < f.length; i++) f[i] += f[i-1];
for(int i = n -1 ; i >= 0 ; i--) b[--f[a[i]]] =a[i];
for(int i = 0 ; i < n ; i++) a[i] = b[i];
}
//메인함수
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("도수 정렬");
System.out.print("요솟수 : ");
int nx = s.nextInt();
int x[] = new int[nx];
for(int i = 0 ; i < nx ; i++){
do{
System.out.print("x["+i+"] : ");
x[i] = s.nextInt();
}while(x[i]<0);
}
int max = x[0];
for(int i = 1 ; i < nx ; i++)
if(x[i] > max) max = x[i];
countionSort(x,nx,max);
System.out.println("오름차순으로 정렬했습니다");
for(int i = 0 ; i < nx ; i++)
System.out.println("x[" + i + "] = " + x[i]);
}전체코드를 기반으로 단계별 부분적인 코드들을 확인해보자
여기서 한가지 볼 것은 도수분포표를 만들기 위해서 요수들의 최대값을 구하고 시작한다는 것이다.
Step1) 도수분포표 만들기
static void countionSort(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]]++;
//for(int i = 1 ; i < f.length; i++) f[i] += f[i-1];
//for(int i = n -1 ; i >= 0 ; i--) b[--f[a[i]]] =a[i];
//for(int i = 0 ; i < n ; i++) a[i] = b[i];
}max값을 함께 매개변수로 전달받아 도수분포표를 만들기 위한 배열을 만든다. 이때 max는 실제 값이기에 배열을 만들때 max+1로 만든다.
아래 결과를 출력해보면 초기 배열에 대해서 다음과 같이 도수 분포표가 만들어진다.
Step2) 누적도수분포표 만들기
static void countionSort(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]]++;
for(int i = 1 ; i < f.length; i++) f[i] += f[i-1];
//for(int i = n -1 ; i >= 0 ; i--) b[--f[a[i]]] =a[i];
//for(int i = 0 ; i < n ; i++) a[i] = b[i];
}도수분포표를 기준으로 누적도수분포표를 만든다. 이때 실제 누적되는 것은 1번부터 앞에 누적된 도수에 현재 도수를 더해지게 된다.
Step3) 목표 배열 만들기
static void countionSort(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]]++;
for(int i = 1 ; i < f.length; i++) f[i] += f[i-1];
for(int i = n -1 ; i >= 0 ; i--) b[--f[a[i]]] =a[i];
//for(int i = 0 ; i < n ; i++) a[i] = b[i];
}step3에서 헷갈릴 수 있다고 생각하는데, 여기서 핵심은 기존배열에는 요소들의 실제 값들이 들어있고, 이를 활용하여 도수분포표, 누적도수분포표를 통하여 배열에서 0~max까지 범위에서 각각의 값들이 몇 개가 존재하는가 ? 해당 위치까지는 몇 개가 존재하는가?를 구했다. 이를 활용하여 기존에 배열에서 요소의 값이 어느 위치에 있어야하는 지를 분포표 배열을 활용하여 정렬하는 것이다. 예를 들어 아래 결과를 보면
마지막 요소인 13을 볼 때 인덱스 값은 9이다. 그럼 f[a[9]] = f[13] = 10이 된다. 즉 13이라는 값까지 총 10개의 요소가 있다는 것이다. 그리고 목표 배열에 이제 정렬시켜서 저장해야한다. 목표배열은 당연히 초기 배열과 크기가 같아야한다. 그리고 배열은 0번부터 시작하기에 현재 누적분포값에서 -1을 한 위치에 넣는다.
Step3) 배열 복사
static void countionSort(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]]++;
for(int i = 1 ; i < f.length; i++) f[i] += f[i-1];
for(int i = n -1 ; i >= 0 ; i--) b[--f[a[i]]] =a[i];
for(int i = 0 ; i < n ; i++) a[i] = b[i];
}이 부분은 단순 정렬된 배열을 초기 배열로 복사해서 초기 배열을 정렬된 배열로 만드는 것이다.