Question

Selection-Sort( A[1..n] )

1 2 3 4 5 6 7 8 9

10

// INPUT: A[1..n], an array of any n numbers in unknown order integer i, j, m

fori=1ton−1

do

swap A[i] ↔ A[m]

// OUTPUT: A[1..n], its numbers now sorted in non-decreasing order

m=i

for j = i to n

do if A[j] < A[m] then m = j

Give a proof that this algorithm sorts its input as claimed.

Answer 1

selection sort algorithm
selectionSort(A,n)
min = 0

for (i = 0; i < n-1; i++)
{
min = i;
for (j = i+1 to n-1)
if (A[j] < A[min])
min = j;

swap(A[min], A[i]);
}

Proof using Loop Invariant
Loop Invariant : After i iteration ,all elements from index 0 to i-1 array A[] is sorted in non decreasing order.And all entries in A[i..n-1] are larger than or equal to the entries in A[0..i-1]

Base case :initially (when i=0),there is no any element from index 0 to -1.

Maintenance: In each outer loop iteration,inner loop finds minimum element in A[i to n-1] and put it at i^th place.which make array A[0 to i] sorted in non decreasing order(Because all entries in A[i..n-1] are larger than or equal to the entries in A[0..i-1]).

Termination: when i=n all element in array A[0..n-1] are sorted in non decreasing order.