Java™ How to Program, Sixth Edition - Part16

Few weeks back i started reading Java™ How to Program, Sixth Edition By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

Nice book written By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

I wanted to share few quotations found the book from the 16th chapter.

1) Searching data involves determining whether a search key is present in the data and, if so, finding its location.

2) Sorting involves arranging data into order.

3) The linear search algorithm searches each element in the array sequentially until it finds the correct element. If the element is not in the array, the algorithm tests each element in the array, and when the end of the array is reached, informs the user that the element is not present. If the element is in the array, linear search tests each item until it finds the correct item.

4) A major difference among searching algorithms is the amount of effort they require in order to return a result.

5) One way to describe the efficiency of an algorithm is with Big O notation (O), which indicates how hard an algorithm may have to work to solve a problem.

6) For searching and sorting algorithms, Big O is often dependent on how many elements are in the data.

7) An algorithm that is O(1) does not necessarily require only one comparison. It just means that the number of comparisons does not grow as the size of the array increases.

8) An O(n) algorithm is referred to as having a linear run time.

9) Big O is designed to highlight dominant factors and ignore terms that become unimportant with high n values.

10) Big O notation is concerned with the growth rate of algorithm run times, so constants are ignored.

11) The linear search algorithm runs in O(n) time.

12) The worst case in linear search is that every element must be checked to determine whether the search item exists. This occurs if the search key is the last element in the array or is not present.

13) The binary search algorithm is more efficient than the linear search algorithm, but it requires that the array be sorted.

The first iteration of binary search tests the middle element in the array. If this is the search key, the algorithm returns its location. If the search key is less than the middle element, binary search continues with the first half of the array. If the search key is greater than the middle element, binary search continues with the second half of the array. Each iteration of binary search tests the middle value of the remaining array and, if the element is not found, eliminates half of the remaining elements.

14) Binary search is a more efficient searching algorithm than linear search because binary search with each comparison eliminates from consideration half of the elements in the array.

15) Binary search runs in O(log n) time because each step removes half of the remaining elements.

16) If the size of the array is doubled, binary search requires only one extra comparison to complete successfully.

17) Selection sort is a simple, but inefficient, sorting algorithm.

18) The first iteration of selection sort selects the smallest element in the array and swaps it with the first element. The second iteration of selection sort selects the second-smallest item (which is the smallest remaining item) and swaps it with the second element. Selection sort continues until the last iteration selects the second-largest element and swaps it with the second-to-last index, leaving the largest element in the last index. At the ith iteration of selection sort, the smallest i items of the whole array are sorted into the first i indices.

19) The selection sort algorithm runs in O(n2) time.

20) The first iteration of insertion sort takes the second element in the array and, if it is less than the first element, swaps it with the first element. The second iteration of insertion sort looks at the third element and inserts it in the correct position with respect to the first two elements. After the ith iteration of insertion sort, the first i elements in the original array are sorted.

21) The insertion sort algorithm runs in O(n2) time.

22) Merge sort is a sorting algorithm that is faster, but more complex to implement, than selection sort and insertion sort.

23) The merge sort algorithm sorts an array by splitting the array into two equal-sized subarrays, sorting each subarray recursively and merging the subarrays into one larger array.

24) Merge sort's base case is an array with one element. A one-element array is already sorted, so merge sort immediately returns when it is called with a one-element array. The merge part of merge sort takes two sorted arrays (these could be one-element arrays) and combines them into one larger sorted array.

25) Merge sort performs the merge by looking at the first element in each array, which is also the smallest element in the array. Merge sort takes the smallest of these and places it in the first element of the larger array. If there are still elements in the subarray, merge sort looks at the second element in that subarray (which is now the smallest element remaining) and compares it to the first element in the other subarray. Merge sort continues this process until the larger array is filled.

26) In the worst case, the first call to merge sort has to make O(n) comparisons to fill the n slots in the final array.

27) The merging portion of the merge sort algorithm is performed on two subarrays, each of approximately size n/2. Creating each of these subarrays requires n/2 1 comparisons for each subarray, or O(n) comparisons total. This pattern continues as each level works on twice as many arrays, but each is half the size of the previous array.

28) Similar to binary search, this halving results in log n levels for a total efficiency of O(n log n).

29) An invariant is an assertion that is true before and after the execution of a portion of your code.

30) A loop invariant is an assertion that is true before you begin executing the loop, during each iteration of the loop and after the loop terminates.

About the Authors

Dr. Harvey M. Deitel, Chairman and Chief Strategy Officer of Deitel & Associates, Inc., has 43 years experience in the computing field, including extensive industry and academic experience. Dr. Deitel earned B.S. and M.S. degrees from the Massachusetts Institute of Technology and a Ph.D. from Boston University. He worked on the pioneering virtual-memory operating-systems projects at IBM and MIT that developed techniques now widely implemented in systems such as UNIX, Linux and Windows XP. He has 20 years of college teaching experience, including earning tenure and serving as the Chairman of the Computer Science Department at Boston College before founding Deitel & Associates, Inc., with his son, Paul J. Deitel. He and Paul are the co-authors of several dozen books and multimedia packages and they are writing many more. With translations published in Japanese, German, Russian, Spanish, Traditional Chinese, Simplified Chinese, Korean, French, Polish, Italian, Portuguese, Greek, Urdu and Turkish, the Deitels' texts have earned international recognition. Dr. Deitel has delivered hundreds of professional seminars to major corporations, academic institutions, government organizations and the military.

Paul J. Deitel, CEO and Chief Technical Officer of Deitel & Associates, Inc., is a graduate of the MIT's Sloan School of Management, where he studied Information Technology. Through Deitel & Associates, Inc., he has delivered Java, C, C++, Internet and World Wide Web courses to industry clients, including IBM, Sun Microsystems, Dell, Lucent Technologies, Fidelity, NASA at the Kennedy Space Center, the National Severe Storm Laboratory, Compaq, White Sands Missile Range, Rogue Wave Software, Boeing, Stratus, Cambridge Technology Partners, Open Environment Corporation, One Wave, Hyperion Software, Adra Systems, Entergy, CableData Systems and many other organizations. Paul is one of the most experienced Java corporate trainers having taught about 100 professional Java training courses. He has also lectured on C++ and Java for the Boston Chapter of the Association for Computing Machinery. He and his father, Dr. Harvey M. Deitel, are the world's best-selling Computer Science textbook authors.