계수(Counting) 정렬(C/C++ 구현, 시간 복잡도)

1. 계수 정렬

 배열에 있는 숫자를 세어 정렬하는 방법 O(n)의 시간복잡도로 정렬가능하나,

배열에 포함된 숫자 중 큰 수가 존재하면, 메모리 낭비가 크다

 In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.[1][2][3]

출처 : https://en.wikipedia.org/wiki/Counting_sort

Counting sort - Wikipedia

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

1. 배열의 숫자가 몇개 인지 count한다

2. 세어준 배열을 다시 minnumber~maxnumber까지 순차적으로 더해준다.

3. 본 배열 끝에서 부터 정해진 위치(2번 배열에 저장한 숫자)에 넣을 수 있도록 한다.

 

메모리 낭비가 큰 이유

1. 임시 배열을 1. count 하는 배열 2. count 합을 저장하는 배열 3. 정렬된 배열 많이 선언해야함으로

메모리 낭비가 큰거를 알 수 있다.

2. maxnumber가 크다면 큰 만큼 숫자를 잡아야한다.

 

시간 복잡도

1. n까지 counting 하는데 n

2. 숫자 더해주는데 n

3. 다시 정렬하는데 n

O(n)

 

애니메이션 

http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

소스 코드

소스코드 실행시 제일 끝 부터 순차적으로 자기 위치에 들어가는 것을 볼 수 있다.

자세한 설명은 주석 참조

#include <iostream>

using namespace std;
int arr[1000] = { 10,23,1,1,23,23,4,5,6,7 };
int a[1000];
void counting_sort(int list[])
{
	int temp[1000];
	int count[1000];
	memset(temp, 0, sizeof(temp));
	//더해주기
	for (int i = 0; i < 10; i++)
		temp[list[i]]++;
	count[0] = temp[0];
	//누적으로 더해주기
	for (int i = 1; i <= 23; i++)
		count[i] = count[i - 1] + temp[i];
	//더해졌는지 확인
	for (int i = 0; i <= 23; i++)
		cout << count[i] << " ";
	cout << endl;
	//제일 끝에서 부터 삽입
	for (int i = 9; i >= 0; i--)
	{
		a[  count[ list[i] ]-1 ] = list[i];
		count[list[i]]--;
		//들어가는 위치 보기
		for (int j = 0; j < 10; j++)
			cout << a[j] << " ";
		cout << endl;
	}
	//정렬된 행렬
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main()
{
	counting_sort(arr);
}