[C언어 계수 정렬 알고리즘] 계수 정렬 구현하기

💡 이번에는 계수 정렬 하는 법을 배워보았다.

문제

💡 사용자가 입력한 값이 오름차순으로 계수 정렬 되게 코드를 구현하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_VALUE 10001

int n, m;
int a[MAX_VALUE];

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

    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &m);
        a[m]++;
    }

    for (int i = 0 ; i < MAX_VALUE ; i++) {
        while (a[i] != 0 ) {
            printf("%d ", i);
            a[i]--;
        }
    }

    return 0;
}

설명

계수 정렬이란?

Counting Sort라고 하는 계수정렬은 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘이다.

각 데이터를 바로 크기를 기준으로 분류하므로 𝑂(𝑁)의 시간 복잡도를 가진다.

하지만 상당히 많은 메모리 소비가 있기 때문에 MAX_VALUE를 지정해줘야 한다.

2102213103

아래는 크기를 기준으로 분류한 표이다.

인덱스0123

원소

2

3

3

2

차례대로 원소의 개수만큼 출력 : 0 0 1 1 1 2 2 2 3 3

main 함수

int main() {
    scanf("%d", &n);  // 원소의 개수를 입력한다.

    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &m);  // 입력된 원소를 받는다.
        a[m]++;  // 바로 해당 인덱스의 값을 + 해준다.
    }

    for (int i = 0 ; i < MAX_VALUE ; i++) {
        while (a[i] != 0 ) {  // 해당 인덱스의 값이 0이 아닐때까지 출력 한다.
            printf("%d ", i);
            a[i]--;  // 출력 후 해당 인덱스의 값 - 처리 해준다.
        }
    }

    return 0;
}

---

마치며..

이제까지 중에서 가장 이해하기 쉽고 짜기 쉬웠던 코드였다.

가끔은 이런 것도 나와주라구..!