힙정렬(Heap sort)과 계수정렬(Counting sort)을 C로 짜보기

소스코드 : 

#include <stdio.h>

#include <iostream>

using namespace std;

void counting_sort(int A[], int k, int n){

    int i, j;

    int B[15], C[100];

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;

    }

    printf("계수정렬 결과 : ");

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

        printf("%d ", B[i]);

}

void heapify(int A[], int n, int i){

    int largest = i;

    int l = 2*i + 1; 

    int r = 2*i + 2;

    if (l < n && A[l] > A[largest])

        largest = l;

    if (r < n && A[r] > A[largest])

        largest = r;

    if (largest != i){

        swap(A[i], A[largest]);

        heapify(A, n, largest);

    }

}

void heap_sort(int A[], int n){

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(A, n, i);

    for (int i=n-1; i>=0; i--){

        swap(A[0], A[i]);

        heapify(A, i, 0);

    }

printf("힙정렬 결과 : ");

    for (int i = 1; i <= n; i++)

        printf("%d ", A[i]);

}

int main(){

    int n, k = 0, A[15], i;

printf("입력할 값들의 갯수를 입력해주세요 : ");

    scanf("%d", &n);

    for (i = 1; i <= n; i++){

printf("\n%d번째의 입력값을 입력해주세요 : ",i);

        scanf("%d", &A[i]);

        if (A[i] > k){

            k = A[i];

        }

    }

    counting_sort(A, k, n);

    printf("\n");

heap_sort(A, n);

printf("\n");

    return 0;

}

실행결과 :