Exercises 2.2-4

Find some special case for the problem, and solve the special case quickly.

Exercises 2.2-3

Average case: n/2
Worst case: n
All are Θ(n)

Exercises 2.2-2

i = 1
while i < n
    min = i
    j = i+1
    while j ≤ n
        if a[j] < a[min]
            min = j
        j = j + 1
    Swap(a[i],a[min])
    i = i + 1

Loop invariant: A[1] ~ A[i] is the smallest i numbers in A[1] ~ A[n], and A[1]~A[i] is sorted.

Since the A[1] ~ A[n-1] is the smallest n-1 numbers, A[n] must be the largest number.

Best case:
Worst case:

Exercises 2.2-1