ABSTRACT
Fundamental concepts Worst-case, average-case, and best-case time complexity; space complexity
Programming skills Adopt and use search algorithms such as linear search and binary search Adopt and use sort algorithms such as selection sort, insertion sort, and bubble sort Empirical method of measuring the performance of an algorithm and compare it with known time complexity measures
Searching and sorting are the two most common tasks in data processing. Can you imagine a telephone directory without names listed in sorted order? Sorting is also quite useful for ordinary folks such as Ms. Smart and Mr. Grace. If Ms. Smart needs to identify all sales personnel in the top 10 percentile, then she needs to sort the list of sales personnel based on their sales. Similarly, if Mr. Grace needs to identify all students in the class in the bottom 25 percentile, then he needs to sort the list of students based on their cumulative test scores. A sorting algorithm permutes or rearranges the elements of a collection either in an ascending or a descending order. Many sorting algorithms are known. In this chapter, you will be introduced to three diff erent sorting algorithms: selection sort, insertion sort, and bubble sort. Once you have a sorted list, searching for an item becomes quite effi cient. Th is chapter presents three search algorithms: linear search on an unsorted array, linear search on a sorted array, and binary search on a sorted array. All these algorithms are illustrated using int array for simplicity. However, once you master the algorithm, it is quite easy to adapt to another situation. In Case Study 10.1, Mr. Grace’s grade sheet demonstrates how easy it is to adopt a sort algorithm to use in the case of array of objects.
