The following variant of bubble sort is used on an array of 10 distinct numbers: SET swapped = true SET pass = 0 WHILE swapped AND pass A[i+1] THEN SWAP A[i], A[i+1] SET swapped = true ENDIF ENDFOR SET pass = pass + 1 ENDWHILE What is the maximum possible number of comparisons performed, and what is the minimum possible number of comparisons performed, for this array size?

Question

The following variant of bubble sort is used on an array of 10 distinct numbers:

SET swapped = true
SET pass = 0
WHILE swapped AND pass < n-1
   SET swapped = false
   FOR i FROM 1 TO n-pass-1
       IF A[i] > A[i+1] THEN
           SWAP A[i], A[i+1]
           SET swapped = true
       ENDIF
   ENDFOR
   SET pass = pass + 1
ENDWHILE

What is the maximum possible number of comparisons performed, and what is the minimum possible number of comparisons performed, for this array size?

Accepted Answer

Maximum 45 comparisons; Minimum 9 comparisons

Gce Model Questions Vol1 2019 Computer Studies Question 35

Answer Options

About This Question

Master the Exam!