Radix Sort
Radix Sort
Radix sort is a sorting algorithm and it sorts the elements by first grouping the individual digits of the same place value.
Algorithm
Suppose we take an unsorted array and sorted it using radixsort.
In the given array, the larsgest element is736 that havethree digits included it. So, the loop will run up to three times that is to the hundreds place. Thats three passes are required to sorting the array.
Now, first sort the elements on the basis of unit place digits that is x = 0. Here, we are using the counting sort algorithm to sort the elements.
Pass 1:
In the pass first, the list is sorted on the basis of the digits at zeros place.
After the first pass, the array elements are –
Pass 2:
In this pass, the list is sorted on the basis of the next significant digits that is digits at tens place.
After that second pass, the array elements are given below
Pass 3:
In this pass, the list is sorted on the basis of the next significant digits that is digits at hundread place.
After that third pass, the array elements are given below
Program of Radix sort in C
#include <stdio.h>
// Function
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1;int i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
void countingSort(int array[], int size, int place) {
int output[size + 1];
int max = (array[0] / place) % 10;
for (int i = 1; int i < size; i++) {
if (((array[i] / place) % 10) > max)
max = array[i];
}
int count[max + 1];
for (int i = 0; int i < max; ++i)
count[i] = 0;
for (int i = 0; int i < size; i++)
count[(array[i] / place) % 10]++;
for (int i = 1;int i < 10; i++)
count[i] += count[i - 1];
for (int i = size - 1; int i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; int i < size; i++)
array[i] = output[i];
}
// Main function
void radixsort(int array[], int size) {
int max = getMax(array, size);
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
void printArray(int array[], int size) {
for (int i = 0; int i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int array[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(array) / sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
Output
1 23 45 121 432 564 788
Program of Radix sort in C++
#include <iostream>
using namespace std;
// Function
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1;int i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
void countingSort(int array[], int size, int place) {
const int max = 10;
int output[size];
int count[max];
for (int i = 0; int i < max; ++i)
count[i] = 0;
for (int i = 0;int i < size; i++)
count[(array[i] / place) % 10]++;
//cumulative count
for (int i = 1; int i < max; i++)
count[i] += count[i - 1];
// elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// Main function
void radixsort(int array[], int size) {
// Get maximum element
int max = getMax(array, size);
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// Print array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver code
int main() {
int array[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(array) / sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
Output
1 23 45 121 432 564 788
Program of Radix sort in Python
def countingSort(array, place):
size = len(array)
output = [0] * size
count = [0] * 10
# count of elements
for i in range(0, size):
index = array[i] // place
count[index % 10] += 1
# cumulative count
for i in range(1, 10):
count[i] += count[i - 1]
# elements in sorted order
i = size - 1
while i >= 0:
index = array[i] // place
output[count[index % 10] - 1] = array[i]
count[index % 10] -= 1
i -= 1
for i in range(0, size):
array[i] = output[i]
# Main function
def radixSort(array):
max_element = max(array)
place = 1
while max_element // place > 0:
countingSort(array, place)
place *= 10
data = [121, 432, 564, 23, 1, 45, 788]
radixSort(data)
print(data)
Output
[1, 23, 45, 121, 432, 564, 788]
Program of Radix sort in Java
import java.util.Arrays;
class RadixSort {
void countingSort(int array[], int size, int place) {
int[] output = new int[size + 1];
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
int[] count = new int[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
//count of elements
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
//cumulative count
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
//elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// Function
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++)
if (array[i] > max)
max = array[i];
return max;
}
// implement radix sort
void radixSort(int array[], int size) {
// Get maximum element
int max = getMax(array, size);
// Apply counting sort
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// Driver code
public static void main(String args[]) {
int[] data = { 121, 432, 564, 23, 1, 45, 788 };
int size = data.length;
RadixSort rs = new RadixSort();
rs.radixSort(data, size);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
Output
Sorted Array in Ascending Order: [1, 23, 45, 121, 432, 564, 788]
Best Case Complexity
Best case complexity occurs when there is no sorting required.That is when the array is already sorted.
The best-case time complexity is Ω(n+k).
Average Case Complexity
Average case complexity occurs when the array elements are in jumbled order that is not properly ascending and descending.
The average case time complexity is θ(nk).
Worst Case Complexity
Worst case complexity occurs when the array elements are required to be sorted in reverse order.
The worst-case time complexity of is O(nk).
2. Space Complexity
| Space Complexity | O(n + k) |
| Stable | YES |
The space complexity O(n + k).
Read more, Counting Sort