Counting sort
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each object in the output sequence.
Working of Counting Sort algorithm:
Consider the array: arr[] = {1, 4, 1, 2, 7, 5, 2}.
- Input data: {1, 4, 1, 2, 7, 5, 2}
- Take a count array to store the count of each unique object.
- Now, store the count of each unique element in the count array
- If any element repeats itself, simply increase its count.
- Here, the count of each unique element in the count array is as shown below:
- Index: 0 1 2 3 4 5 6 7 8 9
- Count: 0 2 2 0 1 1 0 1 0 0
- Modify the count array such that each element at each index stores the sum of previous counts.
- Index: 0 1 2 3 4 5 6 7 8 9
- Count: 0 2 4 4 5 6 6 7 7 7
- The modified count array indicates the position of each object in the output sequence.
- Find the index of each element of the original array in the count array. This gives the cumulative count.
- Rotate the array clockwise for one time.
- Index: 0 1 2 3 4 5 6 7 8 9
- Count: 0 0 2 4 4 5 6 6 7 7
- Output each object from the input sequence followed by increasing its count by 1.
- Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 0.
- Put data 1 at index 0 in output. Increase count by 1 to place next data 1 at an index 1 greater than this index.
- After placing each element at its correct position, decrease its count by one.
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials
Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when it is arranged randomly. When this happens, sorting that data becomes crucial. It is necessary to sort data in order to make searching easier.
Contact Us