|
Be the first user to complete this post
|
Add to List |
114. Counting Sort Algorithm
Counting Sort is a non-comparative integer sorting algorithm that works efficiently when the range of input values is relatively small compared to the number of elements to be sorted. It's often used when the input consists of integers within a known range, such as in cases where the input values are bounded by a constant or a small range of integers.
Implementation:
-
Counting Occurrences:
- Counting Sort begins by counting the occurrences of each distinct element in the input array. It creates an auxiliary array, usually called
Count, to store these counts. - The
Countthe array has a size equal to the range of the input values plus one, as it will store the count of each integer from 0 to the maximum value present in the input array.
- Counting Sort begins by counting the occurrences of each distinct element in the input array. It creates an auxiliary array, usually called
-
Cumulative Counts:
- After counting the occurrences, Counting Sort updates the
Countarray so that each indexiholds the cumulative count of elements less than or equal toi. - This step ensures that each index in the
Countarray reflects the correct position for each element in the sorted output.
- After counting the occurrences, Counting Sort updates the
-
Building the Sorted Array:
- With the
Countarray prepared, Counting Sort traverses the input array in a forward or backward direction, depending on the sorting order needed. - For each element input
[i]in the input array, Counting Sort finds its correct position in the output array using the count stored inCount[input[i]]. - After placing an element in its correct position, Counting Sort decrements the count to indicate that this element has been accounted for in the sorted output.
- With the
-
Output:
- Once all elements have been placed in the correct positions in the output array, Counting Sort returns the sorted array.
Time complexity: O(n + k)
Space Complexity: O(n + k)
n is the number of elements in the input array and k is the range of the input values
Output:
Orginal Array [2, 1, 4, 5, 7, 1, 1, 8, 9, 10, 11, 14, 15, 3, 2, 4] Sorted Array : [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 10, 11, 14, 15]