# Sorting Algorithms

A group of basic sorting algos. Based on Algorithms, 4th Edition - Robert Sedgewick | Kevine Wayne. Just making sure all of my logic and everything is correct.

/*
Sandbox for the various search algorithms from Section 2 of
<a href="http://algs4.cs.princeton.edu/home/">Algorithms, 4th Edition - Robert Sedgewick | Kevine Wayne</a>
*/

import java.util.Arrays;

public class Sorts {

/********************
Sorting Algorithms
********************/

/*Selection Sort

Sorts a passed array of any Comparable object by ascending order.Uses the Selection Sort method. For each iteration i we place the ith smallest item in array[i]*/
public static void selectionSort(Comparable[] toSort) {
int N = toSort.length;
int min; //Index of the minimal element during each run

for (int i=0; i < N; i++) {
min = i;
for(int j = i+1; j < N; j++) {
if(less(toSort[j], toSort[min])) {
min = j;
}
}
swap(toSort, i, min);
}
}

/*Insertion Sort

Sorts a passed array of any Comparable object by ascending order. Uses the Insertion Sort method.  For each iterarion, i, swap array[i] with entries array[<i] that are larger.*/
public static void insertionSort(Comparable[] toSort, int start, int end) {
for (int i=start; i <= end; i++) {
for(int j = i; j > start && less(toSort[j], toSort[j-1]); j--) {
swap(toSort, j, j-1);
}
}
}

/*Shell Sort

Sorts a passed array of any Comparable object by ascending order. Uses the Shell Sort method, which is essentially a modified Insertion Short. Rather then decrementing by 1, we decrement by decreasing values of h, breaking the array into smaller and smaller already sorted sub-arrays. Increased performance on larger arrays, especially when there are very small values at the end of the array*/
public static void shellSort(Comparable[] toSort) {
int N = toSort.length;
int h = 1;

while (h < N/3) {  //Computes the max h-size array
h = h*3 + 1;  //1,4,13,40,121.....
}

while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(toSort[j], toSort[j-h]); j-=h) {
swap(toSort, j, j-h);
}
}
h = h/3;  //Shrinks to the next h-array size
}
}

/*Merge Sort

Sorts a passed array of any Comparable object by ascending order.  Uses the Merge Sort method.  Recursively breaks the array into 1/2 sized sub arrays, then merges them in sorted order as the stack unwinds.

Uses Insertion sort when it gets to a certain threshold for small arrays*/
public static void mergeSort(Comparable[] toSort) {
Comparable[] tempArray = new Comparable[toSort.length];
mergeSort(toSort, tempArray, 0, toSort.length-1);
}

public static void mergeSort(Comparable[] toSort, Comparable[] tempArray, int low, int high) {  //Recursively splits the array in half and then merges in proper order
//Cutoff to just Insertion Sort for smaller arrays
if (high<=low + 15) {
insertionSort(toSort, low, high);
return;
}

int mid = low + (high - low)/2;  //Create the mid point

mergeSort(toSort, tempArray, low, mid);  //Sort left half
mergeSort(toSort, tempArray, mid+1, high); //Sort right half

if(greater(toSort[mid],toSort[mid+1])) {  //Skips the merge if everything in the left is smaller then everything in the right
mergeArrays(toSort, tempArray, low, mid, high);  //Merge results
}

}

//Merges two sorted sub arrays into one larger sorted array
public static void mergeArrays(Comparable[] toSort, Comparable[] tempArray, int low, int mid, int high){
int i = low;
int j = mid+1;

for (int k = low; k <= high; k++) {  //Copy values into temporary array
tempArray[k] = toSort[k];
}

for (int k = low; k <= high; k++) {  //Copy values back in sorted order
if (i > mid) {  //No more left items
toSort[k] = tempArray[j++];
}
else if (j > high) { //No more right items
toSort[k] = tempArray[i++];
}
else if (less(tempArray[j], tempArray[i])) {  //If the item on the right is smaller
toSort[k] = tempArray[j++];
}
else {  //If the item on the left is smaller
toSort[k] = tempArray[i++];
}
}
}

/*Quick Sort

Sorts passed array of any Comparable object by ascending order. Uses the Quick Sort method. Recursively places an element in index array[v], known as the partition into it's proper place so that every element array[<v] is < array[v] and every element array[>v] is > array[v]*/
public static void quickSort(Comparable[] toSort)  {
//StdRandom.shuffle(toSort);   Unusued because in my current implementation the array starts off already random
quickSort(toSort, 0, toSort.length - 1);
}

public static void quickSort(Comparable[] toSort, int low, int high) {
//Cutoff to just Insertion Sort for smaller arrays
if (high<=low + 15) {
insertionSort(toSort, low, high);
return;
}

int j = quickPartition(toSort, low, high);
quickSort(toSort, low, j-1);  //Sorts to the left of partition
quickSort(toSort, j+1, high);  //Sorts to the right od partition
}

/*Places the partition item in it's proper place.  Iterates through each element from both ends and swaps any elements on the right side that are < array[low] with any elements on the left side that are > array[low]. Returns the index, j, of the item that is now in it's proper place*/
private static int quickPartition(Comparable[] toSort, int low, int high) {
int i = low;
int j = high+1;
Comparable v = toSort[low];

while(true) {
while(less(toSort[++i],v)) {  //Scan left side until you find an item that's greater then v
if(i==high) {  //Reached end of array
break;
}
}

while(less(v, toSort[--j])) { //Scan right side until you find an item that's greater then v
if(j==low) {
break;
}
}
if(i>=j) {  //If the right side and left side poointers cross, entire array has been searched
break;
}
swap(toSort, i, j);  //Swaps the two out of place elements
}

swap(toSort, low, j);  //Puts partition item into proper place
return j;  //Returns position of now correct item
}

/********************
Helper methods
********************/
private static boolean less(Comparable x, Comparable y) {
return x.compareTo(y) < 0;
}

private static boolean equals(Comparable x, Comparable y) {
return x.compareTo(y) == 0;
}

private static boolean greater(Comparable x, Comparable y) {
return x.compareTo(y) > 0;
}

private static void swap(Comparable[] items, int x, int y){
Comparable temp = items[x];
items[x] = items[y];
items[y] = temp;
}

private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
if (less(a[i], a[i-1])) {
return false;
}
}
return true;
}

public static void main(String[] args) {
//      int length = Integer.parseInt(args[0]);  //Passing in the length of the random array to be created
//      int range = length;

StdOut.println("Length of array to be generated");

StdOut.println("Range random values");

int[] masterArray =  new int[length];
for (int i = 0; i < length; i++) {
masterArray[i] = StdRandom.uniform(range);
}

StdOut.println();
StdOut.println();

//Will display the array if it's reasonably short
if(length <= 20) {
StdOut.println("Master Array");
for(int i=0; i < length; i++) {
StdOut.print(masterArray[i] + " ");
}
StdOut.println();
StdOut.println();
}

//Selection Sort
StdOut.println("Selection Sort");

Integer[] selectionArray = new Integer[length];
arrayCopy(masterArray, selectionArray);
Stopwatch t1 = new Stopwatch();

selectionSort(selectionArray);

if (isSorted(selectionArray)){
StdOut.println("Successful, running time: " + t1.elapsedTime());
}
StdOut.println();

//Insertion Sort
StdOut.println("Insertion Sort");

Integer[] insertionArray = new Integer[length];
arrayCopy(masterArray, insertionArray);
Stopwatch t2 = new Stopwatch();

insertionSort(insertionArray, 0, length-1);

if (isSorted(insertionArray)){
StdOut.println("Successful, running time: " + t2.elapsedTime());
}
StdOut.println();

//Shell Sort
StdOut.println("Shell Sort");

Integer[] shellArray = new Integer[length];
arrayCopy(masterArray, shellArray);
Stopwatch t3 = new Stopwatch();

shellSort(shellArray);

if (isSorted(shellArray)){
StdOut.println("Successful, running time: " + t3.elapsedTime());
}
StdOut.println();

//Merge Sort
StdOut.println("Merge Sort");

Integer[] mergeArray = new Integer[length];
arrayCopy(masterArray, mergeArray);
Stopwatch t4 = new Stopwatch();

mergeSort(mergeArray);

if (isSorted(mergeArray)){
StdOut.println("Successful, running time: " + t4.elapsedTime());
}
StdOut.println();

//Quick Sort
StdOut.println("Quick Sort");

Integer[] quickArray = new Integer[length];
arrayCopy(masterArray, quickArray);
Stopwatch t5 = new Stopwatch();

quickSort(quickArray);

if (isSorted(quickArray)){
StdOut.println("Successful, running time: " + t5.elapsedTime());
}
StdOut.println();
}

public static void arrayCopy(int[] a, Integer[] b) {
for(int i = 0; i < a.length; i++) {
b[i] = a[i];
}
}
}


Good job in general. Just few comments.

• All the algorithms are implemented on arrays. It is really an overkill; you don't need a random access to sort a collection.

• I am not sure you need to spell out less, equals or greater. Isn't it what Comparable is for?

• I am not sure that isSorted(Comparable[] a, int lo, int hi) needs to exist at all. It doesn't hurt to have it though.

• mergeArrays()

A naked loop usually represents an important algorithm. In this case a for (int k = low; k <= high; k++) loop is even attributed with comment; definitely it is copy(), which deserves a method of its own.

Once a i > mid condition is encountered, there is no point to test it over and over again: break the main loop right away and let a copy() method do the rest. Same goes for j > high.

• quickPartition()

Unnecessary comments sometimes create very hard to understand problems. It took me a while to realize that greater at line 153 is an unfortunate copy-paste. Yet another reason to convert a naked loop into a method.

• insertionSort()

Same naked loop problem. An inner loop is identical to one of the quickPartition's loops.

• selectionSort()

See an insertionSort comment.

• shellSort()

Did I mention naked loops?

• main()

Do something with all those Stopwatches! You already provided arrayCopy - why not use it? The Java experts will comment on Java specifics (final especially).

• I'll admit that spelling out the 'less', 'equals' and 'greater' function did seem redundant. But that's how it's done in the textbook (well the less function at least, I just added the others for good measure). Like I said, it did seem redundant to me, but I assumed the two PhDs who wrote the book had a good reason and went with it. Here is from the textbook companions website. Any insite as to why would be appreciated. algs4.cs.princeton.edu/22mergesort/Merge.java.html Commented Aug 14, 2014 at 20:56
• The only justification for less I can see is if it was a free-standing function, akin to std::less STL template. Here is not the case, since Java doesn't allow free-standing templates, and an interface is cast in concrete to Comparable. I don't know why Segdewick decided to go this way. BTW, they missed factoring out copy and find methods - and I also insist it is wrong. Very few textbooks are error free.
– vnp
Commented Aug 14, 2014 at 22:23

## Java Doc

Java has a documentation standard for documenting members, classes and methods called "JavaDoc" most editors support this documentation and allow you to auto-generate stubs which you can just fill in. It is highly advised that you stick to this standard instead of ad-hoc formatted comments.

## Unit Tests

You really should convert your main method to be a suite of unit tests. There are many unit testing libraries out there but in my opinion the most common one is JUnit which is integrated in eclipse and probably other editors as well.

• This is based on an Algorithms Coursera class and related textbook. It's not really a 'Java' class in of itself. So we haven't covered anything like JavaDocs yet. I am coming from a C++ background, this is my first time really working with Java (not that it's that much of a leap). Commented Aug 14, 2014 at 20:49
• Welcome to the blessed land of easy-to-develop Java! For first timers, I really do recommend installing and using the Eclipse IDE it offers fantastic support for developing with Java and it is free as in speech and beer. I wouldn't trust an algorithms book to have good code (I trust algorithms are correct OTOH). I really do recommend learning JavaDoc though, just hit ALT+SHIFT+J after putting the carret on whatever you want to document in Eclipse to get a stub to fill in and presto! Commented Aug 15, 2014 at 7:36

Comparable is a raw type, whose use has been discouraged since the introduction of Generics with Java 1.5. You should specify type the object is comparable to, using a type variable as in Comparable<T>.

Concretely, that means that a method signature like

public static selectionSort(Comparable[] toSort)


public static <T extends Comparable<? super T>> void selectionSort(T[] toSort)


The swap() method

private static void swap(Comparable[] items, int x, int y){
Comparable temp = items[x];
items[x] = items[y];
items[y] = temp;
}


should be written as

private static <T extends Comparable<? super T>> void swap(T[] items, int x, int y){
T temp = items[x];
items[x] = items[y];
items[y] = temp;
}


One particularly tricky problem is with mergesort, which involves allocating a new array. Due to type erasure, Java can't tell what type of array to create. The workaround is a bit ugly:

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] toSort) {
Comparable[] tempArray = new Comparable[toSort.length];
mergeSort(toSort, (T[])tempArray, 0, toSort.length-1);
}


Here is your class, with just a conversion to use Generics properly, and no other changes. main() has been omitted.

import java.util.Arrays;

public class Sorts {

/********************
Sorting Algorithms
********************/

/*Selection Sort

Sorts a passed array of any Comparable object by ascending order.Uses the Selection Sort method. For each iteration i we place the ith smallest item in array[i]*/
public static <T extends Comparable<? super T>> void selectionSort(T[] toSort) {
int N = toSort.length;
int min; //Index of the minimal element during each run

for (int i=0; i < N; i++) {
min = i;
for(int j = i+1; j < N; j++) {
if(less(toSort[j], toSort[min])) {
min = j;
}
}
swap(toSort, i, min);
}
}

/*Insertion Sort

Sorts a passed array of any Comparable object by ascending order. Uses the Insertion Sort method.  For each iterarion, i, swap array[i] with entries array[<i] that are larger.*/
public static <T extends Comparable<? super T>> void insertionSort(T[] toSort, int start, int end) {
for (int i=start; i <= end; i++) {
for(int j = i; j > start && less(toSort[j], toSort[j-1]); j--) {
swap(toSort, j, j-1);
}
}
}

/*Shell Sort

Sorts a passed array of any Comparable object by ascending order. Uses the Shell Sort method, which is essentially a modified Insertion Short. Rather then decrementing by 1, we decrement by decreasing values of h, breaking the array into smaller and smaller already sorted sub-arrays. Increased performance on larger arrays, especially when there are very small values at the end of the array*/
public static <T extends Comparable<? super T>> void shellSort(T[] toSort) {
int N = toSort.length;
int h = 1;

while (h < N/3) {  //Computes the max h-size array
h = h*3 + 1;  //1,4,13,40,121.....
}

while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(toSort[j], toSort[j-h]); j-=h) {
swap(toSort, j, j-h);
}
}
h = h/3;  //Shrinks to the next h-array size
}
}

/*Merge Sort

Sorts a passed array of any Comparable object by ascending order.  Uses the Merge Sort method.  Recursively breaks the array into 1/2 sized sub arrays, then merges them in sorted order as the stack unwinds.

Uses Insertion sort when it gets to a certain threshold for small arrays*/

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] toSort) {
Comparable[] tempArray = new Comparable[toSort.length];
mergeSort(toSort, (T[])tempArray, 0, toSort.length-1);
}

public static <T extends Comparable<? super T>> void mergeSort(T[] toSort, T[] tempArray, int low, int high) {  //Recursively splits the array in half and then merges in proper order
//Cutoff to just Insertion Sort for smaller arrays
if (high<=low + 15) {
insertionSort(toSort, low, high);
return;
}

int mid = low + (high - low)/2;  //Create the mid point

mergeSort(toSort, tempArray, low, mid);  //Sort left half
mergeSort(toSort, tempArray, mid+1, high); //Sort right half

if(greater(toSort[mid],toSort[mid+1])) {  //Skips the merge if everything in the left is smaller then everything in the right
mergeArrays(toSort, tempArray, low, mid, high);  //Merge results
}

}

//Merges two sorted sub arrays into one larger sorted array
public static <T extends Comparable<? super T>> void mergeArrays(T[] toSort, T[] tempArray, int low, int mid, int high){
int i = low;
int j = mid+1;

for (int k = low; k <= high; k++) {  //Copy values into temporary array
tempArray[k] = toSort[k];
}

for (int k = low; k <= high; k++) {  //Copy values back in sorted order
if (i > mid) {  //No more left items
toSort[k] = tempArray[j++];
}
else if (j > high) { //No more right items
toSort[k] = tempArray[i++];
}
else if (less(tempArray[j], tempArray[i])) {  //If the item on the right is smaller
toSort[k] = tempArray[j++];
}
else {  //If the item on the left is smaller
toSort[k] = tempArray[i++];
}
}
}

/*Quick Sort

Sorts passed array of any Comparable object by ascending order. Uses the Quick Sort method. Recursively places an element in index array[v], known as the partition into it's proper place so that every element array[<v] is < array[v] and every element array[>v] is > array[v]*/
public static <T extends Comparable<? super T>> void quickSort(T[] toSort)  {
//StdRandom.shuffle(toSort);   Unusued because in my current implementation the array starts off already random
quickSort(toSort, 0, toSort.length - 1);
}

public static <T extends Comparable<? super T>> void quickSort(T[] toSort, int low, int high) {
//Cutoff to just Insertion Sort for smaller arrays
if (high<=low + 15) {
insertionSort(toSort, low, high);
return;
}

int j = quickPartition(toSort, low, high);
quickSort(toSort, low, j-1);  //Sorts to the left of partition
quickSort(toSort, j+1, high);  //Sorts to the right od partition
}

/*Places the partition item in it's proper place.  Iterates through each element from both ends and swaps any elements on the right side that are < array[low] with any elements on the left side that are > array[low]. Returns the index, j, of the item that is now in it's proper place*/
private static <T extends Comparable<? super T>> int quickPartition(T[] toSort, int low, int high) {
int i = low;
int j = high+1;
T v = toSort[low];

while(true) {
while(less(toSort[++i],v)) {  //Scan left side until you find an item that's greater then v
if(i==high) {  //Reached end of array
break;
}
}

while(less(v, toSort[--j])) { //Scan right side until you find an item that's greater then v
if(j==low) {
break;
}
}
if(i>=j) {  //If the right side and left side poointers cross, entire array has been searched
break;
}
swap(toSort, i, j);  //Swaps the two out of place elements
}

swap(toSort, low, j);  //Puts partition item into proper place
return j;  //Returns position of now correct item
}

/********************
Helper methods
********************/
private static <T extends Comparable<? super T>> boolean less(T x, T y) {
return x.compareTo(y) < 0;
}

private static <T extends Comparable<? super T>> boolean equals(T x, T y) {
return x.compareTo(y) == 0;
}

private static <T extends Comparable<? super T>> boolean greater(T x, T y) {
return x.compareTo(y) > 0;
}

private static <T extends Comparable<? super T>> void swap(T[] items, int x, int y){
T temp = items[x];
items[x] = items[y];
items[y] = temp;
}

private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
return isSorted(a, 0, a.length - 1);
}

private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
if (less(a[i], a[i-1])) {
return false;
}
}
return true;
}

public static void main(String[] args) {
…
}
}

• What are the advantages of using generics in this way as opposed to just 'Comparable[]'? The textbook only uses 'Comparable[]', I would assume the two PhDs who wrote it had their reasons, though it could be just because it's an Algorithms textbook, not a Java Syntax textbook, and therefore wasn't meant to focus on super specific/particular/tricky Java syntax. algs4.cs.princeton.edu/22mergesort/Merge.java.html Commented Aug 14, 2014 at 20:59
• It's for type safety. A lot of objects may be comparable, but not to each other. For example, a String can be compared to another String, and an Integer can be compared to another Integer, but it does not make sense to compare a String to an Integer. Therefore, the code above is now standard practice, and the code in the question will generate a compiler warning. Commented Aug 14, 2014 at 21:29
• The syntax does get in the way of learning the algorithms, though, so I'm not surprised that an algorithms book chose to be sloppy about types. Commented Aug 14, 2014 at 21:31

Great job! This is a pretty well-written program that implements the algorithms to a T, and you even made sure to avoid integer overflow in your mean calculation! Now let's get down to everything you could do differently:

You use them too much. Consider this line:

    int min; //Index of the minimal element during each run


Variable names should explain themselves and code comments should generally be reserved for tricky logic. min is probably fine; if you want to be absolutely clear, you might change it to indexOfMin. Also, you don't need to declare it before the loop. If it gets re-assigned every time through the outer loop, then declare it in the outer loop. This way it's obvious the effects don't pass through loop iterations.

In

else if (less(tempArray[j], tempArray[i])) {  //If the item on the right is smaller


your method name should make it clear what it does, and the comment is unnecessary. Also, traditionally Java methods returning booleans are of the form 'isAdjective', so this code would turn into

else if (isLess(tempArray[j], tempArray[i])) {


I think it's more clear, though, to stick to what's already defined for us:

else if (tempArray[j].compareTo(tempArray[i]) < 0) {


This makes it clear to me that the thing on the left is less than the thing on the right, though I could potentially see it both ways.

public static void mergeSort(Comparable[] toSort, Comparable[] tempArray, int low, int high) {  //Recursively splits the array in half and then merges in proper order


Not only does this comment make the line way too long, it should probably be a JavaDoc, not a comment.

## Naming

int N = toSort.length;


Speaking of naming, this line is a big no-no. I forget if Algorithms uses this or not, but names starting with an uppercase letter are always reserved for classes. Also, N is a bit vague. I would do

int length = toSort.length;


## Declarations

public static void insertionSort(Comparable[] toSort, int start, int end) {


I understand you use this later in mergeSort, but your public-facing API should be consistent, and this isn't. Instead, have something like

public static void insertionSort(Comparable[] toSort) {
insertionSort(toSort, 0, toSort.length);
}

private static void insertionSort(Comparable[] toSort, int start, int end) {
...


This way your merge sort can still call it, but end-users who want insertion sort don't have to provide start and end points. Alternately, you could decide to add start and end parameters to every method, in case people only want to sort a subset of the array. In this case, still provide public methods without these extra parameters. The same goes for quickSort.

public static void mergeSort(Comparable[] toSort, Comparable[] tempArray, int low, int high)
public static void mergeArrays(Comparable[] toSort, Comparable[] tempArray, int low, int mid, int high)


On a related note, neither of these be public. End users don't really have anything to gain from these methods, so they should be marked private.

## Spacing

for (int i=0; i < N; i++) {
min = i;
for(int j = i+1; j < N; j++) {
if(less(toSort[j], toSort[min])) {
min = j;
}
}
swap(toSort, i, min);
}


You should keep a consistent style. If you put a space between for and (, always put a space between for and (.

if (high<=low + 15) {


Spaces should be generally used to group terms together by precedence. + is evaluated before <=, so this could be high <= low+15. If you like lots of space, you could use high <= low + 15. If you don't like space, you could use high<=low+15. However, in my opinion this snippet is actually misleading. You're not trying to show that high is at least 15 more than low, you're trying to show that the difference between 'high' and 'low' is less than 15. Others might disagree, but I would always write 'high-low <= 15'.

## Other

private static boolean equals(Comparable x, Comparable y) {
return x.compareTo(y) == 0;
}


Aside from using compareTo directly in your methods, this method has no reason to exist. It's simply not used. However, you're right to not use the builtin equals in this case: the contract does not require that the comparison be consistent with equals.

Others have made wonderful points, and I particularly urge the use of generics - integers are comparable, and strings are comparable, but you can't really compare integers to strings. I also agree with the use of JavaDocs and unit tests.

• Hey! Thanks for the feedback! The copious amounts of comments are from the fact that this programs serves as my 'notes' from the reading. So it's more intended for something I would go back and read over later, as opposed to something that I would release to the public. So from that logic the more comments the better as I am re-reading it later. Yes N is what Algorithms uses. Don't know why. Commented Aug 14, 2014 at 20:47
• Ah, then I can understand the comments. I haven't picked up Algorithms in a while, but I seem to remember it had an unusual understanding of Java style, to put it delicately Commented Aug 14, 2014 at 20:57
• I get that feeling too (about the Java). Probably because it's an Algorithms book, not a Java Syntax book, so it uses the simplest conventions it can to be more understandable to people coming from other programming languages. That's my rough theory at least. Commented Aug 14, 2014 at 21:01