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.