정렬: counting sort

정렬될 결과에서 배치될 순서를 기준으로 정렬하는 방법으로

해당 항목값이 몇 개씩 있는지 세는 방법으로 정렬하는 방식을  counting sort라고 합니다.

counting table만 구해서 그 counting 값을 기준으로 원소 값들을 재 배치하면 단순 하겠지만

다음 radix sort에서도 동일 원리를 사용하여 구현하는 것이 용이하기 때문에

누적 counting 값을 기준으로 원소들을 재 배치 합니다.

C/C++로 구현하면 아래와 같습니다.

void counting_sort(int *data, int len)
{
	int table_max = max(data, len) + 1;
	int *counting_table = new int[table_max];
	int *sorted_data = new int[len];

	for (int i = 0; i < table_max; i++) { // counting table 초기화
		counting_table[i] = 0;
	}

	for (int i = 0; i < len; i++) { // 해당 원소 bucket의 count 증가
		counting_table[data[i]]++;
	}

	for (int i = 1; i < table_max; i++) { // 각 bucket의 counting 누적값 계산
		counting_table[i] += counting_table[i - 1];
	}

	for (int i = len-1; i >= 0; i--) { // 해당 원소의 counting 누적값을 거꾸로 빼면서
		int index = counting_table[data[i]] - 1; // 누적 counting 값을 정렬된 배열의
		sorted_data[index] = data[i]; // index로 사용
		counting_table[data[i]]--; // 동일 bucket의 다음 원소는 앞으로 배치하기 위해
	}

	printf("Data Size %d\n", len);
	for (int i = 0; i < len; i++) {
		printf("%d ", sorted_data[i]);
	}
	printf("\n");

	delete[] sorted_data;
	delete[] counting_table;
}