RADIX SORT

Radix sort processes the elements the same way in which the names of the students are sorted according to their alphabetical order. There are 26 radix in that case due to the fact that, there are 26 alphabets in English. In the first pass, the names are grouped according to the ascending order of the first letter of names.

In the second pass, the names are grouped according to the ascending order of the second letter. The same process continues until we find the sorted list of names. The bucket are used to store the names produced in each pass. The number of passes depends upon the length of the name with the maximum letter.

In the case of integers, radix sort sorts the numbers according to their digits. There are 10 radix in that case due to the fact that, there are 0-9 digits in number.

The comparisons are made among the digits of the number starting from units place , then comparing Tenths place, then hundredth place and so on, till the largest number all digits are compared.

Example

Consider the array of length 6 given below. Sort the array by using Radix sort.

A = {10, 2, 901, 803, 1024}

Pass 1: (Sort the list according to the digits at 0’s place)

10, 901, 2, 803, 1024.

Pass 2: (Sort the list according to the digits at 10’s place)

02, 10, 901, 803, 1024

Pass 3: (Sort the list according to the digits at 100’s place)

02, 10, 1024, 803, 901.

Pass 4: (Sort the list according to the digits at 1000’s place)

02, 10, 803, 901, 1024

Therefore, the list generated in the step 4 is the sorted list, arranged from radix sort.

import java.util.ArrayList;

public class RadixSort {
	public static void main(String args[]) {
		int RADIX = 10;
		// int inputArray[] = { 1, 32, 101, 100, 54, 355, 102, 43, 10, 287, 005,
		// 23, 300, 11, 500, 34, 1111, 33333, 12 };
		int inputArray[] = { 10, 2, 901, 803, 1024 };
		ArrayList<Integer>[] bucketArray = new ArrayList[RADIX];
		for (int i = 0; i < bucketArray.length; i++) {
			bucketArray[i] = new ArrayList<>();
		}
		boolean maxDigitLengthReached = false;
		int digitPlace = 1;
		while (!maxDigitLengthReached) {
			maxDigitLengthReached = true;
			for (int i : inputArray) {
				bucketArray[i / digitPlace % RADIX].add(i);
				if (i / digitPlace > 0 && maxDigitLengthReached) {
					maxDigitLengthReached = false;
				}
			}
			System.out.println("Sorted Data after Digit Place :: " + digitPlace);
			for (ArrayList<Integer> i : bucketArray) {
				if (!i.isEmpty())
					System.out.print(i + " ");
			}
			System.out.println();
			System.out.println();

			int a = 0;
			for (int i = 0; i < bucketArray.length; i++) {
				for (int j : bucketArray[i]) {
					inputArray[a++] = j;
				}
				bucketArray[i].clear();
			}
			digitPlace = digitPlace * 10;
		}
                System.out.println("Sorted List :: ");
		for (int i : inputArray) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

Sorted Data after Digit Place :: 1
[10] [901] [2] [803] [1024] 

Sorted Data after Digit Place :: 10
[901, 2, 803] [10] [1024] 

Sorted Data after Digit Place :: 100
[2, 10, 1024] [803] [901] 

Sorted Data after Digit Place :: 1000
[2, 10, 803, 901] [1024] 

Sorted Data after Digit Place :: 10000
[2, 10, 803, 901, 1024] 

Sorted List :: 
2 10 803 901 1024 

Complexity

k is the length of the longest number and n is the size of the input array.