CS201 Study Guide

Unit 7: Searching and Sorting Algorithms

7a. Understand common search methods

  1. Which are the commonly-used search methods?
  2. What is a process for determining which search method is best for a given application?
  3. In what way does data search depend on data sorting?

We began our discussion of search by using vectors for illustration. Do not forget that linked-lists can be used as vectors. First, however, you should consider the algorithm's efficiency and effectiveness. In our study of search, we concentrated on linear, binary, and Fibonacci searches. While linear search is the least efficient in the Big-O sense, the data does not have to be pre-sorted. Plus, it is a very good approach when there is only a small volume of data.


7b. Understand common sort methods

  1. Which are the commonly-used sorting methods?
  2. What is a process for determining which sorting method is best for a given application?
  3. In what way does search impact sorting efficiency?

The ability to sort data allows us to organize it for various uses and search for specific items. We spent a lot of time on divide-and-conquer methods, especially merge sort. Divide-and-conquer allows for the best use of multi-core and multi-node networked systems when large data volumes are involved. Besides merge sort, we also discussed insertion sort; bubble and selection sorts; and quicksort (review this video until 18:44).


7c. Plan efficient and effective search and sort algorithms

  1. Why is it necessary to balance efficiency and effectiveness?
  2. Under what circumstances do we see similar resource utilization for all search or sort methods?
  3. Do the units of efficiency always have to do only with the computer itself? Explain.

Review the difference between recursive and nonrecursive implementations of quicksort. You will notice that the recursive version is much easier to understand. That does have value. However, it is difficult to determine a recursive implementation's memory requirements. For many modern systems, especially embedded systems, you cannot assume the availability of sufficient memory to accommodate whatever is required. From another perspective, cloud-memory is typically far more expensive than runtime. You must be able to calculate a cost-budget rather than assume whatever money is needed will be available. That simply will not work in commercial situations.


7d. Judge searching and sorting algorithms relative to their application efficiency

  1. What are the average runtime O(f(n)) of merge, insertion, binary, bubble, selection, and quicksort?
  2. What are the average runtime O(f(n)) of linear, binary, and Fibonacci search methods?
  3. State means of carrying out Big-O analysis of various approaches to search and sort.

There are general approaches (described on pages 55-85) to analyzing an algorithm's efficiency. To see two good examples, look at Big-O analyses of merge sort and insertion sort.


7e. Rate search and sort algorithms relative to an application's needs

  1. How would one balance ease of system integration with O(f(n)) for a given algorithm's implementation?
  2. Why care about code warnings, memory leaks, and memory fragmentation if the implementation "works"?
  3. For what reason might we not care about a resource's average O(f(n)) when choosing an algorithm?

Having studied search and sort algorithms to determine their average resource O(f(n)), it is time now to look at specific implementations. It is true that an algorithm is not the same as the algorithm's implementation, although many people will hand you a piece of code and refer to it as an algorithm. Always review the code carefully. I like to use static and dynamic review tools since manual approaches can miss subtle problems. Do not be fooled by people telling you that code warnings do not matter. Not only do they obscure problems, but they also have unrecognized interactions that can cause system failures. For this particular subunit, review the code-level expressions of merge, insertion, bubble, and selection sorting algorithms. You should also review the code for binary search.


Unit 7 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included.

  • merge sort
  • insertion sort
  • bubble sort
  • selection sort
  • quicksort
  • linear search
  • binary search
  • Fibonacci search
  • O(f(n))
  • Big-O analysis
  • divide-and-conquer
  • recursive
  • nonrecursive
  • worst, average, best O(f(n)) case