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.
To see this executing using the Java Visualizer click on the following Insertion-Sort
You can step through the code above by clicking on the following Ex-12-5-2.