Tag Archives: MSD

Radix Sort Program and Complexity (Big-O)


Radixsort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position. To sort these specific positions data counting sort as a subroutine.

Counting sort is a linear time sorting algorithm that sort in O(n+k) but that will worst in case of items range from 1 to n2 that sort in O(n^2). Where K is items range from 1 to k.

Note :

  • LSD : Least Significant Digit
  • MSD : Most Significant Digit

Steps to Radixsort

  1. Check for the max length item in input values and check for length.
  2. For each digit position i where i varies from LSD to the MSD.
  3. Perform counting sort based on considering key as i position digits.
  4. Finally, you will get a sorting array for input items.

Points to Remember

  • Data Structure: Array
  • Best Time Complexity: Ω(nk)
  • Average Time Complexity: Θ(nk)
  • Worst Time Complexity: O(nk)
  • Worst Space Complexity: O(n+k)

Radix sort Example


Input Numbers:

        170, 45, 75, 90, 02, 802, 2, 66 
Step 1 : Find the max item length in input i.e 3.

Step 2: Repeat the below process for position i from LSD to MSD
        Perform count sort on numbers, after considering digits as key on 
        particular i.
        
        0 Position :
        170, 90, 02, 802, 2, 45, 75, 66
        
        1 Position :
        02, 2, 802, 45, 66, 170, 75, 90
        
        2 Position :
        02, 2, 45, 66, 75, 90, 170, 802 
        
Step 3: Final Redix Sort result

        02, 2, 45, 66, 75, 90, 170, 802    
 

Radix Sort Program

public class RadixSort {

	public static void main(String[] args) {

		// Assuming our key values are with in range 0 - 9
		int[] items = { 170, 45, 75, 90, 02, 802, 2, 66 };
		System.out.println("Before Radix Sorting :");
		printArray(items);

		// Perform counting sort sort
		radixsort(items);

		System.out.println("After Radix Sorting :");
		printArray(items);
	}

	// radix sort method to sort values of array items
	static void radixsort(int items[]) {
		// find max number to know max number of digits
		int m = getMax(items);

		// Perform counting sort for every digit. Note that instead
		// of passing digit number, exp is passed. exp is 10^i
		// where i is current digit number
		for (int exp = 1; m / exp > 0; exp *= 10)
			countingsort(items, exp);
	}

	// A utility method to get maximum value in items[]
	static int getMax(int items[]) {
		int max = items[0];
		for (int i = 1; i  max)
				max = items[i];
		return max;
	}

	private static void countingsort(int[] items, int exp) {
		// create array of size 10 that will have index value as 0-9
		// it will create array of size 10 and initialize
		// each element with value 0
		int[] counts = new int[10];
		int[] output = new int[items.length];
		for (int key : items) {
			// for each match key, index position element
			// increase count as 1
			counts[(key / exp) % 10] += 1;
		}

		// Change count[i] so that count[i] now contains
		// actual position of this digit in output[]
		for (int i = 1; i = 0; i--) {
			output[counts[(items[i] / exp) % 10] - 1] = items[i];
			counts[(items[i] / exp) % 10] -= 1;
		}

		// Copy the output array to items[] to return
		// sorted array according to index position
		for (int i = 0; i < items.length; i++)
			items[i] = output[i];

	}

	static void printArray(int items[]) {
		for (int item : items) {
			System.out.print(item + " ");
		}
		System.out.println();
	}

}

Output


Before Radix Sorting :
170 45 75 90 2 802 2 66 
After Radix Sorting :
2 2 45 66 75 90 170 802