 # APCS Ch 6: Sorting and Searching Methods

## Insertion Sort

Imagine being dealt cards out of a deck. Usually, you would want to order your cards when you get them, right? When you get dealt your first card, you have nothing to compare its value to so it stays in place. When you get dealt your second card, you can compare the two cards and compare and order them. When you get dealt your third card, you also order the card relative to the values of your other cards. The insertion sort works the same way. I won’t go as in depth in this method of sorting as the selection sort.

Let’s look at the code:

//nums is an array of ints

for (int i = 1; i < nums.length; i++)

{

int temp = nums[i];

int j = i – 1;

while ( j >= 0 && nums[j] > temp)

{

nums[j + 1] = nums [j];

j–;

}

nums[j + 1] = temp;

}

}

The paper version of this would look like this:

The biggest difference is that while the selection sort looks at and compares all the values to the right of the index position we’re currently looking at, the insertion sorts look at all the index positions to the left.

Let’s break down the code:

for (int i = 1; i < nums.length; i++)

This outer for loop starts at index 1 (since the first “card” has nothing to compare to) and goes through the rest of the index positions on the array.

int temp = nums[i];

int j = i – 1;

This sets temp to the number at the index position that we’re currently looking at. The variable j stores the index value immediately to the left of the index position we’re currently looking at.

while ( j >= 0 && nums[j] > temp)

This while loop works as long as j (i – 1) isn’t less than index 0 (and therefore, OutOfBounds) and the number at index j is bigger than the number immediately to the right of it.

nums[j + 1] = nums [j];

j–;

This basically scoots all index positions up to index j + 1 to the left until either j reaches index 0 and can’t scoot anything else down or it finds that the number at index i is bigger than the number at index j. Basically, what happens is that it compares the number at index i to all numbers to the index positions to the left of it. If the number at index i is smaller than the number immediately to the left of it, it moves left one slot until it finds that it is bigger than the number immediately to the left of it at which point it is in its final sorted spot.

nums[j + 1] = temp;

This basically does the last part of what I said above. It sets the number at index i to its final sorted spot.

Since for the insertion sort, the outer loop starts at index position one, if you have four passes of the outer loop, then the first five numbers are in their final sorted position. The number of total passes would still be length – 1.

See next page for Search Methods 