정렬 - 도수 정렬

주빈·2022년 3월 3일

algorithm

목록 보기

13/16

오늘은 정렬의 마지막 도수 정렬을 알아보자.

📘 도수 정렬이란?

지금까지의 정렬 알고리즘은 두 요소의 키 값을 비교해야 했지만 도수 정렬은 요소의 대소 관계를 비교하여 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.
도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사로
4단계로 이루어져있다.

📜 도수 정렬의 원리

도수 정렬은 4단계로 나누어져있기 때문에 4단계로 나누어서 원리를 살펴보자.

✏ 1단계 - 도수분포표 만들기

먼저 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표를 작성한다.
도수 분포표를 나타내기 위해 배열 f를 사용한다.
먼저 배열 f의 모든 요소의 값을 0으로 초기화하고 배열 a를 처음부터 스캔하면서 도수분포표를 만든다.
ex) a[0]은 5점이므로 f[5]를 1증가, a[1]은 7점이므로 f[7]을 1만큼 증가

✏ 2단계 - 누적도수분포표 만들기

이번에는 '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표를 만들자.
다음 그림은 배열 f의 두 번째 요소부터 바로 앞의 요솟값을 더하는 과정이다.
가장 마지막 그림이 누적도수분포표의 완성된 모습이다.

✏ 3단계 - 목적 배열 만들기

각각의 점수를 받은 학생이 몇 번째에 위치하는지 알 수 있으므로 이 시점에서 정렬은 거의 마친 것이다.

for (int i = 1; i <= max; i++) 
	f[i] += f[i - 1];

남은 작업은 배열의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열을 만드는 작업이다.
이 작업에서는 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b가 필요하다.
그러고 배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하며 배열 f와 대조하는 작업을 수행한다.

b[--f[a[i]]] = a[i];

그림을 보면 마지막 요소(a[8])의 값은 3이다. 누적도수를 나타내는 배열(f[3])의 값이 5이므로 0 ~ 3점 사이에 5명이 있다는 것을 알 수 있다. 그러므로 목적 배열인 b[4]에 3을 저장한다.

✏ 4단계 - 배열 복사하기

정렬은 끝났지만 정렬된 결과는 작업용 배열인 b에 저장되어 있기 때문에 배열 a로 복사를 해야한다.

for(int i = 0; i < n; i++)
	a[i] = b[i];

📜 도수 정렬 코드

도수 정렬 프로그램을 한번 만들어보자.

import java.util.Scanner;

public class FSort {
    // 도수 정렬(0 이상 max 이하의 값을 입력)
    static void fSort(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 >= n;     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 num = sc.nextInt();
        int[] a = new int[num];

        for (int i = 0; i < num; i++) {
            do {
                System.out.print("x[" + i + "] : ");
                a[i] = sc.nextInt();
            } while (a[i] < 0);
        }
        
        int max = a[0];
        for (int i = 1; i < num; i++)
            if (a[i] > max) max = a[i];
            
            fSort(a, num, max); // 배열 a를 도수 정렬

        System.out.println("오름차순으로 정렬");
        for (int i = 0; i < num; i++)
            System.out.println("x[" + i + "] = " + a[i]);
    }
}

fSort

fSort 메서드는 배열의 모든 요솟값이 0 이상 max 이하일때를 전제로 배열 a에 대해서 도수 정렬을 수행한다.
또한 정렬을 위한 작업용 배열 f와 b를 만든다.
배열 f는 초깃값으로 모든 요소가 0으로 초기화가 되어 있기 때문에 0을 대입하지 않아도 된다.
배열 f는 인덱스로 0 ~ max가 필요하므로 총 요소의 개수는 max + 1이 된다

위의 프로그램에서 총 4단계의 for문을 거친다. 첫 번째 for문부터 도수분포표 만들기, 누적도수분포표 만들기, 목적 배열 만들기, 배열 복사하기의 4단계이다.

도수 정렬 알고리즘은 데이터의 비교 교환 작업이 필요없어 매우 빠르다. 단일 for문만을 사용해 재쉬 호출, 이중 for문이 없어서 아주 효율적인 알고리즘이다.
하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용이 가능하다.