• Choose a category
• All
• Classic-Fiction

A: Quicksort. It is the best general-case sorting algorithm and is excellent for medium to large sets of data.

Q: Recall that the interfaces to qksort and mgsort require that i and k be passed by the caller. Why is this, and how could we avoid it in practice?

A: The arguments i and k are necessary to define smaller and smaller subsets of the data while recursing. An alternative to the caller providing these is to place each function in a wrapper . Wrappers generally provide cleaner public interfaces to functions that are otherwise cumbersome to call directly. Wrapping qksort, for example, gives us the opportunity to alleviate making the caller pass i and k, since we know that initially these always should be set to and size - 1. Wrapping qksort also gives us the opportunity to encapsulate a call to srand, which seeds the random number generator and prevents certain inputs from consistently eliciting bad behavior. This is something like what the standard library function qsort actually does. A wrapper might be implemented for qksort in Unix as shown below:

#include

#include

#include "sort.h"

int qsrt(void *data, int size, int esize, int (*compare)(const void *key1,

const void *key2)) {

srand(getpid());

return qksort(data, size, esize, 0, size - 1, compare);

}

Q: In rxsort, recall that counting sort is implemented explicitly rather than by calling ctsort. Why might this have been done?

A: Because radix sort works by considering only a single digit of the elements at a time, our counting sort implementation would have had to accept additional parameters to tell it which digit to consider as well as how to obtain each digit value. Recall that modular arithmetic was used in the implementation presented in this chapter, but other techniques might be more appropriate for some data. For example, for long strings we might choose to offset two bytes at a time into the string to form digits. Accounting for these application-specific considerations in counting sort would have complicated it substantially. Therefore, a slightly modified form of counting sort was included in the radix sort implementation.

Q: Suppose we have 220 128-bit elements that we would like to sort. What would be the efficiency of sorting these using quicksort? What would be the efficiency of sorting these as radix-216 numbers using radix sort? Which approach would be better? Suppose we have 210 128-bit elements rather than 220 elements. How do quicksort and radix sort compare in this case?

A: Sorting with quicksort requires O (n lg n) = (220)(20) = (2.10)(107) times some constant amount of time. Considering the elements as radix-216 numbers, the number of digit positions, p, is 8, and the number of possible digit values, k, is 216. Therefore, sorting with radix sort requires O (pn + pk) = (8)(220) + (8)(216) = (8.91)(106) times some constant amount of time. If the space requirements of radix sort are acceptable, radix sort is more than twice as efficient as quicksort. In the second case, sorting with quicksort requires O (n lg n) = (210)(10) = 10,240 times some constant amount of time. Radix sort requires O (pn + pk) = (8)(210) + (8)(216) = 532,480 times some constant amount of time, or 50 times as much time as quicksort! Here is an example of why k is typically chosen to be close to and no more than n. Had we used a radix of 28, radix sort would have required O (pn + pk) = (16)(28) + (16)(28) = 8160 times some constant amount of time, and would have been slightly better than quicksort. However, it is worth noting that the space requirement of radix sort may negate small benefits in time in many cases.

Q: In a sorted set, the successor of some node x is the next largest node after x. For example, in a sorted set containing the keys 24, 39, 41, 55, 87, 92, the successor of 41 is 55. How do we find the successor of an element x using binary search? What is the runtime complexity of this operation?

A: In a sorted set, to determine the successor of some element x using binary search, first we locate x. Next,