Counting sort
Counting sort is a sorting algorithm that arranges items based on a key. Suppose we have an array containing unsorted items with a range between 0 to 9; we can sort it by counting the number of items based on the range as the key. Let's say we have an array of these items—{9, 6, 5, 6, 1, 7, 2, 4, 3, 5, 7, 7, 9, 6}
. In a simple explanation, we just need to count the frequency of the occurrence of each item. We then iterate through the range from 0 to 9 to output the items in a sorted order. Initially, we will have an array containing the following items:
Now, we count the occurrence frequency of each item. Items 1, 2, 3, 4 will occur only once, items 5 and 9 occur twice, items 6 and 7 occur three times, and item 8 never occurs. This can be seen in the following diagram:
Based on this collection, we can reconstruct the array from the lowest item so that we end up with the following result:
Creating C++ code for counting sort is quite simple; we just need to prepare the counterArray...