C++ Data Structures and Algorithms

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 ...