Question

2. You can actually find the median by running a sorting algorithm and stopping early, as soon as you know the median.

(a) Assume you use Bubble Sort to find the median of 13 elements (i.e. n = 13), but stop as soon as you know the median. Exactly how many comparisons do you use (in the worst case)?

(b) Assume you use Mergesort to find the median of 13 elements (i.e. n = 13), but stop as soon as you know the median. Exactly how many comparisons do you use (in the worst case)?

Answer 1

For Bubble sort, Worst case occurs when array is reverse sorted.

In bubble sort , in every pass one element is put to the correct place i.e., from the last. ( Observe j<n-i-1 in the below code)

for (i = 0; i < n-1; i++)         

       // Last i elements are already in place   

       for (j = 0; j < n-i-1; j++)

           if (arr[j] > arr[j+1])

              swap(&arr[j], &arr[j+1]);

Let us consider an example where we have to bubble sort the elements:

13,12,11,10,9,8,7,6,5,4,3,2,1

In every pass, we have one element placed at the right place. Since we have to find median which is [ (n/2)+1]

i.e., [(13/2)+1)] = 6+1 = 7.

So after 7 passes we will have the median placed at the middle position.

In every pass, we have ( n - i ) comparisons. The example we discussed here is the worst possible case, hence to find the median of 13 elements using bubble sort, we require

12+11+10+9+8+7+6 = 63 comparisons.

In merge sort, the approach is divide and conquer. Hence, the complete solution is yielded at last only.

Merge sort does n-1 comparisons for any given problem while merging any two arrays.

Page № 1 Oulb: 13 12 L Lo 83 13 0O 00 12 13 To 3 1o 1 12 13 AMnAge operati n-1 12 13 Rach 3 ,213,h,S,6,7, 8.1心11112132-712-depths 2,3

Hence, total number of comparisons = ( 5 x 1 ) + ( 2 x 3 ) + 3 + 5 + 6 + 12 = 37.

Merge sort does 37 comparisons when n=13 and median can be find after this many comparisons.