The Sorting Application
The examples in this document all part of the Java Application Sorting. Download the source archive Sorting.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details. Like others, the Sorting project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to rightclick the file and select Run File either in the file itself or from the listing in the Projects window. This document introduces two sorting algorithms: selectionSort and insertionSort.Sorting Algorithms
We also introduce the following classes which provide the code basis for the 6 sorting algorithms discussed in the notes:
selectionSort
insertionSort
shellSort
quickSort
mergeSort
heapSort
We use the following classes:
insertionSort
shellSort
quickSort
mergeSort
heapSort

These give access to the 6 implementations for the int type:

These give access to the 6 implementations for the generic types:

These give access to the 6 sorting algorithms, with all possible
arguments,
for the int primitive type and for generic types.
These versions call
the actual sorting functions within
sort.IntArray and sort.GenericArray.

Finally, these are the "show" algorithms for int type:
The ShowSorts demo program
This program, using the sorting algorithms from sort.ShowAlgorithms gives demonstrations of the sorting algorithms written:String choice = // choose one "select" // "insert" // "shell" // "quick" // "merge" // "heap" ; ... int size = 15; ... // choose the method of generating the array public static int[] getIntArray(int size) { Random r = new Random(); int[] A = new int[size]; for (int i = 0; i < A.length; ++i) { A[i] = 1 + r.nextInt(2 * size); //A[i] = 10; //A[i] = 10 + i; //A[i] = 2*NUM  i; } return A; }
Sorting Scenarios
When you analyze sorting algorithms, like any other algorithm, the three cases are of interest: best case
 worst case
 average case
 the array is already sorted
 the array is reverse sorted
 the elements in the array are all equal
Selection Sort
We start with this algorithm because it is probably the simplest one. The idea is this: choose the smallest element in the array and put it into the first position,
 of the remaining, choose the smallest and put it into the second position
 etc, etc.
for (int i = 0; i < n  1; ++i) { // set selected_index so that a[selected_index] // is smallest in a[i]..a[n1] int selected_index = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[selected_index]) { selected_index = j; } } if (selected_index != i) { // swap a[i] & a[selected_index] int tmp = a[selected_index]; a[selected_index] = a[i]; a[i] = tmp; } }
Arraybased sorting functions
Java treats sorting algorithms in two very different ways: Sorting primitive types. Java writes one algorithm in 7 different ways, one for each primitive type. Here stability is not an issue.
 Generic types. Here stability may matter. A single version of the algorithm can suffice.
Sorting generic (nonprimitive) types
There are 4 generic arraybased sort operations in Java:1. public static <E> void somethingSort( E[] a, int fromIndex, int toIndex, Comparator<? super E> c); 2. public static <E> void somethingSort(E[] a, Comparator<? super E> c); 3. public static void somethingSort(Object[] a, int fromIndex, int toIndex); 4. public static void somethingSort(Object[] a);The last 3 can be derived from the first:
2. public static <E> void somethingSort(E[] a, Comparator<? super E> c) { somethingSort(a, 0, a.length, c); } 3. public static void somethingSort(Object[] a, int fromIndex, int toIndex) { Comparator<Object> c = new Comparator<Object>() { @Override public int compare(Object lhs, Object rhs) { return ((Comparable)lhs).compareTo(rhs); } }; somethingSort(a, fromIndex, toIndex, c); } 4. public static void somethingSort(Object[] a) { somethingSort(a, 0, a.length); }In the case of selection sort, the primary generic sorting algorithm would be this:
public static <E> void selectionSort( E[] a, int from, int to, Comparator<? super E> c) { for (int i = from; i < to  1; ++i) { int selected_index = i; for (int j = i + 1; j < to; ++j) { if (c.compare(a[j], a[selected_index]) < 0) { selected_index = j; } } if (selected_index != i) { swap(a, selected_index, i); } } }
Listbased sorting functions
Recall Java's sort function for List classes:List L<SomeClass> = /* an ArrayList or LinkedList */; Collections.sort(L); Collections.sort(L, cmp);
public static <E extends Comparable<? super E>> void somethingSort(List<E> list); public static <E> void somethingSort(List<E> list, Comparator<? super E> c);
public static <E extends Comparable<? super E>> void somethingSort(List<E> list) { Comparator<E> c = new Comparator<E>() { @Override public int compare(E lhs, E rhs) { return lhs.compareTo(rhs); } }; somethingSort(list, c); }
Insertion Sort
The idea is like this: move the second element into the correct position in the 2element array
 move the third element into the correct position in the 3element array
 etc, etc.
for (int i = 1; i < n; ++i) { for (int j = i; j > 0; j) { if (a[j1] > a[j]) { // a[j1] > a[j] swap(a, j1, j); } else { // a[j1] <= a[j], and since the array up to j1 is sorted break; // we are done with this subarray } } }
 capturing the new element to be inserted
 then shifting up each position lower position, until the new element is greater than or equal to the previous, or there is no previous
 inserting the value into the last position.
for (int i = 1; i < n; ++i) { int insert_value = a[i]; // pull the ith value "out" int j; for (j = i; j > 0; j) { // j = "a first correct position" if (a[j1] > insert_value) { // a[j1] is bigger a[j] = a[j1]; // shift the value a[j1] up } else { break; } } if (j != i) { // if j is not the same as i a[j] = insert_value; // insert into the jth position }
public static <E> void insertionSort( E[] a, int from, int to, Comparator<? super E> c) { for (int i = from + 1; i < to; ++i) { E insert_value = a[i]; // pull the ith value "out" int j; for (j = i; j > from; j) { // j = "a first correct position" if (c.compare(a[j  1], insert_value) > 0) { // a[j1] is bigger a[j] = a[j  1]; // shift the value up } else { break; } } if (j != i) { // if j is not the same as i a[j] = insert_value; // insert into the jth position } } }
Analysis and Comparison
When we consider timing analysis of sorting algorithms both comparisons and data movements count. We also want to consider the behavior of an array which is already sorted or nearly sorted, which is usually the best case in these algorithms. For selection sort, the number of comparisons is always the same, regardless of the array input. The number is:(n1) + (n2) + ... + 1 = n*(n1)/2The number of data movements is at best, i.e., none,if the array is already sorted. The worst case is a reversesorted array in which case we must do a swap on each iteration. Counting a swap as 3 data movements we get a worst case of 3*(n1). For insertion sort, the number of comparisons and data movement may both vary. In the best case of a sorted array, there are n1 data movements (to save the insert element) and n1 comparisons. In the worst case of a reversesorted array there n*(n1)/2 comparisons and the same number of shifts, each counting for 1 data movement. A final table illustrates the analysis of the two algorithms:
best case (sorted) 
worst case (reverse sorted) 


comparisons  data movements  comparisons  data movements  
selection sort  n*(n1)/2  0  n*(n1)/2  3*(n1) 
insertion sort  n1  n1  n*(n1)/2  2*(n1) + n*(n1)/2 
Stability
Selectsort is not stable. We can see this in a simple example:[ 3, 3′, 2 ] ↠ [ 2, 3′, 3 ]The "2" exchanges with the first "3" making "3" elements change order from the original array. In contrast, insertion sort is stable. The element comparison is crucial for maintaining the stability:
if (c.compare(a[j–1], insert_value) > 0) { a[j] = a[j–1]; }If we were to change ">" to ">=", then equal elements would "slide" across each other and in the final array be reverseordered in the sorted output relative to the original array (this would also cause an unnecessary extra number of comparisons and data movements).
Inversions and Average time
In selection sort, the number of comparisons is always the same, n*(n–1)/2 ≈ n^{2}/2, thus the average time is quadratic. In insertion sort, we see that the time can vary between linear (best) and quadratic (worst). To show that the average time is quadratic we count the average number of swaps of adjacent elements — recall that insertion sort doesn't actually swap the elements. Consider all possible permutations of an array of n distinct elements. If you consider a single array with its reverse, the total number of inversions is exactly the number of element pairs, which is: n*(n–1)/2. Here's a math:total arrays = n! total array pairs (each with its reverse) = n!/2 total inversions per array pair = total pairs = n(n1)/2 total inversions over all arrays = n!/2 * n(n1)/2 = n! * n(n1)/4 average # inverions = total inversions / total arrays = (n! * n(n1)/4) / n! = n(n1)/4 = O(n^{2})Each swap in insertion sort removes one inversion, and a comparison is required to do so. Thus the average number of comparisons required in insertion sort is O(n^{2}). The preceding argument holds for any algorithm that sorts by swapping pairs of elements: it has a quadratic worstcase and averagecase time. In particular, if you know about bubble sort, it sorts also by swapping pairs of elements.
Move elements larger distances
The outcome is that a sorting algorithm can never get faster than quadratic time (on the average) if it only swaps adjacent elements. Consider, however, swapping elements which are farther away. Take this example:[9,8,7,6,5,5,4,3,2,1] this has 9*8/2 = 36 inversions swap the (9,1) pair [1,8,7,6,5,5,4,3,2,9] this has 7*6/2 = 21 inversionsThis one swap removed 15 inversions!
Bubble Sort
So how does bubble sort stack up against insertion sort: the answer is the insertion sort is the clear winner. Here are some excerpts from the Wikipedia article, http://en.wikipedia.org/wiki/Bubble_sortEven among simple O(n^{2}) sorting algorithms, algorithms like insertion sort are usually considerably more efficient [than bubble sort]. Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught. The Jargon file ... calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous book The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he then discusses.Despite this commentary, one thing you can say about bubble sort is that it is stable, like insertion sort.