Insertion Sort (cont)
Complexity analysis ...
- cost for inserting element into sorted list of length i
- C=??, depends on "sortedness", best=1, worst=i
- S=??, don't swap, just shift, but do C-1 shifts
- always have N iterations
- Costbest = 1 + 1 + ... + 1 (already sorted)
- Costworst = 1 + 2 + ... + N = N*(N+1)/2 (reverse sorted)
- Complexity is thus O(N2)
|