Week 03 (Sorting) (20)

20

Selection Sort (cont)

Cost analysis (where n = hi-lo+1):

on first pass, n-1 comparisons, 1 swap
on second pass, n-2 comparisons, 1 swap
... on last pass, 1 comparison, 1 swap
C = (n-1)+(n-2)+...+1 = n*(n-1)/2 = (n²-n)/2 ⇒ O(n²)
S = n-1

Cost is same, regardless of sortedness of original array.