Algorithms in a Nutshell

(^92) | Chapter 4: Sorting Algorithms
Forces
COUNTINGSORTsucceeds only because thekvalues form a total ordering for the
elements.
Solution
COUNTINGSORTcreateskbuckets that store the number of times thekth
element was seen in the input array. COUNTINGSORTthen makes two passes
over the input array. During the first pass, COUNTINGSORTincrements the
count of thekthbucket. In the second pass, COUNTINGSORToverwrites the orig-
inal array by processing the count values in the total ordering provided byk
buckets. The COUNTINGSORTimplementation in Example 4-10 relies on the
calling function to determine the proper value fork.
Figure 4-17. Counting Sort fact sheet
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use