Counting Sort

#include<stdio.h>
#define LEN 8

int main() {
    int maxValue=0;
    int data[LEN];
    int count[LEN] = { 0, };
    int temp[LEN] = { 0, };

    for (int i = 0; i < LEN; i++) {         
        scanf_s("%d", &data[i]);        // 데이터 입력받기
    }


    for (int i = 0; i < LEN; i++) {
        if (maxValue < data[i]) maxValue = data[i];         // counts배열의 크기 구하기
        count[data[i]] += 1;            // 발생 횟수 세기
    }

    // 각 항목 위치 설정을 위한 카운트 조정
    for (int i = 1; i <= maxValue; i++) {
        count[i] = count[i] + count[i - 1];
    }

    // 카운트를 사용하여 각 항목 위치 결정
    for (int i = LEN - 1; i >= 0; i--) {
        temp[--count[data[i]]] = data[i];
    }

    // 출력
    for (int i = 0; i < LEN; i++) { 
        printf("%d", temp[i]);
    }
}

 

배열 count의 인덱스는 data의 값, count의 값은 data값의 갯수로 한다.

배열 count에서 각 값의 앞에 위치할 값의 개수를 반영하기 위해 카운트 조정한다. 인덱스 1부터 maxValue까지 이전 값과 지금 값을 더해 저장한다.

배열 data의 마지막 값부터 처음 값까지 반복한다.

data의 값을 count의 인덱스로 값을 찾는다. count 값을 1 감소 시킨다.

감소시킨 이 값을 배열 temp의 인덱스로 하여 data값을 저장한다.