Java Reference
In-Depth Information
Chapter 1
Sorting, Searching, and Merging
In this chapter, we will explain the following:
How to sort a list of items using selection sort
How to sort a list of items using insertion sort
How to add a new item to a sorted list so that the list remains sorted
How to sort an array of strings
How to sort related (parallel) arrays
How to search a sorted list using binary search
How to search an array of strings
How to write a program to do a frequency count of words in a passage
How to merge two sorted lists to create one sorted list
1.1 Sorting an Array: Selection Sort
S orting is the process by which a set of values are arranged in ascending or descending order. There are many reasons
to sort. Sometimes we sort in order to produce more readable output (for example, to produce an alphabetical listing).
A teacher may need to sort her students in order by name or by average score. If we have a large set of values and we
want to identify duplicates, we can do so by sorting; the repeated values will come together in the sorted list.
Another advantage of sorting is that some operations can be performed faster and more efficiently with sorted
data. For example, if data is sorted, it is possible to search it using binary search—this is much faster than using a
sequential search. Also, merging two separate lists of items can be done much faster than if the lists were unsorted.
There are many ways to sort. In this chapter, we will discuss two of the “simple” methods: selection and insertion
sort. In Chapter 9, we will look at more sophisticated ways to sort. We start with selection sort.
Consider the following list of numbers stored in a Java array, num :
 
Search WWH ::




Custom Search