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
Insertion Sort
Insertion sort has the same worst-case scenario efficiency as selection sort, but it has a much better best-case scenario efficiency.
Step 1: Nested loop with an inner loop traversing in reverse.
Still Step 1: The inner loop doesn't need to start at index[0]
[0]
Step 2: The inner loop goes backwards so long as the number that the outer loop has is bigger
Step 3: You'll have to move numbers over as you go to make room
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.
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.
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
This article is a great follow-up to the video below.
Let's start with some numbers to 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:
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.
Last updated