Radix Sort in Java

Goal: Fill in the the TODO area within the radixSort method to make the program sort from smallest to largest.

Note: I already did countingSort, so don't change anything in the countingSort method unless I have an error.

--------------

The following are the code:

---------------

package edu.wit.cs.comp3370;

import java.util.Arrays; import java.util.Scanner; import java.util.ArrayList;

/** Sorts integers from command line using various algorithms. * Once you pass the JUnits, run ChartMaker.java to visually compare the performance. * * Wentworth Institute of Technology * COMP 3370 * Programming Assignment 2 *

* Javadoc example: * http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html#examples * Press: Shift+F2 to view the Javadocs * */

public class PA2 {

// TODO: document this method public static int[] countingSort(int[] a) { //TODO: implement this method int[] aux = new int[a.length]; int min = a[0]; int max = a[0]; for (int i = 1; i < a.length; i++) { if (a[i] < min) { min = a[i]; } else if (a[i] > max){ max = a[i]; } } int[] counts = new int[max - min + 1]; for (int i = 0; i < a.length; i++) { counts[a[i] - min]++; } counts[0]--; for (int i = 1; i < counts.length; i++) { counts[i] = counts[i] + counts[i - 1]; } for (int i = a.length - 1; i >= 0; i--) { aux[counts[a[i] - min]--] = a[i]; } return aux; }

// TODO: document this method public static int[] radixSort(int[] a) { // TODO: implement this method return null; }

/******************************************** * * You shouldn't modify anything past here * ********************************************/

public final static int MAX_INPUT = 524287; public final static int MIN_INPUT = 0;

/** * Implementation of insertionSort as given in week 1 lecture. * temp is the key * we step through the array and look for the proper place to insert the key * elements up to the key are assumed to be sorted. *

Steps: *

*
• Copy the key *
• Copy elements UP until we find where the key goes *
• We put [insert] the key *
• Repeat for j+1 *

*

* Java, C++ implementation reference: * http://www.algolist.net/Algorithms/Sorting/Insertion_sort *

* Expected Cost: O(n^2) * * @param a array to be sorted * @return sorted array */ public static int[] insertionSort(int[] a) {

for (int i = 1; i < a.length; i++) { int tmp = a[i]; int j; for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j]; a[j+1] = tmp; }

return a; }

/* Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, * Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data * sets that cause other quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. */ public static int[] systemSort(int[] a) { Arrays.sort(a); return a; }

// read ints from a Scanner // returns an array of the ints read private static int[] getInts(Scanner s) { ArrayList a = new ArrayList();

while (s.hasNextInt()) { int i = s.nextInt(); if ((i <= MAX_INPUT) && (i >= MIN_INPUT)) a.add(i); }

return toIntArray(a); }

// copies an ArrayList of Integer to an array of int private static int[] toIntArray(ArrayList a) { int[] ret = new int[a.size()]; for(int i = 0; i < ret.length; i++) ret[i] = a.get(i); return ret; }

public static void main(String[] args) { Scanner s = new Scanner(System.in);

System.out.printf("Enter the sorting algorithm to use ([c]ounting, [r]adix, [i]nsertion, or [s]ystem): "); char algo = s.next().charAt(0);

System.out.printf("Enter the integers that you would like sorted, followed by a non-integer character: "); int[] unsorted_values = getInts(s); int[] sorted_values = {};

s.close();

switch (algo) { case 'c': sorted_values = countingSort(unsorted_values); break; case 'r': sorted_values = radixSort(unsorted_values); break; case 'i': sorted_values = insertionSort(unsorted_values); break; case 's': sorted_values = systemSort(unsorted_values); break; default: System.out.println("Invalid sorting algorithm"); System.exit(0); break; }

System.out.println(Arrays.toString(sorted_values)); }

}