Work in pairs or groups of 3 on this lab.
public class SortingMethods {
/**
* The method sorts an array using insertion sort
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
*/
public static <T extends Comparable<T>> void insertionSort(T [] arr) {
for (int i = 1; i < arr.length; ++i) {
// loop invariant: arr[0..i-1] is sorted
// the item to be inserted into the proper
// position in the sorted portion of the array
T nextItem = arr[i];
// iterating through the sorted portion backward
int j = i;
while (j > 0 && arr[j-1].compareTo(nextItem) > 0){
// loop invariant: nextItem is smaller than
// elements to the left of it
//shift arr[j-1] to the right
arr[j] = arr[j-1];
j--;
}
// insert the new item into its position
arr[j] = nextItem;
}
}
/**
* The method sorts an array using merge sort. The method is recursive.
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
*/
public static <T extends Comparable<T>> void mergeSort(T [] arr) {
if (arr.length > 1) {
// split the array into two halves
int length1 = arr.length/2;
int length2 = arr.length - arr.length/2;
// create the arrays:
T[] half1 = (T[]) new Comparable[length1];
T[] half2 = (T[]) new Comparable[length2];
// copy the corresponding portions of the array into new arrays
for(int i = 0; i<length1; i++) {
half1[i] = arr[i];
}
for(int i = length1; i < arr.length; i++) {
half2[i - length1] = arr[i];
}
// fill in the rest of your code here
}
}
}
import java.util.Random;
public class TestSorting {
public static void main(String [] args) {
// the array must be of Integer, not int,
// otherwise it's not recognized as Comparable
System.out.println("======== Testing random array generating ==========");
Integer [] toSort = randomInts(1, 101, 20);
printIntArray(toSort);
System.out.println(isSorted(toSort));
System.out.println("======== Testing insertion sort ==========");
// small-scale test: print elements
toSort = randomInts(1,101, 10);
System.out.println("Before sorting: ");
printIntArray(toSort);
System.out.println("After sorting: ");
SortingMethods.insertionSort(toSort);
printIntArray(toSort);
// larger-scale test: run on several arrays and check if they
// are sorted
boolean allSorted = true;
for (int i = 0; i < 5; ++i) {
toSort = randomInts(1, 101, 20 * (i + 1));
SortingMethods.insertionSort(toSort);
boolean isSorted = isSorted(toSort);
allSorted = allSorted && isSorted;
System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
if (!isSorted) {
System.out.println("This array was not sorted properly:");
printIntArray(toSort);
}
}
if (allSorted) {
System.out.println("Congratulations! Your insertion sort is working!");
} else {
System.out.println("There are problems with your insertion sort");
}
System.out.println("======== Testing merge sort ==========");
toSort = randomInts(1,101, 11);
System.out.println("Before sorting: ");
printIntArray(toSort);
System.out.println("After sorting: ");
SortingMethods.mergeSort(toSort);
printIntArray(toSort);
allSorted = true;
for (int i = 0; i < 5; ++i) {
toSort = randomInts(1, 101, 20 * (i + 1));
SortingMethods.mergeSort(toSort);
boolean isSorted = isSorted(toSort);
allSorted = allSorted && isSorted;
System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
if (!isSorted) {
System.out.println("This array was not sorted properly:");
printIntArray(toSort);
}
}
if (allSorted) {
System.out.println("Congratulations! Your merge sort is working!");
} else {
System.out.println("There are problems with your merge sort");
}
}
/**
* Generates an array of random Integers in the range from
* min (inclusive) to max (exclusive). The number of elements
* is given by num.
* @param min - the minimum value (inclusive)
* @param max - the maximum value (exclusive)
* @param num - the number of elements in the array
* @return - the array of num random Integers between min and max
* @throws IllegalArgumentException if min >= max or num < 0
*/
public static Integer [] randomInts(int min, int max, int num) {
if (min >= max || num < 0) {
throw new IllegalArgumentException();
}
Integer [] theInts = new Integer[num];
Random rand = new Random();
for (int i = 0; i < num; ++i){
theInts[i] = rand.nextInt(max - min) + min;
}
return theInts;
}
/**
* Checks if the parameter array is sorted
* @param <T> - the type of the elements in the array. Must
* extend Comparable<T>
* An array is sorted if for every two consecutive elements
* arr[i].compareTo(arr[i+1]) <= 0
* @param arr - the given array
* @return true if the given array is sorted, false otherwise
*/
public static <T extends Comparable<T>> boolean isSorted(T [] arr) {
for (int i = 0; i < arr.length - 1; ++i) {
if (arr[i].compareTo(arr[i+1]) > 0 ) {
return false;
}
}
return true;
}
/**
*
* The method prints its argument <code>arr</code>
* element by element on one line, separated by commas,
* with [ before the first element and ] after the last one
* @param arr - an array of type Integer
*/
public static void printIntArray(Integer [] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i]);
if (i != arr.length - 1)
System.out.print(", ");
}
System.out.println("]");
}
}
import static org.junit.Assert.assertArrayEquals;
import org.junit.Before;
import org.junit.Test;
public class UnitTestingSorting {
String [] strings = {"cherry", "kiwi", "pear", "apple", "avocado", "tomato"};
String [] sortedStr = {"apple", "avocado", "cherry", "kiwi", "pear", "tomato"};
Integer [] numbers = {7, 0, 5, 4, 4, 2, 1, 9, 2, 3, 7, 6, 5};
Integer [] sortedNumbers = {0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 9};
@Test
public void insertionSortStrings() {
SortingMethods.insertionSort(strings);
assertArrayEquals(sortedStr, strings);
}
@Test
public void insertionSortIntegers() {
SortingMethods.insertionSort(numbers);
assertArrayEquals(sortedNumbers, numbers);
}
}
Send me your code. CC your partner if you worked in a pair.