CountSort

Sort-CountSort.cpp

#include<iostream>
using namespace std;

void countSort(int a[], int size, int k) {
    int *b = (int *)malloc(sizeof(int) * k);
    memset(b, 0, sizeof(int) * k);
    for (int i = 0; i < size; i++) {
        b[a[i]]++;
    }
    for (int i = 1; i < k; i++) {
        b[i] += b[i - 1];
    }
    int *c = (int *)malloc(sizeof(int) * size);
    memset(c, 0, sizeof(int) * size);
    for (int i = 0; i < size; i++) {
        c[i] = a[i];
    }
    for (int i = size - 1; i >= 0; i--) {
        a[b[c[i]] - 1] = c[i];
        b[c[i]]--;
    }
    free(b);
    free(c);
}

int main() {
    int a[] = {6,4,7,3,7,1,2,3,9,10};
    countSort(a, 10, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}