[Introduction to Algorithms, CLRS] Exercises 2.2-2

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.2-2

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1] . Then find the second smallest element of A, and exchange it with A[2] . Continue in this manner for the first n-1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n-1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ-notation.

Answer:

- Pseudocode:

SELECTION-SORT(A)     

1     for i = 1 to A.length-1

2        min = i

3        for j = i+1 to A.length  

4            if A[min] > A[j]

5                min = A[j]

6            temp = A[i]

7            A[i] = A[min]

8            A[min] = temp

- loop invariant:

At the start of each iteration of the outer for loop, the subarray A[1..i−1] contains the smallest i−1 elements of the array, sorted in nondecreasing order. At the start of each iteration of the inner for loop, A[min] is the smallest number in the subarray A[i..j−1].

- Why n−1 elements?:

In (n-1)th step, the algorithm will have two elements to compare. It will store the smaller one in A[n−1] and leave the larger in A[n]; therefore, (n)th step will have only one, the largest element to compare with nothing. In this given situation, comparing n-1 elements is enough.

- Best-case & Worst-case

1) best-case (if the array is already sorted)

( n - 1 ) * ( 1 + (( n - 1 + 1 ) / 2) * 1 + 3 ) = ( n - 1 ) * ( n / 2 + 4 )

2) worst-case (if the array is reversely sorted)

( n - 1 ) * ( 1 + (( n - 1 + 1 ) / 2) * (2) + 3 ) = ( n - 1 ) * ( n  + 4 )

therefore, both are Θ(n^2).

source: https://ita.skanev.com/02/02/02.html