2-(3) Sorting in Linear time-Counting Sort

이 챕터에서는 n time안에 끝낼 수 있는 sorting들을 배우는데, 대표적으로 Counting sort를 다뤄보고자 한다.

(*책에는 Bucket sort랑 Radix sort도 있음)

우선, 원소들의 대소를 부등호로 비교해가며 정렬하는 비교정렬 방법들은 n time안에 끝낼 수 없다는 것이 알려져있다. 이론적 증명을 보고싶다면 책을 참고하면 된다. 나는 안궁이어서 안 봤다. 그럼 n time안에 끝낼 수 있는 정렬이 있을까?

 

수의 range가 n에 const하게 비례할 때 n time안에 끝낼 수 있는 정렬로서 Storing Sort가 알려져있는데 다음과 같은 아이디어를 생각해보자.

만약 우리가 정렬하고자 하는 배열에서 어떤 수가 몇 번 나오는지 세어 놓은 자료가 있다면, 그 자료만 가지고도 원래 배열을 정렬한 새로운 배열을 만들 수 있지 않을까? 예를 들어 arr[1:5]={1,3,3,5,2}인 배열을 생각해보자. (편의상 index는 1부터) 그리고 우리는 이 수의 range가 1~5라는 것을 알고 있는 상황이라고 하자.(몰라도 배열의 최대/최소를 찾는 것은 n time안에 가능하니까 n-time solution을 만드는데 문제되지 않는다.)

 

그럼 range가 5니까 그것에 대응하는 배열 range[1:5]를 만든다. 이제 arr를 훑으면서 k를 보면 range[k]를 1키운다.

그러면 range[]={1,1,2,0,1}이 될 것이다. 그러면 range배열을 통해 어떤 수가 마지막으로 나오는 위치를 알 수 있는데

"k가 나오는 마지막 위치 = k가 나온 횟수 + 1~k-1까지의 수가 나온 총 횟수"가 되므로 range[i]+=range[i-1]을 i는 2부터 5까지 해서 그 수들을 배열에 저장하면 된다. 그러면 range는 다음과 같이 바뀐다.

range[]={1,2,4,4,5}

 

그러면 이제 정렬된 수를 저장할 새로운 배열 new_arr[5]를 만들고 기존 arr를 보자.

arr[1]을 보니 그 수가 1이다. 그러면 range[1]을 보자. 1의 마지막 나오는 곳은 1이라고 한다. 따라서 new_arr[1]=1, 그리고 이제 1을 하나 썼으니 1이 남았다면 그 1은 new_arr[1]앞에 와야할 것이다. 따라서 range[1]에 있는 수를 하나 줄인다.

따라서 range[]={0,2,4,4,5}, new_arr={1,x,x,x,x}

 

arr[2]를 보니 그 수가 3이다. 그러면 range[3]를 보자. 3의 마지막 나오는 곳은 4라고 한다. 따라서 new_arr[4]=3, 그리고 이제 3을 하나 썼으니 3이 남았다면 그 3는 new_arr[4]앞에 와야할 것이다. 따라서 range[3]에 있는 수를 하나 줄인다.

따라서 range[]={0,2,3,4,5}, new_arr={1,x,x,3,x}

 

arr[3]을 보니 그 수가 3이다. 그러면 range[3]를 보자. 3의 마지막 나오는 곳은 3이라고 한다. 따라서 new_arr[3]=3, 그리고 이제 3을 하나 썼으니 3이 남았다면 그 3은 new_arr[3]앞에 와야할 것이다. 따라서 range[3]에 있는 수를 하나 줄인다.

따라서 range[]={0,2,2,4,5}, new_arr={1,x,3,3,x}

 

arr[4]를 보니 그 수가 5이다. 그러면 range[5]를 보자. 5의 마지막 나오는 곳은 5라고 한다. 따라서 new_arr[5]=5, 그리고 이제5를 하나 썼으니 5가 남았다면 그 5는 new_arr[5]앞에 와야할 것이다. 따라서 range[5]에 있는 수를 하나 줄인다.

따라서 range[]={0,2,2,4,4}, new_arr={1,x,3,3,5}

 

arr[5]를 보니 그 수가 2이다. 그러면 range[2]를 보자. 2의 마지막 나오는 곳은 2라고 한다. 따라서 new_arr[2]=2, 그리고 이제2를 하나 썼으니 2가 남았다면 그 2는 new_arr[2]앞에 와야할 것이다. 따라서 range[2]에 있는 수를 하나 줄인다.

따라서 range[]={0,1,2,4,4}, new_arr={1,2,3,3,5}

 

ok? 다음은 그 코드를 구현한 것이다. 실제 배열은 0부터 인덱스가 시작하니까 오프셋을 잘 생각해봐야한다. range를 모른다고 생각하고 range를 찾아내는 것까지 코드로 넣었다.( input은 unsigned int로 가정한다.)

#include<iostream>
#include<time.h>
#define INFINITE 1000000000
using namespace std;


bool Issort(int* arr, int size) {
	for (int i = 0; i < size - 1; i++) {
		if (arr[i] > arr[i + 1]) return false;
	}
	return true;
}
void CountingSort(int* arr, int size) {
	int* sorted = new int[size];
	//(i)range를 알아야 가능.
	int range=-INFINITE;
	for (int i = 0; i < size; i++) if (arr[i] > range) range = arr[i];
	int* counted = new int[range+1]; //counted[range]까지 접근하려면 range+1크기여야
	for (int i = 0; i <= range; i++) { //배열 초기화
		counted[i] = 0;
	}
	for (int i = 0; i < size; i++) { //그 수가 몇번 나오나 세기
		++counted[arr[i]];
	}
	for (int i = 1; i <= range; i++) { 
		counted[i] += counted[i - 1];
	}
	for (int i = size - 1; i >= 0; i--) { //거꾸로 해야함. 마지막부터 세야 맞음
		sorted[counted[arr[i]]-1]=arr[i];
		--counted[arr[i]];
	}
	for (int i = 0; i < size; i++) { //원래 배열에 element wise로 정렬된 배열의 원소를 복사
		arr[i] = sorted[i];
	}
    //메모리 정리
	delete[] counted;
	delete[] sorted;
}

int main() {
	int arrsize;
	int range;
	cout << "Enter size of array: ";
	cin >> arrsize;
	cout << "Enter size of range: ";
	cin >> range;
	int* arr = new int[arrsize];
	double m_ratio = 0;	//Change the ratio of negative numbersL its 0 to this case
	srand((unsigned int)time(NULL));
	for (int i = 0; i < arrsize; i++)
	{
		arr[i] = rand() % range - int(m_ratio * range);
	}
	cout << "origin array"<<endl;
	for(int i=0;i<arrsize;i++)
		cout << "arr[" << i << "]: " << arr[i] << endl;
	cout << "afted sorting and its result: ";
	CountingSort(arr, arrsize);
	cout << ((Issort(arr, arrsize)) ? "success" : "false") << endl;
	if ((Issort(arr, arrsize))) { 
		for (int i = 0; i < arrsize; i++)
			cout << "arr[" << i << "]: " << arr[i] << endl;
	}
}

수행시간 분석해보면 n짜리 루프 여러개랑 k(range)짜리 루프 한 개가 있으니까 대충 O(cn+k)라고 이 알고리즘의 수행시간을 분석해볼 수 있다. 그래서 k가 n에 const하게 비례하면 O(n)으로 퉁칠 수 있다.