Non Comparison Based Sorting
Non Comparisons Based Sorting Algorithm sort data directly comparing the elements. Instead they utilize the properties of the data to achieve efficient sorting. The primary Non Comparisons based sorting algorithms are: –
1. Counting Sort
Counting Sort is an integer sorting algorithms that operates by counting the number of occurrences of each unique element in the input array. The counts are then used to determine the position of each element in the sorted output array.
Key Characteristics
- Complexity : – O(n+k), where n is the number of elements in the input array, and k is the range of the input values.
- Stability : – Stable, as it maintains the relative order of equal elements.
- In – Place: – No, requires additional space for the count array.
2. Radix Sort
Radix Sort number by processing individuals digits. It processes each digit of the numbers, starting from the least significant digits (LSD radix Sort) or vice versa (MSD Radix Sort), using stable sorting algorithm like counting sort as a subroutine.
Key Characteristics
- Complexity : – O (d – (n + b) ), where d is the number of digits, n is the number of elements, and b is the base of the number system.
- Stability : – Stable if the underlying sorting algorithms is stable.
- In – Place: – No, requires additional space for sorting each other.
3. Bucket Sort
Bucket Sort distributes elements into several buckets and then sorts each bucket individually using another sorting algorithms. The individual buckets are the connected concatenated to produce the final sorted array.
key Characteristics
- Complexity: – O (n + k), where n is the number of elements, and k is the number of buckets.
- Stability : – Depends on the stability of the sorting algorithms used within the buckets.
- In – Place: – No, requires additional space for the buckets.
