Consider the quick sort algorithm as implemented in the text using the sort pattern. Which of the following data characteristics give the fastest run time? Explain.
a. An array sorted into increasing values.
b. An array sorted into decreasing values.
c. An array of random values
d. An array that increases for half the array, then decreases
Part c) an array of random values will have the least chance of having the split create consistently equal subarrays, hence give a runtime of O(N log N).
Explanation: All the other choices guarantee split gives subarrays of size 1 and N-1, hence give quadratic performance. Part d) requires a little thought, but it too gives quadratic runtime.
You might also like to view...
Map the BANK ER schema of Exercise 7.23 (shown in Figure 7.21) into a relational schema. Specify all primary keys and foreign keys. Repeat for the AIRLINE schema (Figure 7.20) of Exercise 7.19 and for the other schemas for Exercises 7.16 through 7.24.
What will be an ideal response?
The StringIndexOutOfBoundsException could be thrown by the method parseInt of the class Integer.
Answer the following statement true (T) or false (F)
Which of the following resources need to be protected to the detriment of all other resources?
A. tangible assets B. intangible assets C. information assets D. personnel assets
Discuss in detail the importance of using culling and cut-ins during the CGI process. How does this save processor power?
What will be an ideal response?