Encyclopedia > Counting sort

  Article Content

Counting sort

Counting Sort - a sorting algorithm which takes advantage of knowing the maximum value within the array to be sorted and uses this to create an array (referenced by the values within the array to be sorted) that will serve to count the number of values of a certain number and, after this, the future positions of the values on a third array, which is the sorted permutation of the second array (i.e., A[i] <= A[j], i < j). This algorithm is stable and it is O(n+k), where k is the maximum value within the array. In order for this algorithm to have any semblance of efficiency, k must be comparatively small. The values within an array have to be known and non-negative.

References:

  • Cormen, et al. Introduction to Algorithms 2nd. ed. 2001. The MIT Press.
  • Seward, Harold H. Information sorting in the application of electronic digital computers to business operations Masters thesis. MIT 1954.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Westhampton Beach, New York

... is 65 years of age or older. The average household size is 2.25 and the average family size is 2.81. In the village the population is spread out with 20.5% under the age ...

 
 
 
This page was created in 38.1 ms