Consider this array. What is the first thing you notice? Yes, right. This array has repeating values in a small range. Counting array uses the idea of storing the frequencies of elements. This is a non-comparison based sorting. It doesn’t compare its elements with each other. Let’s see how it goes!
What can we use to store the frequencies? A map? yes, we can use a map. But we will use an array. You can ask why? In maps, hashing functions are used. These functions are used to translate a key to a value. This is costly in terms of time and space. Whereas, if we consider an array’s indices representing elements and value on those indices as the frequency of these elements, we can get the job done in less space and time. Got confused? …
In the array, all the elements need to be stored continuously. Let’s see some of the shortcomings of the array —
What do we mean by the Hash Value of some data? It is a value that uniquely identifies a large data. When we are searching for a value in an array, searching traditionally will take linear time. This can be reduced to logarithmic time if the data is sorted. But most data is not sorted, and sorting it will take more than linear time. There is a ton of data being produced every second. Searching through it linearly could take several days. What can we do to do this search in constant time? …
All this time I kept using printf and writing functions but never gave it much thought that printf accepts as many arguments as you want. How about we write a function that does the same?
The header file we’re going to use is cstdarg in C++ and stdarg.h in C. This header provides us one type and some macro functions to handle the argument list.