QUESTION # 19 5.3.012BC

The bubble sort that we introduced in Example 4.55 is sometimes called the "dumb bubble sort because it will continue to run even after the array has been put in order. The following algorithm checks a true/false variable s each time through the loop to see if any more sorting is necessary, The Smart Bubble Sort. Preconditions: X1, X2, Postconditions: X1Sx2 , and n 2. , xn E U, a set that is totally ordered by SX- s-talse //s="array is sorted" while do strue // hile jsn-i do array is sorted UNLESS r swap X and X +1 L S talse // a swap is nade This algorithm takes advantage of the observation that if no swaps are made, then the array must be in order. (a) What is the best-case number of array item comparisons in this algorithm, in terms of n? For what kind of data sets does it occur? INDICATE A, B, C OR D Ao the array alternates between large numbers and small numbers BO the array is in order CO the array is in a random order D o the array is in reverse order