[알고리즘] 계수 정렬(Counting Sort)

---

계수 정렬 기본

• 특정한 조건(데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을 때)에서만 사용 가능한 알고리즘
  • 최솟값과 최댓값의 차이가 너무 크면 사용할 수 없음
• 최댓값의 크기를 갖는 배열을 선언해야함 → 메모리 낭비

---

정렬 과정

• 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴

---

시간 복잡도

• 데이터의 개수 : N, 데이터 중 최대값의 크기 : K
• $O(N+K)$

---

구현

// Counting Sort
		// 과정 1 
		for(int i = 0; i < array.length; i++) {
			// array 의 value 값을 index 로 하는 counting 배열 값 1 증가 
			counting[array[i]]++;			
		}
		
		// 과정 2 
		for(int i = 1; i < counting.length; i++) {
			// 누적 합 해주기 
			counting[i] += counting[i - 1];
		}
		
		// 과정 3
		for(int i = array.length - 1; i >= 0; i--) {
			/*
			 *  i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤 
			 *  counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
			 */
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;
		}

---