[알고리즘 | 정렬] 카운팅 정렬 (Counting Sort) 정리

서론

카운팅 정렬(Counting Sort)은 정수 기반의 데이터를 정렬하기 위해 설계된 효율적인 정렬 알고리즘이다.

이 알고리즘은 각 원소의 등장 횟수를 계산하여 정렬을 수행하며, 특정 조건에서 매우 빠르게 동작할 수 있다.

이 글에서 카운팅 정렬의 개념과 동작 방식, 장점 및 단점을 정리하고자 한다.

카운팅 정렬이란

카운팅 정렬은 입력 데이터의 범위가 상대적으로 좁을 때 효과적인 정렬 알고리즘이다. 이 알고리즘은 각 원소가 등장하는 횟수를 기록하고, 이 빈도 정보를 바탕으로 정렬된 결과를 빠르게 생성한다. 카운팅 정렬의 주요 아이디어는 데이터를 직접 정렬하는 대신, 각 값의 출현 빈도를 계산하여 원래 배열의 정렬을 수행하는 것이다.

카운팅 정렬 동작 과정

카운팅 정렬은 다음과 같은 단계로 이루어진다.

• 최댓값 찾기:
  • 배열에서 가장 큰 값을 찾는다. 이 값은 카운트 배열의 크기를 결정하는 데 필요하다.
  • 예를 들어, 배열의 원소가 0부터 10까지의 값이면, 카운트 배열은 11개의 요소를 가진다.
• 카운트 배열 생성 및 초기화:
  • 최댓값 + 1 크기의 카운트 배열을 생성하고, 모든 값을 0으로 초기화한다.
  • 이 배열은 각 원소가 얼마나 자주 등장하는지를 기록한다.
• 빈도 계산:
  • 원래 배열을 순회하면서 각 원소의 빈도를 카운트 배열에 기록한다.
  • 예를 들어, 배열 [1, 5, 5, 2]가 있다면, 카운트 배열은 [0, 1, 1, 0, 0, 2]로 업데이트된다.
• 누적 카운트 배열 생성:
  • 카운트 배열을 누적 카운트 배열로 변환하여 각 원소의 위치를 결정한다.
  • 누적 카운트 배열의 각 인덱스는 해당 값이 정렬된 배열에서의 최종 위치를 나타냅니다.
• 정렬된 배열 생성:
  • 원래 배열을 역순으로 순회하면서 카운트 배열을 참조하여 정렬된 배열을 생성한다.
  • 이렇게 하면 같은 값을 가지는 원소들이 원래 배열에서의 순서를 유지하며 정렬된다.

 

카운팅 정렬 예시 :

 

1. 최대 값 찾기

• 정렬하고자 하는 배열의 최대값을 찾는다.
• A 배열의 최대값은 10이다.

 

2. 카운팅 배열 생성

• 배열의 각 원소의 등장 횟수를 기록하기 위해 카운팅 배열을 생성한다.
• 카운팅 배열의 크기는 A 배열의 최대값인 (10 + 1)로 선언한다.
  • 따라서 카운팅 배열의 크기는 11이 된다. (0부터 10까지)
• 0으로 초기화 되지만 가독성을 위해 제외하였다.

 

3. 원소의 빈도 수 저장

• 배열 A를 순회하면서 각 원소의 빈도 수를 카운팅 배열에 저장한다.
  • 원소 1: B[1]를 1로 증가
  • 원소 6: B[6]를 1로 증가
  • 원소 5: B[5]를 1로 증가 (다시 등장하므로 2로 증가)
  • 원소 4: B[4]를 1로 증가
  • 원소 10: B[10]를 1로 증가
  • 원소 8: B[8]를 1로 증가

업데이트 된 카운팅 배열 $B=[0,1,0,0,1,2,1,0,1,0,1]$

 

4. 누적 합 계산

• B 배열을 순회하면서 현재 원소값에 이전 원소의 값을 더하여준다.
•  누적 합을 계산하여 각 숫자가 정렬된 배열에서 시작해야 할 인덱스를 결정한다.
  
  • 숫자 1은 인덱스 1 ~ 3에 위치한다.
  • 숫자 2는 인덱스 4에 위치한다.
  • 숫자 4는 인덱스 5에 위치한다.
  • 숫자 5는 인덱스 6 ~ 7에 위치한다.
  • 숫자 6은 인덱스 8 ~ 9에 위치한다.
  • 숫자 10은 인덱스 10에 위치한다.

5. 정렬

순서 빨 -> 주 -> 노 -> 초 -> ...

처리 과정:

먼저 정렬된 배열을 저장할 배열 C를 선언해야한다. $C.length == A.length$

 

• 첫 번째 요소:
  • 숫자 가져오기: A 배열의 마지막 원소인 $8$을 가져온다
  • 위치 찾기: B[8] 값은 6이다. 이 값은 숫자 $8$이 C 배열에서 위치할 자리이다.
  • 배치하기: C 배열의 인덱스 6−1=5 위치에 숫자 8을 배치합니다.
  • 위치 값 감소: 이제 B[8] 값을 1 감소시켜 다음에 숫자 8이 나오면 올바른 위치에 배치되도록 한다.

 

• 다음 요소 :
  • 숫자 가져오기 : A 배열의 두 번째 마지막 원소인 $10$을 가져온다.
  • 위치 찾기 : B[10] 값은 7이다. 이 값은 숫자 $10$이 C 배열에서 위치할 자리이다.
  • 배치하기 : C 배열의 인덱스 7-1=6 위치에 숫자 $10$을 배치한다.
  • 위치 값 감소: 이제 B[10] 값을 1 감소시켜 다음에 숫자 $10$이 나오면 올바른 위치에 배치되도록 한다.

 

• 다음 요소:
  • 숫자 가져오기: A배열의 세 번째 마지막 원소인 4를 가져온다.
  • 위치 찾기: B[4]의 값은 2이다.
  • 배치하기: C 배열의 인덱스 2−1=1 위치에 숫자 4를 배치한다.
  • 위치 값 감소: B[4] 값을 1 감소시킨다.

 

   ... 생략

 

• 마지막 요소:
  • 숫자 가져오기: A배열의 첫 번째 요소인 1을를 가져온다.
  • 위치 찾기: B[1]의 값은 1이다.
  • 배치하기: C 배열의 인덱스 1−1=0 위치에 숫자 1를 배치한다.
  • 위치 값 감소: B[1] 값을 1 감소시킨다.

위와 같은 동작을 반복하여 배열을 정리한다.

카운팅 정렬 구현

public static int[] countingSort(int[] arr) {

	int maxValue = Integer.MIN_VALUE;
        
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] > maxValue) {
			maxValue = arr[i];
		}
	}
	int[] countArr = new int[maxValue + 1];
	for (int i = 0; i < arr.length; i++) {
		countArr[arr[i]]++;
		}

		for (int i = 1; i < countArr.length; i++) {
			countArr[i] += countArr[i - 1];
		}

	int[] sortedArr = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		int num = arr[arr.length - i - 1];
		sortedArr[countArr[num] - 1] = num;
		countArr[num]--;
		}
	return sortedArr;
    }
}

카운팅 정렬(Counting Sort)의 장단점

장점

1. 선형 시간 복잡도:
   • 카운팅 정렬은 데이터의 범위가 작을 때 $O(n+k)$의 시간 복잡도를 가진다.
   • 여기서 $n$은 입력 데이터의 크기, $k$는 입력 데이터 중 최대 값이다.
   • 따라서 특정 조건에서는 매우 효율적인 알고리즘이다.
2. 간단한 구현:
   • 카운팅 정렬은 비교 기반 정렬 알고리즘이 아니므로 구현이 간단한다.
   • 각 숫자의 등장 횟수를 카운팅하고 그 정보를 사용해 배열을 정렬한다.
3. 안정 정렬:
   • 카운팅 정렬은 안정 정렬이다.
   • 동일한 값을 가진 요소들의 순서가 정렬 전후에도 유지된다. 이는 중복된 요소가 있는 데이터에서 유리하다.

 

단점

1. 제한된 데이터 유형:
   • 카운팅 정렬은 정수 또는 정수로 표현할 수 있는 데이터에만 적합하다.
   • 실수나 복잡한 데이터 유형에는 적용하기 어렵다.
2. 큰 범위의 데이터에 비효율적:
   • 데이터의 최대 값 $k$ 가 크다면, 카운팅 배열의 크기 또한 커지게 되어 메모리 사용량이 비효율적일 수 있다.
   • 예를 들어, 범위가 0부터 1,000,000인 데이터를 정렬하려면 매우 큰 카운팅 배열이 필요하다.
3. 메모리 낭비:
   • 데이터의 최대 값과 최소 값 사이에 많은 빈 값이 있는 경우 메모리를 비효율적으로 사용하게 된다.
4.  정렬 범위의 제약:
   • 카운팅 정렬은 데이터의 범위가 제한적일 때만 효과적이다.
   • 범위가 넓어지면, 시간 및 공간 효율성 측면에서 다른 정렬 알고리즘에 비해 비효율적일 수 있다.

시간 복잡도 분석

1. 최대값 찾기

• 배열에 최대값을 찾는 과정은 입력 배열을 한 번 순회하면서 이루어지므로 시간 복잡도는 $O(n)$이다.

2. 카운트 배열 생성 및 초기화

• 최댓값 $k$ 를 이용하여 크기가 $k+1$인 카운트 배열을 생성하고 초기화하는 과정은 $O(k)$의 시간 복잡도를 가진다.

3. 빈도 계산

• 입력 배열을 다시 순회하며 각 원소의 빈도를 카운트 배열에 저장하는 과정으로, 시간 복잡도는 $O(n)$이다.

4. 누적 합 계산

• 카운트 배열을 누적 합 배열로 변환하는 과정으로, 시간 복잡도는 $O(k)$ 이다.

5. 정렬된 배열 생성

• 입력 배열을 역순으로 순회하면서 각 원소를 정렬된 배열에 배치하는 과정으로, 시간 복잡도는 $O(n)$이다.

 

총 시간 복잡도

각 단계를 종합하면 카운팅 정렬의 전체 시간 복잡도는 다음과 같다.

$O(n)+O(k)+O(n)+O(k)+O(n)=O(n+k)$

• $n$은 입력 배열의 크기,
• $k$는 입력 배열의 최대 값이다.

따라서, 카운팅 정렬의 시간 복잡도는 $O(n+k)$ 이다.

결론

카운팅 정렬은 특정한 상황에서 매우 빠르게 동작할 수 있는 알고리즘이다. 정렬을 매우 빠르게 수행할 수 있지만, 데이터의 특성과 범위를 고려하여 사용해야 한다. 데이터가 정수로 이루어져 있고, 데이터의 최대값이 데이터의 크기 $n$에 비해 크지 않으며 메모리가 충분히 여유가 있는 경우 카운팅 정렬을 사용하면 빠르게 정렬을 할 수 있다.

 

이러한 조건을 만족할 때 카운팅 정렬은 효율적인 정렬 알고리즘으로, 특히 대량의 정수 데이터나 범위가 제한된 데이터를 다룰 때 매우 유용하다. 따라서, 카운팅 정렬을 적용할 때는 데이터의 범위와 메모리 사용량을 신중히 고려하여 적절히 활용하는 것이 중요할거 같다.

 

관련 문제