Methods in this group of examples assume that the type to be sorted
implements Comparable interface. Sorting Comprable
objects by their compareTo method is refered to as "sorting
accoring to their natural ordering".
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];
}
mergeSort(half1);
mergeSort(half2);
int index1 = 0;
int index2 = 0;
int index3 = 0;
while(index1 < half1.length && index2 < half2.length){
if(half1[index1].compareTo(half2[index2]) <= 0){
arr[index3] = half1[index1];
index1++;
index3++;
}
else{
arr[index3] = half2[index2];
index2++;
index3++;
}
}
while(index1 < half1.length) {
arr[index3] = half1[index1];
index1++;
index3++;
}
while(index2 < half2.length) {
arr[index3] = half2[index2];
index2++;
index3++;
}
}
}
}
Testing sorting methods
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("]");
}
}