If you choose to study computer science, you will almost certainly encounter these algorithms (or a very similar set of algorithms) early in your study:
- sequential search
- binary search
- selection sort
- insertion sort
- merge sort
Some curricula include the selection sort but not the insertion sort, or vice versa. Other curricula substitute the quicksort for the merge sort and others ask students to learn both the merge sort and the quicksort algorithms.
Of course, if you continue your studies far enough, you will encounter other algorithms. These algorithms are those found somewhere in the first few courses of all computer science curricula.
Let’s suppose that you have the power to decide which algorithms all students of computer science will learn well early in their study of computer science. How will you go about selecting algorithms?
Here are some properties that might make an algorithm attractive:
- we can express the algorithm concisely
- the algorithm that has wide application
- computer scientists understand the algorithm very well
- study of the algorithm will introduce students to important principles
Now look at our five algorithms. Do the algorithms that we have chosen possess these attractive qualities?
Concise expression
A programmer can write code that expresses any of the five algorithms on less than one page. You will complete some of your exercises with just ten lines of code.
Some other algorithms must address several exceptional conditions. These algorithms do not.
Some other algorithms work with complex data structures. These algorithms do not. These algorithms act on lists. Students come to class already knowing what lists are.
Descriptions of these algorithms require no mathematical notation or definitions of mathematical operations that might be unfamiliar.
Wide application
The solutions of a great variety of problems require some searching or sorting.
When students at a college use software to register for courses, find a book at the library, or look up a professor’s e-mail address, they are searching. For example, a search for a particular course in a database that contains all courses that a college is offering during the fall semester can yield information about the number of seats still available in the course, the name of the instructor, and the time and place at which the class will meet.
When students use software to produce a bibliography, they might be sorting articles by the authors’ names.
When a computer game draws a three-dimensional scene, it draws the objects in the foreground over the objects in the background. The graphics software sorts objects from back to front.
There are many other examples.
Well understood
Computer scientists have thoroughly analyzed the sequential search, binary search, selection sort, insertion sort, and merge sort algorithms.
Let’s focus on just two of these algorithms.
Our list of algorithms includes two searching algorithms. An analysis of the sequential search and the binary search algorithms yields bounds on the number of instructions that the computer will have to execute in order of find a match in a list. The number of instructions depends upon the length of the list. That relationship between the number of instructions and the length of a list is known.
Sequential search can find a match in an unsorted list, but might have to examine every element of the list to find a match. Imagine a pile of old mail on a messy desk. The letters lie stacked in no particular order. Someone who is looking for last month’s telephone bill will, in the worst case, have to examine every letter.
Binary search works only with sorted lists like the words in a dictionary or the names in a telephone book. A person who is looking for the definition of “xylophone” in a dictionary need not look at the definitions of all the words that begin with the letter “a,”, then all of the words that begin with the letter “b,” and so on until arriving at the words that begin with “x.” A binary search can be faster than a sequential search.
Computer scientists work with time and space. Time means the number of instructions that the computer executes to produce the solution to a problem. Space means how much memory is needed for the execution of an algorithm. Given two alternative solutions to a problem, computer scientists want to know which method requires the least time or the least space.
Computer scientists have developed methods for analyzing algorithms. They have a notation for concisely describing the complexity of these algorithms. The time complexity of the sequential search algorithm is O(N). The time complexity of the binary search algorithm is O(log N).
Important principles
Through the study of searching and sorting algorithms, you will learn how to measure and compare the performance of algorithms.
In writing programs that express searching and sorting algorithms, you will learn how to work with lists. You will use lists in many programs that you write later. Lists are both simple and ubiquitous.
You will learn how to instruct the computer to repeatedly execute a block of code. You will learn to use iteration and recursion. You will learn how to instruct the computer to execute a block of code conditionally.
In your study of the binary search and merge sort algorithms, you will learn how to “divide and conquer.” This strategy can simplify the solution of some problems.
Exercises with all of these functions will give you practice designing, writing, and testing functions. You will gain familiarity with principles that will guide your design, writing, and testing of functions. These are fundamental skills. A knowledge of principles will make you a more skillful software engineer.