Let A [1: n] be an array that contain a sequence of distinct integers. Consider
ID: 3814961 • Letter: L
Question
Let A [1: n] be an array that contain a sequence of distinct integers. Consider the following algorithm, called selection sort, to sort A in increasing order: In the first pass, the smallest element is found and moved to the first position. In the second pass, the smallest of the remaining elements is found and moved to the second position. And so on. Express this algorithm in psuedocode, determine the exact number of comparisons made between elements of A, and then express this using big-O notation. (Ignore any other type of operation done by the algorithm.) Your style of pseudocode should be similar to the one in the text or seen in class; do not give full-blown C/C++/Java etc.Explanation / Answer
for i in 0 to n-1: //runing loop n times
do
min_ind = i //assigns the min element to be first element from where the loop is to be run
for j in i+1 to n: //Running loop n-i-1 times
do
if A[min_ind] > A[j]: //For finding the index of the min element in A[i] to A[n-1]
min_ind=j
end
swap(A[i], A[min_ind]) //The min element is moved to the ith position
end
For example: 5 4 3 2 1
First Pass: min_ind is set to 0. Then, in the inner loop min_ind successively becomes 1,2,3 and finally 4
After the inner loop is ended, A[0] and A[4] is swapped. New array = 1 4 3 2 5
Second pass: min_ind is set to 1. Then, in the inner loop min_ind successively becomes 2 and finally 3
After the inner loop is ended, A[1] and A[3] is swapped. New array = 1 2 3 4 5
Successive passes are similar
Number of comparisons:
The outer loop runs n-1 times:
For ith iteration of outer loop, inner loop runs n-i-1 times i.e. n-i-1 comparsions are made.
For first iteration of outer loop, n-1 comparisons are made, for second n-2 comparisons, for third, n-3 and so on.
Total no. of comparisons = n-1 + n-2 + n-3 +... + 1 = n*(n+1)/2 = O(n^2)
I hope this helps. Feel free to comment in case of any further doubts.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.