Radix Sort in Java Goal: Fill in the the TODO area within the radixSort method t
ID: 3846736 • Letter: R
Question
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
* <p>
* 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.
* <p> Steps:
* <ul>
* <li> Copy the key
* <li> Copy elements UP until we find where the key goes
* <li> We put [insert] the key
* <li> Repeat for j+1
* </ul>
* <p>
* Java, C++ implementation reference:
* http://www.algolist.net/Algorithms/Sorting/Insertion_sort
* <p>
* 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<Integer> a = new ArrayList<Integer>();
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<Integer> 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));
}
}
Explanation / Answer
Edited your code and inserted radix sort algorithm
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
* <p>
* 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) {
int i, m = a[0], exp = 1, n = a.length;
int[] b = new int[10];
for (i = 1; i < n; i++)
if (a[i] > m)
m = a[i];
while (m / exp > 0)
{
int[] bucket = new int[10];
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
return a;
}
/********************************************
*
* 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.
* <p> Steps:
* <ul>
* <li> Copy the key
* <li> Copy elements UP until we find where the key goes
* <li> We put [insert] the key
* <li> Repeat for j+1
* </ul>
* <p>
* Java, C++ implementation reference:
* http://www.algolist.net/Algorithms/Sorting/Insertion_sort
* <p>
* 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<Integer> a = new ArrayList<Integer>();
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<Integer> 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));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.