계수 정렬

  • 계수 정렬(Counting Sort)는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘 이다.
  • 각 데이터를 바로 크기를 기준으로 분류하므로 O(N)의 시간 복잡도를 가진다.

먼저 아래와 같이 총 4개의 원소가 있는 배열을 만든다.
image.png

하나의 원소를 발견할 때 마다, 해당 원소의 값을 1씩 증가 시킨다.

맨 처음에 2가 나왔으므로, 첫번째 배열의 2번인덱스 값을 1증가 시키면서 입력 배열의 끝까지 반복을 진행한다.

image.png

입력배열을 끝까지 돌고나면, 계수정렬된 배열을 앞에서부터 차례대로 출력하면 된다.

image.png


#define MAX_VALUE 10001
#include <stdio.h>

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]--;
        }
    }
}

기수정렬

기수 정렬(Redix Sort)는 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘입니다. 각 데이터를 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도를 가진다.

자릿수 배열은 각 자릿수에대한 정보를 저장한다. 자릿수배열을 저장하는 것은 계수정렬과 같은 원리로 저장시킨다.(이때, 누적값을 저장해야함)

image.png

image.png

결과배열을 만들때는 입력배열의 뒤에서부터 확인을 하면된다. 가장 뒤에 현재 34가 있는데, 34의 일의자리 4값을 자릿수 배열의 4번째 인덱스에 저장을 했으므로, 결과배열에 4번째 자리에 34를 넣는다.

image.png

결과적으로 1의자리에 대해서는 정렬이 완료된 상태가 된다.
image.png

1의자리정렬을 완료한 후에는 10의자리에 대해서 정렬을 수행한다.

image.png

image.png

10의자리 정렬 후에는 100의자리에 대해서 정렬을 수행한다.

image.png

image.png

#include<stdio.h>
# define MAX 10000

void redixSort(int * a, int n) {
    int res[MAX], maxValue = 0;
    int exp = 1;
    //가장큰 값의 자리수를 구하기 위해서 가장 큰값 찾 
    for(int i = 0; i < n; i++) {
        if(a[i] > maxValue) maxValue = a[i];
    }

    while (maxValue / exp > 0) {

        int bucket[10] = {0};
        for(int i = 0; i < n; i++) bucket[a[i] / exp % 10]++;
        for(int i = 1; i < 10; i++) bucket[i]+= bucket[i-1];
        for(int i = n-1; i >= 0; i--){

            res[--bucket[a[i] / exp % 10]] = a[i];
              //누적값을 1씩 감소시키면서 이동하기 위해서 --한다.
        }
        for(int i = 0; i < n; i++) a[i] = res[i];
        exp *= 10;
    }
} 

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

    for(int i = 0; i < n ; i++) {
        printf("%d ",a[i]);
    }
}
//123 / 1 % 10 = 3
//123 / 10 % 10 = 2
//123 / 100 % 10 = 1