카운팅 정렬 이해하기 - Java(자바)

카운팅 정렬(Counting Sort)이란?

카운팅 정렬은 시간 복잡도 O(n)으로 성능이 아주 좋은 정렬 알고리즘이다.

빠른 정렬로는 대표적으로 퀵 정렬, 힙 정렬, 병합 정렬이 있는데 이들은 모두 평균 시간복잡도가 O(nlogn)인것을 보면 카운팅 정렬은 성능이 가장 좋다고 볼 수 있다.

 

우선 카운팅 정렬의 과정을 먼저 살펴보겠다.

 

아래와 같은 원본 배열 arr을 정렬해보려 한다.

1. counting 배열 생성

우선 arr의 값을 인덱스로 하는 counting배열의 값을 1 증가시킨다.

arr[0] = 4 →  counting[4] ++

arr[1] = 5 →  counting[5] ++

...

arr[8] = 1 →  counting[1] ++

counting 배열은 arr의 값들의 개수를 알 수 있는 배열이다.

counting[0] →  arr배열에서 0인 값 개수: 0개

counting[1] →  arr배열에서 1인 값 개수 : 2개

따라서 counting 배열의 마지막 인덱스는 arr 배열의 최댓값과 같다.

 

2. counting 배열 누적합 계산

이제 이 counting 배열의 누적합을 계산해준다.

counting[0]+counting[1] 값을 counting[1]에 삽입

counting[1]+counting[2] 값을 counting[2]에 삽입

이런식으로 누적합을 계산해주면

최종 counting 배열은 다음과 같다.

counting값 -1 은 해당 arr의 값의 위치를 의미한다.

 

3. result 배열에 정렬된 arr 값 삽입

이제 마지막으로 arr 값들을 정렬해야 한다.

arr의 마지막 값부터 시작한다.

arr의 값을 인덱스로 하는 counting의 값을 -1 해주고 그 값을 인덱스로 하는 result에 arr의 값을 삽입한다.

글로 이해하기 헷갈리기 때문에 순서대로 그림으로 알아보겠다.

 

 

 

 

 

 

이런식으로 반복하여 정렬해주게 되면

 

 

최종적으로 정렬이 된 result 배열을 볼 수 있다.

 

카운팅 정렬은 시간 복잡도가 O(n)이라는 좋은 성능을 가지고 있지만 큰 단점이 있기때문에 자주 사용하지는 않는 정렬 알고리즘이다.

위에서 살펴봤듯이 counting 배열의 크기는 arr의 max값에 의해 결정된다.

그렇기 때문에 만약 arr 배열의 크기는 작은데 max의 값이 너무 크게 되면 치명적인 메모리 낭비가 된다.

arr의 값의 폭이 크지 않은 경우에 사용하면 좋을 정렬 알고리즘인듯 하다.

 

 

카운팅 정렬 구현

크기 N의 배열 arr 정렬하기(arr의 최대값을 max라고 가정)

1. counting 배열 생성

 

2. result 배열에 arr값 삽입하여 정렬하기