Unit 7: Searching and Sorting
As a computer programmer, you need to know how to search and sort data. This will require you to leverage what you have learned in a number of different computer science areas, drawing from your earlier study of data structures and algorithms. In this
unit, we will identify the importance of searching and sorting, learn a number of popular searching and sorting algorithms, and determine how to analyze and appropriately apply them. By the end of this unit, you will recognize instances in which you
need a searching or sorting algorithm and be able to apply one efficiently.
Completing this unit should take you approximately 8 hours.
7.1: Search Algorithms
Why study searching and sorting? There are two reasons for doing so.
First, searching and sorting are tasks that occur frequently and so are needed in programming.
Secondly, the requirements for these two necessary capabilities are simple and clear. Their designs and implementations are well developed, they are implemented in every language, are available in many code libraries, and their performance (time and space) are well understood.
Divide and Conquer algorithms, such as List and Tree Search, and Merge and Insertion Sort, make good examples for demonstrating the concepts of this course: decomposition, abstraction, modularization, hierarchy.
7.2: Sorting Algorithms
Whereas searching takes a data structure as input and outputs an element of the data structure, sorting is more complex in that it takes a data structure as input and returns a data structure of the same type, but with the elements rearranged. There are a few search algorithms: linear for a list, depth or breadth traversal for a tree, and binary search. There are several sorting algorithms; this unit presents a number of them.
7.3: Analyzing Program Efficiency
Unit 7 Assessment