Radix Sort in Java

Here is an implementation of radix sort in java.

import java.util.LinkedList;
import java.util.Random;

public class RadixSort {

	// Define the length of the array.
	private static final int LENGTH = 10;

	// Define the queues.
	private static LinkedList[] q = {
			new LinkedList(), // 0
			new LinkedList(), // 1
			new LinkedList(), // 2
			new LinkedList(), // 3
			new LinkedList(), // 4
			new LinkedList(), // 5
			new LinkedList(), // 6
			new LinkedList(), // 7
			new LinkedList(), // 8
			new LinkedList() // 9
	};

	/**
	 * Main method.
	 * @param args
	 */
	public static void main(String[] args)
	{
		// Random List.
		Object[] list = new Object[LENGTH];

		// Generate a random list of numbers.
		for(int r=0; r < LENGTH; r++){
			list[r] = new Random().nextInt(1000 * 1000);
		}

		// Sort the list.
		Object[] sortedList = sort(list);

		// Print the sorted list.
		for(int i=0; i < sortedList.length; i++){
			System.out.println(sortedList[i]);
		}

	}

	/**
	 * Sorts an array of objects (integers) using radix sort.
	 * @param list	The unsorted list.
	 * @return		The sorted list.
	 */
	public static Object[] sort(Object[] list)
	{
		// Get the maximum number of digits.
		int maxDigits = getMaxDigits(list);

		// Iterate through the radix depending on max digits.
		for(int r=1; r <= maxDigits; r++){

			// Iterate through every number.
			int radix;
			for(int n=0; n < list.length; n++){
				// Figure out what queue to put it into.
				radix = getDigitAt(Integer.parseInt(list[n].toString()), r);
				// Put it into it's queue accordinmaxDigits = getMaxDigits(list);g to the radix.
				q[radix].offer(list[n]);
			}

			// Go through the queues and put the numbers back into the list.
			int a=0;
			for(int k=0; k < q.length; k++){
				// Go through every element in the queue.
				while(q[k].peek() != null){
					list[a++] = q[k].poll();
				}
			}

		}

		// Return the list, it is now sorted.
		return list;

	}

	/**
	 * Gets the maximum digits of a list of integers.
	 * @param list
	 * @return
	 */
	public static int getMaxDigits(Object list[])
	{
		// Define the max digits.
		int maxDigits = 0;

		// Iterate through the list.
		int digits;
		for(int i=0; i < list.length; i++){

			// Cast the number to a string.
			digits = getDigits(Integer.parseInt(list[i].toString()));

			// Compare the lengths.
			if(digits > maxDigits){
				maxDigits = digits;
			}

		}

		// Return the max digits.
		return maxDigits;
	}

	/**
	 * Gets the number of digits the specified number has.
	 * @param i
	 * @return
	 */
	public static int getDigits(int i)
	{
		if(i < 10){
			return 1;
		}
		return 1 + getDigits(i / 10);
	}

	/**
	 * Gets the digit at the specified radix of the specified number.
	 * @param number
	 * @param radix
	 * @return
	 */
	public static int getDigitAt(int number, int radix)
	{
		return (int)(number / Math.pow(10,radix-1)) % 10;
	}

}

Leave a Reply

Your email address will not be published. Required fields are marked *