[알고리즘] 계수정렬

계수 정렬

계수 정렬은 비교연산을 사용하지 않고 정렬하는 알고리즘이다
배열 내의 특정한 값이 몇번 나왔는지에 따라 정렬이 수행되기 때문에 비교 연산이 사용되지 않는다
count배열(0~4)에 저장할 원소들의 실제값은 1~5
정렬하고 싶은 원소 내에서 가장 최대값을 기준으로 새로운 배열 생성
해당 원소들의 갯수를 세어서 배열에 순서대로 저장

count배열에 갯수 넣기

• 계수 정렬은 해당 원소들의 갯수를 세어서 count배열에 저장해둔 뒤 출력하는 것이다
• 아래의 코드에서 SIZE 5 크기의 배열을 정하고 원소를 넣어주었다
• 가장 큰 원소의 값 3으로 새로운 count배열을 생성한다
• count배열에 원소의 갯수를 넣을때, 넣을 인덱스 자리와 실제 값이 -1 차이가 나기 때문에
  count[list[i] - 1]++;
  

#include <iostream>
using namespace std;
#define SIZE 5
int main()
{
	int list[SIZE] = { 1,2,3,3,2 };

	int count[3] = { 0, };

	// 배열을 순회하면서 count배열에 원소 갯수 넣기
	for (int i = 0; i < SIZE; i++)
	{
		count[list[i] - 1]++;
	}
	
   // count배열의 크기만큼 반복하여 count배열안의 수 만큼 요소 출력
	for (int i = 0; i < 3; i++)
	{
		if (list[i] != 0)
		{
			for (int j = 0; j < count[i]; j++)
			{
				cout << i + 1 << " ";
			}
		}
	}
}

count배열의 갯수를 사용해 정렬하여 출력하기

• 우리는 count배열에 들어있는 갯수를 알기때문에 count[i]만큼 반복한 뒤 값을 넣어주면 정렬된 값이 순서대로 나온다
  

결과값:

계수정렬 복잡도

계수정렬 시간복잡도

O(N + k)
-> N은 배열의 크기 (즉, 원소의 갯수)
-> k는 배열에 있는 최대값
1. 원본 배열을 확인하면서 count배열안의 값을 증가시키는 부분 : O(N)
2. count배열 크기만큼 순회하면서 출력하는 부분 : O(k)

계수정렬 공간복잡도

O(k)
-> 계수정렬은 새로운 배열을 할당하여 count값을 세기 때문에 추가적인 메모리가 필요하다
데이터 범위가 크면 배열의 크기가 크므로 메모리 낭비가 심하다

입력받은 배열의 값들 중 최대값으로 count배열의 크기를 정하기 때문에 입력한 값의 범위가 작을때 효율이 높다!

예를 들면)
원본배열안에 1과 1000이 들어있다면 이 원소의 갯수를 저장하기 위한 count배열의 크기는 1000이다.
count[1000];

-> 메모리 낭비도 심하고 비효율적이다

---

계수 정렬 다시해보기

#include <iostream>
#define SIZE 8
using namespace std;


int main()
{
	// 계수 정렬
	// 배열 안에 있는 요소들의 갯수를 새로운 배열에 담고 정렬해서 출력하는 것

	// 값을 비교하지 않고 정렬함

	int array[SIZE] = { 3,3,3,2,2,2,1,1};

	int count[3] = { 0, };

	// count인덱스는 0부터 시작하고, 배열의 실제값은 인덱스보다 1많다
	// count[array[i] - 1]++;로 count배열에 순서대로 저장할 수 있는 이유는 
	// count배열의 크기가 기존 배열의 최대값으로 설정되어 있기 때문

	// 카운트 세기
	for (int i = 0; i < SIZE; i++)
	{
		count[array[i] - 1]++;
	}

	for (int i = 0; i < SIZE; i++)
	{
		if (array[i] != 0)
		{
			for (int j = 0; j < count[i]; j++)
			{
				cout << i + 1 << " ";
			}
		}
	} 

}

---

📌 계수 정렬을 사용한 백준 10989번 문제 풀기

많은 시행착오가 있었던 문제였지만, 결국 계수 정렬을 사용해서 풀면 간단한 문제였다.
➡ 메모리 제한 때문에 vector 자료형을 사용하지 못하고, sort도 사용할 수 없었다.

예전 과정에서는 기존 배열 1개와 카운트를 셀 배열 1개를 사용했는데, 백준 문제에서는 cin을 통해 입력받기 때문에 따로 배열이 2개가 필요하지 않았다. ➡ count 배열만 사용하여 입력 받고 바로 카운팅

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
	int N = 0;    // 입력받을 개수
	int num = 0;  // 입력받기
	
	int count[10001] = { 0 };

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		// 입력받은 수를 카운트 배열에 카운팅
		cin >> num;
		count[num]++;
	}

	for (int i = 0; i < 10001; i++)
	{
		for (int j = 0; j < count[i]; j++)
		{
			cout << i << '\n';
		}
	}
}

코드에 이 구문을 작성하고 안하고 시간 차이가 생각보다 많이 났다.

    ios::sync_with_stdio(false);
    cin.tie(NULL);