Why program a computer to perform a task that people can do by hand?People can sort short lists by hand. Computers become indispensable when the number or length of the lists to be sorted become very large.
We study two algorithms for searching and three algorithms for sorting in our first course. If you continue your study of computer science, you will encounter other searching and sorting algorithms. By showing you several algorithms, we are making the point that you will often have a choice of methods for solving a given problem. A good computer scientist finds the solution to an assigned problem. A better computer scientist recognizes choices, selects the best alternative from among those several methods, and can give reasons for preferring one method over another.
When a word processing program checks the spelling in a document, the program searches for matching words in a dictionary. When a customer enters the title of a book on the Web site of an on-line bookstore, a program on the store’s server searches for the price, reviews, and other information that will help the customer decide for or against the purchase of the book.
When the registrar\’s office publishes the list of courses that the college offers, the office lists the courses in numerical order within departments that it lists alphabetically. Sorting is the key to efficient searches. Students can find the number of seats available in a course or the number of the classroom in which the class will meet quickly because the registrar has listed the courses in order.
An organization can save money by sorting newsletters by the zip codes of the members to which it wants to send the newsletters. The United States Postal Service charges less for postage when the organization sorts mail before bringing it to the post office.
We will study methods of searching and sorting because the solutions to many of the problems that clients present to software engineers require searching through data and/or sorting data. A large fraction of computer programs contain within them functions that search through data or sort data.
Our examination of searching and sorting algorithms will lead us to a deeper understanding of challenges that are common to many kinds of programming problems. Of course, people who have never studied computer science know how to find the smallest element in a collection, find a matching value in a list, and order objects in set from smallest to largest. Searching and sorting are easy. However, putting into words the steps taken in a search or sort can be hard. Computer scientists can describe the procedures precisely.