Nice work building your own
insertionSort() function. An important point to remember about insertion sort is that the algorithm breaks our input array into two virtual lists. A sorted sub-list initially containing the first element in the array and an unsorted sub-list initially containing the remainder of the items in the input array.
Let’s walk through what we actually coded.
insertionSort() method, we have a for loop that runs left to right, running the insertion logic until the array is fully sorted. Inside the outer
for loop, we have a
while loop that iterates right to left through the sorted sub-list and checks whether the previous element(s) are greater than current element. If they are, we shift them one place to the right and insert our current element. The outer loop stops running after we have reached our last element in our array.
The nested-loop structure of the algorithm makes the worst case runtime
O(n^2). In the case of an already sorted array, insertion sort is able to cut out some of the work. We ultimately wind up with linear time of
O(n) in the best-case scenario.
Here we have our finished code from the last exercise. Go ahead and run the code again to see the results! Below you’ll find some more challenges:
- Try changing the data provided to the input array. What happens when you provide just one or no values?
- Change your algorithm so your array gets sorted in descending order rather than ascending order.
- Change your algorithm to sort
Stringvalues. You’ll have to do a few edits here. First, a few variables will need to be changed from
Strings, including the type of the input array itself! Next, you’ll have to take a look at your if statement. We can’t use
Strings. Instead, look into how the compareTo() method works. By using
compareTo()and seeing if the value is greater than or less than
0, you can determine which
Stringis “bigger” in value.