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:

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

To see this executing using the Java Visualizer click on the following Insertion-Sort

    12-5-1: 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.

    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;
      }
    }
    
  • 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.

Next Section - 13.6. Merge Sort