This book is now obsolete Please use CSAwesome instead.

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

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 the following Insertion-Sort

13-5-3: Under what condition will an insertion sort execute faster?

• If the data is already sorted in ascending order
• If the data is already sorted in the correct order you don't need to move any values.
• If the data is already sorted in descending order
• This would actually result in the longest execution.
• It will always take the same amount of time to execute
• This would be true if it was a selection sort.

13-5-4: 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;
  }
}

• line 1
• It should loop through the entire array.
• line 2
• The value at the outer loop index should be stored in temp.
• line 3
• The possible index should be set to the outer loop index before the inner loop executes.
• line 4
• Loop while the possible index is greater than 0 and the temp value is less than the value at the possible index minus one.
• line 5
• Move the value at possible index minus one to the possible index (move to the right).

You can step through the code above by clicking on the following Ex-12-5-2.

You have attempted of activities on this page