Comp 110 Insertion Sort

Insertion Sort

Algorithm

1.) Set the start index at the beginning of the array

2.) SWAP the start element backwards through the array while its value is less than the element before it

  1. Set our selected index to start
  2. While selected is not the first element and it is smaller than the element before it
  3. SWAP the element at selected with the element before it
  4. Subtract one from selected and return to step 2.1

3.) Increment start index by one

4.) If the end of the array has been reached: sorted! Else, go to step #2

Swap steps

Given indexes i and j, swap the elements in the array.

1.) Store the element at index i in a temporary variable

2.) Set the element at index i to the value of the element at index j

3.) Set the element at index j to the value stored in the temporary variable

Run Time

Worst case: O(n2)

Best case: O(n)

Average case: O(n2)