(C, C++) - 카운팅 정렬(counting sort)

< 카운팅 정렬 > - 시간 복잡도 O(n): 특수 케이스에서 일반적으로 빠른 퀵(Quick) 정렬(시간 복잡도 O(nlongn))보다 더 빠름

1. 가장 큰 숫자의 값만큼 배열의 방을 만듬

2. 입력받은 값의 수를 세서 만든 배열에 넣어줌

3. 만든 배열의 방을 누적합으로 바꿔줌

4. 입력받은 배열의 인덱스 값들을 순서대로 읽으며 만든 배열의 인덱스로 가게함

5. 그 후 만든 배열의 인덱스의 값을 하나 감소시킨 값을 정렬시킬 배열안에 넣어줌

#include <iostream>
#include <stdio.h>
using namespace std;
 
void counting_sort(int A[], int k, int n)
{
    int i, j;
    int *B = new int[n];
    int *C = new int[n];
    for (i = 0; i <= k; i++)
        C[i] = 0;
    for (j = 1; j <= n; j++)
        C[A[j]] = C[A[j]] + 1;
    for (i = 1; i <= k; i++)
        C[i] = C[i] + C[i - 1];
    for (j = n; j >= 1; j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }
    
    for (i = 1; i <= n; i++)
        printf("%d \n", B[i]);
}
 
{
    int n, k = 0, i;
    
    scanf("%d", &n);
    int *A = new int[n];
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &A[i]);
        if (A[i] > k) {
            k = A[i];
        }
    }
    counting_sort(A, k, n);
    printf("\n");
    return 0;
}