Learn

Great job! So far we have created a for loop that starts at index 1 and loops through our input array: 7, 2, 5, 8, -3
We have a sorted sub-list containing our first item: 7
Our unsorted sub-list contains the rest of our array: 2, 5, 8, -3

Inside of our for loop we set the value of the input array at i, arr[i], to current. Our first time through the loop, array[i] is equal to 2.

We then created a while loop that will break if we have reached the front of the array or will break if the preceding item compared to current is indeed less than the value of current.

In this exercise we want to look at how to shift our element(s) in the sorted sub-list that is greater than current.

We will also look at how we insert current when either of the conditions in our while loop are not true.

insertionSort(array)
  Iterate over array starting at index 1
    Compare the current element to its predecessor
      If the current element is smaller than its predecessor, compare it to the element before
      Move the greater elements one position up to make space 
    Insert current element
end insertionSort

Instructions

1.

Inside of our while loop we want to take the value at array[j] and move it one element to the right. We can do this by setting array[j + 1] to array[j].

2.

Still inside our while loop, reduce the value of j by 1.

3.

When either of our while loop conditions break it means we have found the position to insert our unsorted element. Set array[ j+1 ] to current before we close our outer for loop. This is because if we need to insert the value to the very front of the array, then j would eventually become -1. We don’t want to insert the value into array[-1], but rather array[-1 + 1], or array[0].

... for (var i = 1; i < size; i++) { int current = array[i]; int j = i - 1; while (j >= 0 && array[j] > current) { array[j+ 1] = array[j]; j--; } // insert code here } ...

This continues for every iteration of the outer for loop until that also breaks by reaching the end of the input array. At this point we can consider our array sorted!

4.

Let’s take a look at our insertion sort algorithm in action! In the main() function add the following code:

int[] numbers = {7, 2, 14, -7, 72}; System.out.println("Array in ascending order"); sort(numbers); System.out.println(Arrays.toString(numbers));

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?