[자료구조] 계수정렬(C) & 백준 [10989] 수 정렬3(C)

출처 | https://www.youtube.com/watch?v=n4kbFRn2z9M

이번 시간에는 계수정렬에 대해서 알아보겠다.

계수정렬이란?

주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

[계수정렬]

다음의 5이하 자연수 데이터들을 오름차순 정렬하세요

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

[범위가 주어지면 쓸 수 있는 빠른 알고리즘 -> 계수정렬 ]
이번 예시는 정렬할 데이터의 갯수가 30개 다. 다만 보시면 모든 데이터가 1부터 5사이에 속한다는 특징이 있다.
'범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이다. o(n) 속도다. 이 알고리즘은 '계수 정렬' 이라고 하며 '크기를 기준으로 세는' 알고리즘이다.

개념

크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    0	  0	   0  	  0	 0


1. 1번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1 

크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    1	     0	   	    0  	      0	        0

2. 2번째 상태
크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    1	     0	        1 	       0	     0

3. 3번째 상태
크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    1	     1	        1 	      0	        0


3. 4번째 상태
크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    1	     1	       1 	     1	        0

4. 5번째 상태 
크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    1	    1	      2	        1	       0


5. n번째 상태[끝 까지 다 읽은 경우]
크기 = 1 | 크기 = 2 | 크기 = 3 | 크기 = 4 | 크기 = 5 
    8	    6	      8	        4	       4

크기 1부터 5까지 해당 숫자만큼 출력하고 즉 1을 8번 출력하고 2를 6번 출력하고 3을 8번 출력하고 4를 4번 출력하고 5를 4번 출력하면 정렬이 이루어진다.

[동빈나 구현]

//계수정렬

#include <stdio.h>


int main()
{
	int temp;
	int count[5];
	int array[30] = {
		1,3,2,4,3,2,5,3,1,2,
		3,4,4,3,5,1,2,3,5,2,
		3,1,4,3,5,1,2,1,1,1
	};

	for (int i = 0; i < 5; i++)
	{
		count[i] = 0;

	}

	for (int i = 0; i < 30; i++)
	{
		count[array[i] - 1]++;
	}
	//count 1 -> 몇 만큼 증가하고 감소하는지 나타내는 것.


	for (int i = 0; i < 5; i++)
	{
		if (count[i] != 0) //들어있는 데이터가 0이 아닌 이상 
		{
			for (int j = 0; j < count[i]; j++)
			{
				printf("%d", i + 1);
			}
		}
	}

}

//계수정렬은 범위가 주어진 한에서 사용하는 정렬 방법이다. [동빈나 구현 예제 ]

// 구현

// 총 2가지가 필요하다. 

// 1. array[30] = { 정렬할 수 }

// 2. count[5] => 정렬할 수 에서 범위를 구한 다음 카운팅 하는 배열

// 3. 카운팅 구현은 어떻게 구현하는가? count[array[i] - 1]++ 하는 아이디어가 중요하다 

// 4. for(~~~;; 돌리면서) if(count[i] != 0)

// 5. j를 돌리면서 count[i] 만큼 출력하는 아이디어가 중요하다. 

개념 참고하기

https://yaboong.github.io/algorithms/2018/03/20/counting-sort/

10989번 백준 문제풀이

#include <stdio.h>

int main(void) {
    int N;
    scanf("%d", &N);

    // 1. 카운팅 배열 선언/초기화
    int counting[10001];
    for (int i = 0; i < 10001; i++) {
        counting[i] = 0;
    }

    // 2. 카운팅 정렬 (입력)
    for (int i = 0; i < N; i++) {
        int input;
        scanf("%d", &input);
        counting[input]++;
    }

    // 3. 카운팅 정렬 (출력)
    for (int i = 0; i < 10001; i++) {
        // counting[i] 횟수만큼 i 출력
        for (int j = 0; j < counting[i]; j++) {
            printf("%d\n", i);
        }
    }
}


//첫 단계는 카운팅 배열을 만드는 단계
// 입력될 수들의 범위가 10,000 이하라는 조건이 주어지므로 10,001의 크기를 가진
// 카운팅 배열을 선언 / 초기화한다. 카운팅 배열 선언을 완료하면, 입력을 받으며 각 숫자를 카운팅 배열에 기록
// 최대 인덱스가 정확히 10,000 이므로, 어떤 숫자가 입력되어도 그 숫자에 해당하는 인덱스가 존재하여 입력이 가능하다.
// 마지막 단계에서는 counting 배열 수들의 출력을 진행한다..