230608 8주 3일차 TIL. Counting Sort

Counting Sort

Counting Sort란

각 자료가 몇 개 존재하는 지를 정리한 뒤 그 정보를 활용해 정렬하는 방식이다. 

예를 들어 숫자가 적힌 카드가 1이 2개, 2가 3개, 3이 1개 있다고 하면 1, 1, 2, 2, 2, 3 와 같이 정렬하는 방식이다.

 

 

1. 먼저 자료들 값의 범위만큼 공간을 가진 배열을 만든다.

만약 자료들 값이 0~5까지 있다면 크기가 6인 배열(counts)을 만든다.

int[] arr = {0, 1, 4, 4, 3, 0, 5, 2, 5, 1};

//(최대값과 최소값을 안다는 가정 하에)
int max = 5;
int min = 0;
int[] counts = new int[max - min + 1];

 

 

2. arr 배열을 돌면서 각 자료의 데이터(data)를 확인하고, counts[data]의 값을 증가시킨다.

이 과정이 끝나면 counts[data]에는 data가 몇 개인지가 저장된다.

for (int data : arr) {
	counts[data]++;
}

 

 

3. counts의 첫 번째 원소부터 시작해 앞쪽 원소의 값을 뒤에 합하며 누적합을 구한다.

이 과정이 끝나면 상대적 위치가 아닌 절대적 위치가 나온다. counts[arr[i]]가 arr[i]의 절대 위치값이 되는 것이다.

ex) counts[0] = 2일 때, output[0], output[1]은 0이 되고.

counts[1] = 2이므로 그 다음 두 개(output[2], output[3])는 1이 된다.

 

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

 

 

4. 이후 본래의 자료(arr) 데이터를 순회하여, counts 배열에 따라 결과를 정리한다.

int[] output = new int[arr.length]; // 결과 저장용 배열
for (int i = arr.length - 1; i >= 0; i++) { // 뒤에서부터 순회
	counts[arr[i]]--;
	int position = counts[arr[i]];
	output[position] = arr[i];
}

 

 

 

시간복잡도

⇒ Counting Sort는 자료의 총량보다 자료의 범위가 너무 크지 않을 때 효율적이다!