[JAVA] 계수 정렬(Counting Sort) 개념 및 알고리즘을 이용한 코딩

계수 정렬 개념

계수 정렬(Counting Sort)이란?

• 데이터 값을 직접 비교하지 않고, 단순하게 개수를 세어 기록하고 정렬하는 방식이다.
• 값 비교가 일어나지 않기 때문에 속도가 매우 빠르다.
• 하지만 개수를 저장하는 배열, 정렬할 배열을 위한 추가 공간이 필요하다.
• 또한 숫자가 매우 큰 경우에는 속도가 현저히 느려질 수 있다.

매일프로그래밍 문제 기준

1. 문제
   원소가 0, 1, 2로 구성된 배열이 주어졌을 때, 상수 공간을 이용해 선형 시간에 배열을 정렬하시오.

문제의 핵심은 주어진 배열만을 이용하는것 입니다. 주어진 배열로 Output을 처리하려면 병합정렬을 사용하면 됩니다.

Input: [0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

2. 풀이
   이 문제는 계수 정렬(count sort)을 생각해 볼 수 있습니다. 배열에서 0, 1, 2의 개수를 센 후 0부터 해당 개수만큼 배열에 넣어 줍니다. 이 방법은 O(n)의 시간 복잡도를 가지지만 배열을 두 번 순회해야 합니다.

배열을 한 번만 순회하여 정렬하는 방법으로 값들을 세개의 그룹으로 분리하는 대안적인 선형 시간 분할법(linear-time partition routine)을 적용할 수 있습니다.

만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다.

중심값(pivot)보다 작은 값들 -> 작은 값 0
중심값과 같은 값들 -> 중심값 1
중심값보다 큰 값들 -> 큰 값 2

이 문제를 풀기 위해서는 중심값을 1로 설정하여 위 방법을 적용합니다.

import java.util.Arrays;

class ThreeWayPartition
{
    // 0, 1, 2로 구성된 배열을 정렬하기 위한 선형 시간 분할법
    public static void threeWayPartition(int[] A, int end)
    {
        int start = 0, mid = 0;
        int pivot = 1;

        //end 값을 만날떄가지 루프를 돕니다.
        while (mid <= end)
        {
            if (A[mid] < pivot) { // 현재 원소가 0인 경우
                swap(A, start, mid);
                ++start;
                ++mid;
            }
            else if (A[mid] > pivot) { // 현재 원소가 2인 경우
                swap(A, mid, end);
                --end;
            } else // 현재 원소가 1인 경우                        
                ++mid;
        }
    }

    // A 배열의 두 원소 A[i]와 A[j]의 자리를 바꾸는 메소드
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    // 메인 함수
    public static void main (String[] args)
    {
        int A[] = { 0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0 };

        threeWayPartition(A, A.length - 1);
        System.out.println(Arrays.toString(A));
    }
} 

결과