Insertion Sort¶

The insertion sort that you need to know for the exam starts at index 1 and inserts the value at index 1 into its correct place in the already sorted part (the part to the left of the current index). It moves any value larger than the value stored in temp to the right until it either finds the appropriate place to put temp or gets to the front of the array.

To identify an insertion sort look for the following:

• an outer for loop that starts at 1 and loops through the entire array (see line 7)
• storing the element value at the outer loop index in temp (see line 9)
• setting the possible index to the outer loop index (see line 10)
• an inner while loop that loops while the possible index is greater than 0 and the value in temp is less than the value at the possible index minus one (see line 11)
• set the value at the possible index to the one to the left of it (the one at possible index minus one) (see line 13)
• decrement the possible index (subtract one from it) (see line 14)
• when the while loop ends set the value at the possible index to temp (see line 16)

The code for insertionSort below is from the AP CS A course description.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.Arrays; public class SortTest { public static void insertionSort(int[] elements) { for (int j = 1; j < elements.length; j++) { int temp = elements[j]; int possibleIndex = j; while (possibleIndex > 0 && temp < elements[possibleIndex - 1]) { elements[possibleIndex] = elements[possibleIndex - 1]; possibleIndex--; } elements[possibleIndex] = temp; } } public static void main(String[] args) { int[] arr1 = {3, 86, -20, 14, 40}; System.out.println(Arrays.toString(arr1)); insertionSort(arr1); System.out.println(Arrays.toString(arr1)); } } 

To see this executing using the Java Visualizer click on this link

12-5-1: Under what condition will an insertion sort execute faster?

12-5-2: This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

public static void insertionSort(int[] elements)
{
for (int j = 1; j < elements.length - 1; j++)                       // line 1
{
int temp = elements[j];                                          // line 2
int possibleIndex = j;                                           // line 3
while (possibleIndex > 0 && temp < elements[possibleIndex - 1])  // line 4
{
elements[possibleIndex] = elements[possibleIndex - 1];        // line 5
possibleIndex--;
}
elements[possibleIndex] = temp;
}
}