선형시간 정렬 알고리즘 (1)

선형 시간 정렬 알고리즘 (1)

Counting Sort

- n개의 정수를 정렬하는데, 모든 정수는 0에서 k사이의 정수라는 사전 지식이 주어지는 정렬법이기 때문에 크기관계만을 이용하여 정렬하지 않고 사전 지식을 적극적으로 활용한다. (k의 크기도 비교적 작은 편이다.)

Ex) n명의 학생들의 시험점수를 정렬하라. 단 모든 정수는 100이하의 양의 정수이다.

- k = 5인 경우

A = 2 5 3 0 2 3 0 3 (n = 8)

C(counter) = 2 0 2 3 0 1 => 각 인덱스마다 A배열에서 해당 수가 몇개 들어있는지 세어 저장한다.

∴ A = 0 0 2 2 3 3 3 5

- 슈도 코드

int A[n];

int C[k] = {0, };

for (int i = 1; i <= n; i++)

C[A[i]]++;

for (int s = 1, i = 0; i <= l; i++)

for (int j = 0; j < C[i]; j++)

A[s++] = j;

->이 방식은 문제가 있다. 대부분의 경우 정렬할 키들은 레코드의 일부이기 때문이다. (Lee, 010~, 서울... 과 같이 있기 때문이다. 하여 같이 움직일 필요가 있다.)

- 레코드를 함께 정렬하기 위한 방법

누적합을 이용한다.

A배열의 값을 C로 옮길 때 2 0 2 3 0 1의 방식이 아닌 2 2 4 7 7 8과 같이 누적된 값을 저장한다.

누적합 C를 해석하여 넣을 B배열을 생성한다. 그 후 A를 역순으로 탐색하며 해당 값이 새로 저장될 인덱스를 찾는다. 이 때 C를 활용하는데 누적합의 결과인 데이터가 실제 B에 들어갈 인덱스를 가리키게 되는 것이다. B에 저장한 후에는 C의 해당 데이터를 셌던 인덱스의 값을 1줄여주며 이를 반복한다.

- 슈도 코드

Counting-Sort (A, B, k)

for i <- 0 to k

do C[i] <- 0

for j <- 1 to length[A]

do C[A[j]] <- C[A[j]] + 1 //이 작업으로 C[i]는 i와 같은 요소 수를 표시하게 된다.

for i <- 1 to k

//C[i - 1]은 이전 인덱스의 누적 합이다.

do C[i] <- C[i] + C[i - 1] //이 작업으로 C[i]는 i와 작거나 같은 요소 수를 표시하게 된다.

for j <- length[A] downto 1

do B[C[A[j]]] <- A[j]

     C[A[j]] <- C[A[j]] - 1

Counting Sort의 시간 복잡도

- Θ(n + k), 또는 Θ(n) if k = O(n). => 선형 시간 복잡도이다.

- 이 정렬은 k의 값이 커지면 커질수록 실용적이지 않게 된다.

- Stable한 정렬 알고리즘이다.

"입력에 동일한 값이 있을 때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다."

-> Counting Sort에서는 별로 중요하지 않지만, Radix Sort에서는 중요해지는 개념이다.

코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//2019-05-26
//Counting Sort알고리즘 프로그램
//구현에 문제는 없었으나, count를 위한 배열을 설정할 때 최대값인 N까지 넣기 위해서
//index를 N + 1로 만들고 프로그래밍하는 과정에서 ArrayOutOfBoundException을 조금 겪었다.
public class CountingSort {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write("정렬하고자 하는 수를 입력해주세요(0이상) : ");
        bw.flush();
        
        int index = 0, comp, biggestNumber = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int[] inputArray = new int[st.countTokens()];
        
        while (st.hasMoreTokens()) {
            comp = Integer.parseInt(st.nextToken());
            if (comp < 0) {
                bw.write("입력 범위를 넘었습니다.");
                bw.close();
                System.exit(1);
            }
            
            if (biggestNumber < comp)
                biggestNumber = comp;
            inputArray[index++] = comp;
        }
        
        bw.write("정렬된 결과값은 " + Arrays.toString(sorting(inputArray, biggestNumber)) + "입니다.");
        bw.close();
    }
    
    static int[] sorting(int[] inputArray, int N) {
        int[] resultArray = new int[inputArray.length];
        int[] countArray = new int[N + 1];
        
        for (int i : inputArray)
            countArray[i]++;
        for (int i = 1; i <= N; i++)
            countArray[i] += countArray[i - 1];
        for (int i = inputArray.length - 1; i >= 0; i--) {
            resultArray[countArray[inputArray[i]] - 1] = inputArray[i];
            countArray[inputArray[i]]--;
        }
        
        return resultArray;
    }
}