Searching and Sorting - A Concise and Practical Introduction to Programming Algorithms in Java - page 127

6
Searching and Sorting
6.1 Overview
We have quickly sketched in Chapter 4.7 the sequential and dichotomic/bisec-
tion search strategies to answer element membership queries: Does an element
already belong to the data-set or not? In this chapter, we further describe the
generic framework for inserting/deleting or modifying attributes of elements of
a data-set. We revisit the linear sequential and logarithmic bisection searches
on sets of complex data-structured elements: sets of objects. Since the bisection
search requires arrays to be totally ordered, and since raw arrays of elements
are very unlikely to be already sorted beforehand, we then present two methods
for sorting data-sets:
- (1) The selection sort , which iteratively selects the current smallest element
of remaining sub-arrays, and
- (2) The quicksort , which recursively sorts the arrays by partitioning elements.
Finally, to conclude this chapter, we present the hashing method that is often
used in practice to find elements in almost constant time, and summarize the
time complexity of these various methods.