Counting sort(계수 정렬) - O(n)

Counting sort는 배열에 담긴 숫자가 몇 번씩 들어가 있는지 counting하여 정렬해주는 방식입니다!

예를 들어서 1부터 9까지의 정수만 들어갈 수 있는

int[] unsorted = {9, 2, 1, 3, 9, 7} 이라는 배열이 있다고 가정하면

index가 0부터 9까지의 빈 배열을 하나 만들어 줍니다. 

 

int[] countArr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

 

countArr의 인덱스가 1부터 9까지의 정수 역할을 해주게 됩니다. 

index 0 에는 숫자 0의 갯수가 들어가고, index 1에는 숫자 1의 갯수가 들어가고, index 2에는 숫자 2의 갯수가 들어가고,,,index 9에는 숫자 9의 갯수가 들어가게 되는 것입니다. (여기서는 1~9만 들어가므로 index 0은 항상 0이겠죠?)

 

이 예시에서는 int[] countArr = {0, 1, 1, 1, 0, 0, 0, 1, 0, 2} 이렇게 표시가 될 것입니다. 

그런다음 countArr의 index를 각 요소가 0이 될때까지 반복해서 출력해주면 숫자가 정렬된 형태로 나오게 됩니다!

 

버블 정렬처럼 배열을 여러번 돌지 않아도 되어서 시간 복잡도는 O(n)으로 빠른 편입니다. 

 

- 사용: 배열에 들어가는 숫자의 범위가 정해져 있을 때

- 시간복잡도: O(n)

 

- 구현 코드:

 

 
    public static void countingSort(int[] arr) {
 
        //arr의 원소로 들어갈 수 있는 수의 범위가 1부터 9까지라고 가정
        //범위에 따라 사이즈를 다르게 하면 됨
        int[] countArr = new int[10]; //index는 0부터기 때문에 사이즈를 10으로 설정
        
        //countArr을 이용해 정수가 몇개 들어왔는지 확인하기
        for(int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        
        //counntArr의 인덱스를 배열에 들어있던 정수로서 활용해 하나씩 프린트해주기
        for(int j = 0; j < countArr.length; j++) {
            while (countArr[j] > 0) {
                System.out.print(j + "\t");
                countArr[j]--;
            }
        }
    }
 

위의 예제처럼 1부터 9까지의 숫자가 들어가는 경우에는 위의 코드와 같이 작성할 수 있습니다.

만약에 0부터 100까지의 숫자가 들어가는 경우라면 아래처럼 할 수 있겠죠.

 

 
   public static void countingSort(int[] arr) {
 
        //arr의 원소로 들어갈 수 있는 수의 범위가 0부터 100까지라고 가정
        //범위에 따라 사이즈를 다르게 하면 됨
        int[] countArr = new int[101];
 
        //countArr을 이용해 정수가 몇개 들어왔는지 확인하기
        for(int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
 
        //counntArr의 인덱스를 배열에 들어있던 정수로서 활용해 하나씩 프린트해주기
        for(int j = 0; j < countArr.length; j++) {
            while (countArr[j] > 0) {
                System.out.print(j + "\t");
                countArr[j]--;
            }
        }
    }
 

수의 범위만 주어진다면 빠르게 정렬할 수 있는 counting sort입니다!

 

# Counting sort를 사용해서 풀어 본 leet code와 백준 문제가 몇가지 있는데 필요하신 분들을 위해서 문제와 저의 풀이를 공유합니다.

 

1. 문제: 

912. Sort an Array

풀이:

https://github.com/happyduck-git/LeetCode/blob/master/SortAnArray.java

GitHub - happyduck-git/LeetCode

 

2. 문제:

1051. Height Checker

풀이:

https://github.com/happyduck-git/LeetCode/blob/master/HeightChecker.java

GitHub - happyduck-git/LeetCode