[C언어 소스] 계수 정렬(Counter Sort) 알고리즘

[C언어 소스] 계수 정렬(Counter Sort) 알고리즘

언제나 휴일 티스토리

계수 정렬(Counter Sort) 알고리즘.c

//카운터 정렬

#include <time.h>

#include <stdlib.h>

#include <stdio.h>

#include <memory.h>

 

 

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

 

void MakeRandomArr(int *base,int n,int min,int max);//min~max 사이의 랜덤한 값 n개를 만들기

void CounterSort(int *base,int n);

void ViewArr(int *arr,int n);

int main(void)

{

    int arr[100];

    srand((unsigned)time(NULL));

 

    MakeRandomArr(arr,100,1,10);//1~10 사이의 랜덤한 수를 100개 생성

    ViewArr(arr,100);//정렬 전 상태 출력

    CounterSort(arr,100);//계수 정렬

    ViewArr(arr,100);//정렬 후 상태 출력

    return 0;

}

void MakeRandomArr(int *base,int n,int min,int max)

{

    int i = 0;

    for(i=0;i<n;i++)

    {

        base[i] = rand()%(max-min+1) + min;//min~max 사이의 랜덤한 수 발생

    }

}

 

void CounterSort(int *base, int size)

{

    int carr[10]={0}; //돗수 분포포 세기 후에 인덱스 표로 사용

    int index;

    int value;

    int i = 0;

    int *temp;

    temp = (int *)malloc(sizeof(int)*size);//배열 크기의 임시 버퍼 생성

   

    for(i=0;i<size;i++)

    {

        index = base[i]-1;//원소의 값-1

        carr[index]++;     //돗수의 수를 1 증가  

    }   

    for(i=0;i<10;i++)//돗수별 개수 출력

    {

        printf("%d:%d개 ",i,carr[i]);

    }

    printf("\n");

 

    carr[0]--;//맨 앞의 돗수의 개수를 1 감소(맨 뒤에 있는 0을 배치할 인덱스를 의미)

    for(i=1;i<10;i++)

    {

        carr[i] += carr[i-1];//맨 뒤에 있는 i값을 배치할 인덱스를 계산

    }

 

    for(i=size-1; i>=0; i--)

    {

        value = base[i]-1;//인덱스를 얻어옮

        temp[carr[value]] = base[i]; //값을 인덱스 표를 참고하여 배치

        carr[value]--;//인덱스 표의 요소 값 1 감소

    }

    memcpy(base,temp,sizeof(int)*size);//메모리 복사

    free(temp);//임시 할당한 메모리 해제

}

 

void ViewArr(int *arr,int n)

{

    int i = 0;

    for(i=0;i<n;i++)

    {

        printf("%2d ",arr[i]);

    }

    printf("\n");

}