C언어 카운팅 정렬 단순정리 & 백준(S5) 수 정렬하기 (C언어 C11 C99)

정렬 알고리즘 중 가장 빠른 정렬.

정렬 함수의 속도는 O(N)이다. 

지금까지 다른 함수들은 데이터를 위치를 바꿔가며 정렬했지만, 정렬 함수는 데이터의 크기를 기준으로 개수만 세면 되기 때문에 다른 정렬들보다 시간을 많이 아낄 수 있다.

for (int a = 0; a < num; a++)
    {
        scanf("%d", &numbers);
        if (numbers > max)
        {
            max = numbers;
        }
        countings[numbers - 1]++;
    }

이렇게 입력을 하면서 바로 데이터의 크기를 기준으로 갯수를 셀 수 있다.

 

개수를 센 다음에는 밑에 나와있는 코딩처럼 데이터 크기를 저장한 배열을 출력하면 된다.

for (int a = 0; a < max; a++)
    {
        if (countings[a] != 0)
            for (int i = 0; i < countings[a]; i++)
            {
                printf("%d\n", a + 1);
            }
    }

#include <stdio.h>
int countings[10000];
int main()
{
    int num;
    int numbers;
    int max = 0;
    scanf("%d", &num);
    for (int a = 0; a < num; a++)
    {
        scanf("%d", &numbers);
        if (numbers > max)
        {
            max = numbers; // 원래라면 입력값을 저장하는 배열이 있어야 하는데 숫자의 개수가 너무 많으므로 저장하지 않고 입력한다.
        }
        countings[numbers - 1]++; // 데이터의 크기를 기준으로 분류하는 배열에 바로 저장돼야한다.
    }
    for (int a = 0; a < max; a++)
    {
        if (countings[a] != 0)
            for (int i = 0; i < countings[a]; i++)
            {
                printf("%d\n", a + 1);
            }
    }
    return 0;
}