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`.

``````...
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));``````