[알고리즘/계수정렬(Counting Sort)] - 자바

 

 

 

계수정렬에 대해 알아보자

지난 포스팅에서 대부분의 sort알고리즘을 살펴보았는데요. 그 중 빠르다고 할 수 있는 알고리즘은 O(NlogN)의 속도를 자랑하는 퀵정렬,병합정렬이 있죠. 하지만 특정한 경우에 이 알고리즘들 보다도 더 빠른 알고리즘이 존재합니다. 무려 O(N)의 속도를 보입니다. 바로 계수정렬(Counting Sort)인데요. 이름만 봐도 아시겠지만 맞습니다. 세는거에요!

 

[6,3,5,4,8,4,0,3,4,8,0,5,3,2,5,7,8,3,1,2,4]

이러한 데이터가 있다고 가정했을 때 가장 큰 값이 8 작은 값이 0입니다. 이 데이터를 정렬한다고 할게요.

0~8의 인덱스를 가지는 1차 배열을 선언해주고 

데이터를 돌아가면서 각 인덱스에 값을 1씩 ++해줍니다. 맞습니다 개수를 세는거에요. 그렇게 되면 순서대로 정렬이 되는 효과를 보입니다.

 

다음과 같이 정렬되고 개수만큼 인덱스를 출력하면 정렬이 된겨죠! 

코드로 볼까요

 

코드

public class 계수정렬 {
	public static void main(String[] args) {

		int[] data = { 6, 3, 5, 4, 8, 4, 0, 3, 4, 8, 0, 5, 3, 2, 5, 7, 8, 3, 1, 2, 4 };
		int[] arr = new int[data.length];

		for (int i = 0; i < data.length; i++) {
			arr[data[i]] += 1;
		}
		for (int i = 0; i < arr.length; i++) {
			while (arr[i] > 0) {
				System.out.print(i + " ");
				arr[i]--;
			}
		}
	}

}

다음과 같이 될 수 있겠네요.

 

끝!