Overleg:Counting sort

counting sort is standaard O(n+k), maar de voorbeeldalgorithmes zijn dat niet. Ze hebben een allemaal een dubbele forloop (of een forloop while loop). De volgende pseudocode is daarom beter:

 void counting_sort(int A[], int B[], int k) {
   int C[k+1];
   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;
   }
 }

Het algoritme dat op deze pagina wordt beschreven is niet de volledige versie van counting sort. Er kunnen alleen gehele integers gesorteerd worden en niet delen van integers waarbij de volgorde behouden blijft. Counting sort is oorspronkelijk geintroduceerd voor het implementeren van radix sort en die eigenschap is dus essentieel. – De voorgaande bijdrage werd geplaatst door 80.115.2.241 (overleg · bijdragen) 25 jun 2017 13:42