16.1 |
a) 16, because an O(n2) algorithm takes 16 times as long to sort four times as much information. b) O(n log n). |
16.2 |
Both of these algorithms incorporate "halving"somehow reducing something by half. The binary search eliminates from consideration one half of the array after each comparison. The merge sort splits the array in half each time it is called. |
16.3 |
The insertion sort is easier to understand and to program than the merge sort. The merge sort is far more efficient (O(n log n)) than the insertion sort (O(n2) ). |
16.4 |
In a sense, it does not really sort these two subarrays. It simply keeps splitting the original array in half until it provides a one-element subarray, which is, of course, sorted. It then builds up the original two subarrays by merging these one-element arrays to form larger subarrays which are then merged, and so on. |
Introduction to Computers, the Internet and the World Wide Web
Introduction to Java Applications
Introduction to Classes and Objects
Control Statements: Part I
Control Statements: Part 2
Methods: A Deeper Look
Arrays
Classes and Objects: A Deeper Look
Object-Oriented Programming: Inheritance
Object-Oriented Programming: Polymorphism
GUI Components: Part 1
Graphics and Java 2D™
Exception Handling
Files and Streams
Recursion
Searching and Sorting
Data Structures
Generics
Collections
Introduction to Java Applets
Multimedia: Applets and Applications
GUI Components: Part 2
Multithreading
Networking
Accessing Databases with JDBC
Servlets
JavaServer Pages (JSP)
Formatted Output
Strings, Characters and Regular Expressions
Appendix A. Operator Precedence Chart
Appendix B. ASCII Character Set
Appendix C. Keywords and Reserved Words
Appendix D. Primitive Types
Appendix E. (On CD) Number Systems
Appendix F. (On CD) Unicode®
Appendix G. Using the Java API Documentation
Appendix H. (On CD) Creating Documentation with javadoc
Appendix I. (On CD) Bit Manipulation
Appendix J. (On CD) ATM Case Study Code
Appendix K. (On CD) Labeled break and continue Statements
Appendix L. (On CD) UML 2: Additional Diagram Types
Appendix M. (On CD) Design Patterns
Appendix N. Using the Debugger
Inside Back Cover