Topics to Revisit

• Selection algorithm
• Calculate

Sorting Algorithms

Insertion Sort

How It Works

• GIF
• Code
• Time complexity is $O(n^2)$
• Assume first element of the array $A$, with $n$ elements, is sorted
• We have the left-hand side of the array as sorted, and the right-hand side is unsorted.
• For each unsorted element $A[i]$, scan the array backwards and look to insert $A[i]$ in the correct position
• We store $A[i]$ in $\text{key}$ since we may shift a value into that position
• We start scanning the array backwards from $j = i-1$
• If $\text{key} < A[j]$ and $j \ge 0$:
  • shift $A[j]$ to $A[j+1]$
  • decrement $j$
• Otherwise, we have found the correct position $j+1$ to insert $\text{key}$ into; $A[j+1] = \text{key}$.

Selection Sort

• Code
• Time complexity: $O(n^2)$