# 8: Sorting

We will write our most complex algorithms as we study efficient ways to sort collections of data. Some of these algorithms will require recursion, our most abstract and challenging topic to date.

# Learning Targets

• I can implement selection, insertion and merge sort algorithms.

• I can compare sorting algorithms' efficiency.

# Algorithms

We've talked about algorithms before, most especially around the shuffling patterns we've used in the Elevens lab.

## Efficiency

The bigger the group of data, the more important it is to be efficient. Searching on the web or in a database needs to be awfully fast. We measure the efficiency of a complex search or sort algorithm in Big O notation.

## Searching

Let's knock out a quick algorithm first, searching. The `O(n)` way is just a straight traversal. But we could chop that down to a `O(log n)` with a binary search:

The visualization of these patterns / algorithms / methods / whatever, is surprisingly helpful. You can get a feel for how we chunk the computer's task to organize a long list of numbers.

## Selection Sort

Let's start with a nested loop, a boring old `O(n^2)` traversal and sort.

Now between the inner and otter loops, we do a 3-part-swap

`public static void selectionSort ( int[] num ){		int i, j, temp;       		for ( i = 0; i < num.length - 1; i++ ){      					//initialize the smallest_index    				smallest_index = i;        						//inner loop locate smallest 				for(j = i + 1; j < num.length; j++) {						if( num[ j ] < num[ smallest_index ] )								smallest_index = j;    						}       					// 3 part swap between loops   				temp = num[ smallest_index ];         					num[ smallest_index ] = num[ i ];     						num[ i ] = temp;    		} // close the otter loop          } // close the method​`

## Insertion Sort

Insertion sort has the same worst-case scenario efficiency as selection sort, but it has a much better best-case scenario efficiency. This animation depends on an insert option to move over the other numbers

## Assignment

Create a class that uses `Sortable` and `IntegerMonster`. Hopefully, that and the code below is enough for you to figure out what to do next. If not, let's make some extra time to practice/read about inheritance in Java.

You'll have to use `extends` before `implements`. Potentially helpful analogy: I imagine "extends" as the class's last name and "implements" as job titles.

Sortable.java
IntegerMonster.java
Sortable.java
`interface Sortable {    void selectionSort(boolean lowToHigh);        void insertionSort(boolean lowToHigh);    }`
IntegerMonster.java
`abstract class IntegerMonster {​  public int[] nums;    public IntegerMonster(int length){    nums = new int[length];  }    public void buildRandomArray(){    for(int i = 0; i < nums.length; i++){      nums[i] = (int)(Math.random() * 5000);    }  }    public abstract void printArray();  }`

Surprise: Your client suddenly changes the SoW and insists that the sort methods' outer loops print the current state of the array neatly on one line. Each array during the sort should be labeled.

# Recursion

What happens if I call a function that calls itself? You can use this as a trick to chunk information in a loop-like flow.

`public void recursive(){    System.out.println("It was a dark and stormy night.");    recursive();}` To avoid an infinite repeat, we've got to include a base case

A base case is the critical piece of a recursive function that will terminate the recursive calls, and start the domino effect in the opposite direction.

If we have a base case in place (rhymes!) we can use recursion to solve some tricky problems in an elegant fashion.

## Merge Sort

Check if `nums` has hit its base case. Is it already split up? If not, split it up.

Then we send each side to mergeSort. Notice we send the left side first. And the next copy of `mergeSort` will break that side up first too--all the way down to the base case.

But down at that last level, when they can't be broken down any further, we'll be left with a few useful ingredients, the (yellow) `nums`, the left side, `l`, and the right side, `r`. Now we'll shove `l` and `r` back together, in order, and overwrite the contents of `nums`. We'll do this in a separate function: `merge(nums, l, r, mid, n - mid);`

There are all sorts of variations on mergeSort and the merge function. The one from Baeldung is pretty clever and fun to talk over. Check it out:

`public static void merge(  int[] a, int[] l, int[] r, int left, int right) {      int i = 0, j = 0, k = 0;    while (i < left && j < right) {        if (l[i] <= r[j]) {            a[k++] = l[i++];        }        else {            a[k++] = r[j++];        }    }    while (i < left) {        a[k++] = l[i++];    }    while (j < right) {        a[k++] = r[j++];    }}`

First notice how they include the post-operation increment, `k++` (instead of `++k`). This way, every time `k` is used, it increases the index tracker on the parent array. It's a clever touch. Meanwhile, `i` is serving similarly as the index tracker for the left side and `j` is serving the right side.

The first while loop proceeds until one of the counters hits their max. Then only one of the two remaining while loops will execute, collecting the last number.

## Assignment

Create a class that extends `NameManager` and implements all required methods.

`abstract class NameManager {    /** Core data structure to hold your name list */    protected ArrayList<String> names;​    /** Adds names to the list until a blank is submitted */    abstract void buildList();        /** Uses selection shuffle algorithm */    abstract void shuffle();        /** Sorts the list of names using insertion sort */    abstract void insertionSort();        /** Sorts the list of names using selection sort */    abstract void selectionSort();        /** Sorts the list of names using merge sort */    abstract void mergeSort();        /** Returns a random name from the names list */    abstract String pickRandom();}`