[C code] 계수 정렬 (Counting Sort)

첫번째 방법 - 기존의 Array 정렬

#include <stdio.h>
#include <stdlib.h>

// Function to sort an array using counting sort
void CountingSort(int arr[], int n)
{
    //in arr, max value == max == counting_arr max index
    int max = 0 , i;
    for(i=0 ; i<n ; i++)
    {
        if(arr[i] > max)
            max = arr[i];
    }

    int output_arr[n];
    int counting_arr[max];
    for(i=0 ; i<max ; i++)
        counting_arr[i] = 0;

    //filling counting_arr
    for(i=0 ; i<n ; i++)
        counting_arr[arr[i]-1]++;

    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for(i=1 ; i<max ; i++)
        counting_arr[i] += counting_arr[i-1];

    // Build the output_arr
    for(i=n-1 ; i>=0 ; i--)
    {
        output_arr[counting_arr[arr[i]-1]-1] = arr[i];
        counting_arr[arr[i]-1]--;
    }

    // Copy the output array to arr, so that arr now
    // contains sorted values
    for(i=0 ; i<n ; i++)
        arr[i] = output_arr[i];
}

/* Function to print an array */
void PrintArray(int arr[], int size)
{
   printf("\n**********************\n");
   for(int i=0 ; i<size ; i++)
   {
       printf("%4d", arr[i]);
   }
}

// Driver program to test above functions
int main()
{
    int array[5];

    for(int i=0 ; i<5 ; i++)
    {
        printf("Put your %d integers : ", i);
        scanf("%d", array+i);
    }

    int n = sizeof(array)/sizeof(array[0]);
    PrintArray(array, n);
    CountingSort(array, n);
    PrintArray(array, n);

    return 0;
}

계수정렬은 특정한 범위 내에 key로 정렬하는 기술이다 (One of Non-Comparison Sort)

key의 값을 가진 배열원소의 수를 카운팅하며 작동 (kind of hashing)

그리고 출력할 때에 각 배열원소의 위치를 계산함

 - O(n+k) (k는 array의 최댓값) / 

​

수의 범위가 작다면, 메모리 사용이 적으려면 사용!

​

Example:

For simplicity, consider the data in the range 0 to 9.

Input data: 1, 4, 1, 2, 7, 5, 2

-> arr:

Index: 0 1 2 3 4 5 6

Count: 1 4 1 2 7 5 2

​

1) counting_arr에 다음과 같이 채운다. (Input data값이 Index로, 카운트해준다.)

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 2 0 1 1 0 1 0 0

​

2) counting_arr 각 값들에 직전 index값을 더해 업데이트한다.

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 4 4 5 6 6 7 7 7

​

이 값들은 output_arr의 index값들을 가리킴.

​

3) arr를 역순으로 훑으며 정렬한다.

ex:

arr[6]의 값인 2 -> counting_arr[2]의 값인 4 -> output_arr[4] = 2; (후에 output_arr[4]--;)

arr[5]의 값인 5 -> counting_arr[5]의 값인 6 -> output_arr[6] = 5; (후에 output_arr[6]--;)

...

arr[0]의 값인 1 -> counting_arr[1]의 값인 0 -> output_arr[0] = 1;

​

-GeeksforGeeks

-ordo.tistory.com

---

두번째 방법 - Array에 수 입력하여 정렬

#include <stdio.h>
#include <stdlib.h>

int countingArr[10001];

int main()
{
    int N, max=0, i=0, temp;

    scanf("%d", &N); //입력할 수의 개수 입력
    getchar();

    for(i=0 ; i<N ; i++)
    {
        scanf("%d", &temp);

        if(temp > max)
            max = temp; //입력하는 수들의 max값

        countingArr[temp]++; //countinArr의 index값이 입력받은 수 (배열의 값은 index수의 중복 개수)
    }

    i = 0;
    while(i <= max) //max값까지
    {
        if(countingArr[i] > 0)
        {
            printf("%d\n", i);
            countingArr[i]--;
        }
        if(countingArr[i] == 0)
            i++;
    }

    return 0;
}