Sorting Algorithms Questions Medium
Radix sort, counting sort, and bucket sort are all linear time sorting algorithms, meaning their time complexities are directly proportional to the size of the input array.
1. Radix Sort:
The time complexity of radix sort is O(d * (n + k)), where n is the number of elements in the input array, k is the range of values, and d is the number of digits in the maximum value. Radix sort works by sorting the elements based on each digit, from the least significant to the most significant. It performs counting sort for each digit, which takes O(n + k) time. The number of digits, d, determines the number of iterations required. In the worst case, d is proportional to log base 10 of the maximum value, resulting in a time complexity of O((n + k) * log(k)).
2. Counting Sort:
The time complexity of counting sort is O(n + k), where n is the number of elements in the input array and k is the range of values. Counting sort works by counting the occurrences of each element and then determining their positions in the sorted array. It creates a count array of size k+1 to store the frequency of each element. The count array is then modified to store the actual position of each element in the sorted array. Finally, the sorted array is constructed using the modified count array. Counting sort has a linear time complexity because it iterates over the input array once to count the occurrences and once again to construct the sorted array.
3. Bucket Sort:
The time complexity of bucket sort is O(n + k), where n is the number of elements in the input array and k is the number of buckets. Bucket sort works by dividing the input array into k equally sized buckets, distributing the elements into these buckets, and then sorting each bucket individually. The time complexity of distributing the elements into buckets is O(n), and the time complexity of sorting each bucket depends on the sorting algorithm used. In the average case, if the elements are uniformly distributed across the buckets, the time complexity of bucket sort is O(n + n/k * log(n/k)), which simplifies to O(n + n * log(n/k)).
In summary, radix sort, counting sort, and bucket sort all have linear time complexities, but the specific time complexity may vary depending on the range of values and the number of digits or buckets. Counting sort and bucket sort have the same time complexity of O(n + k), while radix sort has a time complexity of O((n + k) * log(k)) in the worst case.