Selection sort (4)
Analysis (counting comparisons):
Let n = right – left + 1 be the length of the array.
Step 1.1 performs right–l comparisons.This is repeated with l = left, …, right–2, right–1.
No. of comparisons = (right–left) + … + 2 + 1 = (n–1) + … + 2 + 1 = (n – 1)n/2 = (n2 – n)/2
Time complexity is O(n2).