< Free Open Study > |
After studying this chapter, you should be able to
Design and implement the following sorting algorithms:
Straight selection sort
Bubble sort (two versions)
Insertion sort
Merge sort
Heap sort
Radix sort
Compare the efficiency of the sorting algorithms, in terms of Big-O complexity and space requirements
Discuss other efficiency considerations: sorting small numbers of elements, programmer time, and sorting arrays of large data elements
Sort on several keys
Discuss the performances of the following search algorithms:
Sequential search of an unsorted list
Sequential search of a sorted list
Binary search
Searching a high-probability sorted list
Define the following terms:
Hashing
Rehashing
Collisions
Linear probing
Clustering
Design and implement an appropriate hashing function for an application
Design and implement a collision-resolution algorithm for a hash table
Discuss the efficiency considerations for the searching and hashing algorithms, in terms of Big-O notation
At many points in this book, we have gone to great trouble to keep lists of elements in sorted order: student records sorted by ID number, integers sorted from smallest to largest, words sorted alphabetically. The goal of keeping sorted lists, of course, is to facilitate searching. Given an appropriate data structure, a particular list element can be found more quickly if the list is sorted.
In this chapter, we examine strategies for sorting and searching, two tasks that are fundamental to a variety of computing problems. In fact, we challenge you to look back at the programs you have written so far. Are there any that do not include a sort or a search?
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |