5 What is the order of growth of your algorithm to find the median?
??( n( lg n ) ), based on merge_sort
182 ANSWERS TO REVIEW QUESTIONS
2.6 Suppose that your algorithm to find the mean is ??(n), and that your algorithm to find the median is
??(n lg n), what will be the execution speed ratio between your algorithm for the mean and your
algorithm for the median when the number of values is 1,000,000?
mean : median :: 1,000,000 : 1,000,000 * lg 1,000,000
mean : median :: 1 : lg 1,000,000
mean : median :: 1 : 20
It will be 20 times faster to find the mean than the median.
2.7 A sort routine which is easy to program is the bubble-sort. The program simply scans all of the elements
to be sorted repeatedly. On each pass, the program compares each element with the one next to it, and
reorders the two, if they are in inverse order. For instance, to sort the following list:
6 7 3 1 4
Bubble-sort starts by comparing 6 and 7. They are in the correct order, so it then compares 7 and 3.
They are in inverse order, so bubble-sort exchanges 7 and 3, and then compares 7 and 1. The
numbers 7 & 1 are in reverse order, so bubble-sort swaps them, and then compares 7 & 4. Once
again, the order is incorrect, so it swaps 7 & 4.
Pages:
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500