Skip to content

Instantly share code, notes, and snippets.

@honghaoz
Last active August 29, 2015 14:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save honghaoz/a2dac73b0f5eab8ec668 to your computer and use it in GitHub Desktop.
Save honghaoz/a2dac73b0f5eab8ec668 to your computer and use it in GitHub Desktop.
CountSort
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment