Chapter 2.2

\(\Theta(n^3)\)

SELECTION-SORT(A)
for i = 1 to A.length - 1
    x = A[i]
    k = i
    for j = i + 1 to A.length
        if A[j] < x
            x = A[j]
            k = j
    exchange A[i] with A[k]

Loop Invariant: At the start of each outer loop iteration, the subarray A[1..i - 1] contains the (i - 1) smallest elements.

When the first (n - 1) elements contains the (n - 1) smallest elements, the nth element is the largest element.

The running time of selection sort is \(\Theta(n^2)\) on any cases.

We need to check Half of the input sequence on the average case.

The worst-case appears when v is not in A, we need to check all elements in A.

The average-case and worst-case running times are both \(\Theta(n)\).

Modify the algorithm to test the input, and output the immediate result when the input is as expected.