These notes and closely review Unit 2 Section 1.

## selectionSort

SelectionSort is one of the classic sorting algorithms. Here's a nice simple iterative version of it:
selectionSort(A,n)
input:  A an array of n objects for which "<" is defined
n the size of A
Output: side effect of leaving A in sorted order according to "<"

for i from 0 to n-2 do
m = i
for j from i+1 to n-1 do
if A[j] < A[m]
m = j
swap(A[i],A[m])

In class we showed that its worst-case running time is $O(n^2)$, which ... well, duh. More interestingly, we showed that its worst-case running time is $\Omega(n)$. Put the two together, and we arrive at the fact that the worst-case running time for selectionSort is $\Theta(n)$.

## insertionSort

SelectionSort is another one of the classic sorting algorithms. Here's a nice simple iterative version of it:
insertionSort(A,n)
input:  A an array of n objects for which "<" is defined
n the size of A
Output: side effect of leaving A in sorted order according to "<"

for i from 0 to n-2 do
j = i + 1
while j > 0 and A[j] < A[j-1] do
swap(A[i],A[m])
j = j - 1

In class we showed that its worst-case running time is $O(n^2)$, which ... well, duh. More interestingly, we showed that its worst-case running time is $\Omega(n)$. This was more involved than for selectionSort. Why? Because selectionSort's inner loop always executes $n - i - 1$ times, no matter what the input looks like. With insertionSort, however, the inner loop makes anywhere from $0$ to $i$ iterations, depending on the particulars of the input, because the "A[j] < A[j-1]" condition allows us to exit the inner loop early. To do this analyis, we had to find concrete inputs for which insertionSort is slow. Someone noticed that for reverse-sorted input, the inner loop always iterates the maximum number of times (which is $i$). So we derived $\Omega(n)$. Once again, put the two facts together, and we arrive at the fact that the worst-case running time for insertionSort is $\Theta(n)$.