Previous: 10.1 Finding a Data Item - The Search Problem
Up: 10 Sorting and Searching
Next: 10.3 Binary Search
Previous Page: 10.1 Finding a Data Item - The Search Problem
Next Page: 10.2.1 Selection Sort

10.2 Improving Search - Sorting the Data

As we mentioned above, linear search may be useful when the number of elements is small; however, when there are many data items in the array, linear search may require a long time to find the element matching the key. In the case where such an element is not in the data base, we must search the entire collection to find that out. Consider the phone book again. When we want to look up someone's phone number, we do not start at the beginning of the book and look line by line until we find the name. Instead, we make use of the fact that the data items are sorted by name in the phone book. (Of course, if we had a phone number and wanted to find the name, we would have to resort to linear search - we do not often do that).

Before we develop an algorithm to conduct a more efficient search of sorted data, we first describe several algorithms which will sort an array of data. There are numerous ways to sort data, some more suitable than others for different applications. In this section we will describe three different standard algorithms: selection sort, bubble sort, and insertion sort.

• 10.2.1 Selection Sort
• 10.2.2 Bubble Sort
• 10.2.3 Insertion Sort