[#11] Counting Sort : 계수 정렬, 카운팅 정렬

계수 정렬

 

- 오름차순 기준 

 

구현1 ( 배열이 주어졌을 때 )

1. 정렬하고자 하는 데이터 배열을 만든다.
2. count를 세야하는 배열을 만든다 ( count 배열은 정렬하려는 데이터의 최대 값이다 )
3. 정렬하려는 데이터의 값을 인덱스로 해서 count 배열의 카운트를 센다.
4. count의 이전 항의 값과 자신의 값을 더하면서 누적합을 계산한다.
5. 해당 누적합을 토대로 원본 데이터 배열을 스왑해가며 정렬한다.

 

구현2 (Counting 배열만 사용하기)

1. 예상하는 최대값을 인덱스로 하는 카운팅 배열을 생성한다. (*데이터는 0으로 초기화)
2. 입력받는 값들을 해당 카운팅배열의 인덱스로 해서 카운트를 센다.
3. 2번과 동시에 입력되는 값들을 max 값으로 누적시켜서 최대값을 보관한다.
4. 최대값 만큼의 i = 0 루프문을 생성한 후  카운팅 배열에서 0이 아닌 값을 조건식으로 찾아낸다
5. 0이 아닌 카운팅 배열의 value를 기준으로 루프문을 돌리면서 상위 루프문의 i를 출력한다.
   (여기서 i는 실제 정렬하고자 하는 데이터들의 value이다.)

 

---

 

전체 코드

구현1 코드

#include <iostream>

void Swap(int* DataA, int* DataB)
{
	int temp = (*DataA);
	(*DataA) = (*DataB);
	(*DataB) = temp;
}

void Print_Arr(int DataSet[], const int LEN)
{
	for (int i = 0; i < LEN; i++)
		std::cout << DataSet[i] << '\n';
}

int Find_Max(int DataSet[], const int LEN)
{
	int max = 0;
	for (int i = 0; i < LEN; i++)
	{
		if (DataSet[i] > max)
			max = DataSet[i];
	}
	return max;
}

void CountingSort(int DataSet[], const int LEN);

int main(void)
{
	using namespace std;
	int* dataSet = nullptr;
	int  length  = 0;
	
	cin >> length;
	dataSet = new int[length];
	for (int i = 0; i < length; i++)
		cin >> dataSet[i];

	CountingSort(dataSet, length);
	Print_Arr(dataSet, length);

	delete[]dataSet;
	return 0;
}

void CountingSort(int DataSet[], const int LEN)
{
	int* countArr = nullptr;
	int  i = 0, goIndex = 0, maxValue = 0;

	maxValue = Find_Max(DataSet, LEN);
	countArr = new int[maxValue + 1]{0}; // 0으로 초기화
	for (i = 0; i < LEN; i++)
		++countArr[DataSet[i]];

	for (i = 1; i <= maxValue; i++)
		countArr[i] = countArr[i] + countArr[i - 1];

	for (i = 0; i < LEN; i++)
	{
		goIndex = (countArr[DataSet[i]] - 1);
		Swap(&DataSet[goIndex], &DataSet[i]);
		countArr[DataSet[i]];
	}

	delete[]countArr;
}

 

 

 

구현2 코드

#include <iostream>

int main(void)
{
	using namespace std;
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int  countArr[10001]{ 0 };
	int  length = 0, cTemp = 0, maxValue = 0;
	int  i = 0;

	cin >> length;
	for (i = 0; i < length; i++)
	{
		cin >> cTemp;
		++countArr[cTemp];
		if (cTemp > maxValue)
			maxValue = cTemp;
	}

	for (i = 0; i <= maxValue; i++)
	{
		if (countArr[i])
		{
			for (int j = 0; j < countArr[i]; j++)
				std::cout << i << '\n';
		}
	}

	return 0;
}

 

 

---