Consider sorting numbers stored in array by first finding the smallest element of and exchanging it with the element in . Then find the smallest element of , and exchange it with . Then find the smallest element of , and exchange it with . Continue in this manner for the first elements of .
Write the 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 elements, rather than for all elements?
Give the worst-case running time of selection sort in -notation.
Is the best-case running time any better?
Algorithm
SELECTION-SORT (A, n)
for i = 1 to n
min_index = i
for j = i + 1 to n:
if A[j] < key
min_index = j
SWAP(A, i, j)
SWAP(A, i, j)
temp = A[i]
A[i] = A[j]
A[j] = temp
Loop Invariant
Initialization:
Maintenance:
Termination:
In the case of selection sort, all the elements at are sorted containing an increasing order of the smallest values in the array while the sub array remains unsorted. To sort the unsorted part, we need to find the smallest element from and swap with , removing the need to start searching from the first element which in turn could mean looping through the inner loop for every element, we only loop through the entire loop in times for the first element, and for each element , we have to loop elements to get the array sorted.
The worst case running time would occur at the first element. The Outer loop runs at for the first item at index , but to get the index of the lowest element from the sub array A[: ], the inner loop has to run times comparing each element to determine the lowest. Combining both run times becomes , and taking away the lower order terms and constants, the worst case running time is .
The best case running time would still be considering the fact that the lowest element of the subarray must be determined. If is sorted, and is an unsorted subarray, and we have to sort the next smaller element by swapping with any smaller element from . If the lowest element occurs at – the first element from the unsorted subarray, the inner loop can’t halt operation at this point, it has to continue to assert that no other element is lower than from , even if from this point onwards all the elements in the subarray are larger than .