c perle sorte voudrait de l’aide

J’ai une longue liste d’entiers positifs dans un tableau et j’aimerais utiliser un sorting de billes mais je me suis rendu compte que ce n’était pas bien documenté. est-ce que quelqu’un a le code pour une sorte de perle?

Cette page a des implémentations dans plusieurs langues, y compris C: http://rosettacode.org/wiki/Sorting_algorithms/Bead_sort

De cette question , une modification du sorting des billes utilise un espace supplémentaire O(N) au lieu de O(N*k) comme dans la version du code Rosetta.

 void sort(int A[], int N) { int i, j; int *R = calloc(N, sizeof(int)); do for (i = j = 0; i < N; i++) if (A[i]) { R[j++]++; A[i]--; } while (j); for (j = N, i = 0; i < N; i++) A[i] = R[--j]; // A is now sorted ascending. free(R); } 

Cependant, il est au moins 10 fois plus lent que qsort , et il s’aggrave à mesure que les éléments de votre tableau deviennent volumineux. Je ne recommanderais pas de l'utiliser.