Page 427 - Introduction to Programming with Java: A Problem Solving Approach

10.8 Sorting an Array
Computers are particularly good at storing large quantities of data and accessing that data quickly. As you learned in the previous section, binary search is an effective technique for finding and accessing data quickly. In order to prepare the data for binary search, the data must be sorted. Sorting data is done not only for binary search purposes. Computers also sort data so that it’s easier to display in a user-friendly fashion. If you look at the e-mails in your inbox, aren’t they normally sorted by date with the most recent e-mail first? Most e-mail organizers allow you to sort your e-mails using other criteria as well, such as using the “from” person or using the size of the e-mail. In this section, we describe the basics of how sorting is performed. We first present a sorting algorithm, and we then present its implementation in the form of a program that sorts the values in an array.
Selection Sort
There are many different sorting algorithms with varying degrees of complexity and efficiency. Frequently, the best way to solve a problem on a computer is the way a human would naturally solve the problem by hand. To illustrate this idea, we’ll show you how to convert one of the common human card-sorting algo- rithms to a Java sorting program.
If you’re sorting cards in a card game, you probably use the Selection Sort algorithm. Assume that you’re sorting smallest cards first. You search for and select the smallest card and move it to the small-card side of the card group. The small-card side of the card group is where you keep the cards that have been sorted already. You then search for the next smallest card, but in so doing, you look only at cards that are in the unsorted portion of thAe cpardaggrouop. YoPuDmoFve thEe fnouhndacanrdctoethersecond position on the small-card side of the card group. You repeat the search-and-move process until there are no more cards left in the un- sorted portion of the card group.
As a first step in implementing the selection sort logic, let’s examine a pseudocode solution. Above, we said to “repeat the search-and-move process.” Whenever there’s a repetition, you should think about using a loop. The following algorithm uses a loop for repeating the search-and-move process. Note how i keeps track of where the search starts. The first time through the loop, the search starts at the first element (at index 0). The next time, the search starts at the second position. Each time through the loop, you find the smallest value and move it to the sorted portion of the list (the i tells you where in the list you want the smallest value to go).
for (i ← 0; i < list’s length; i􏰃􏰃)
find the smallest value in the list from list[i] to the end of the list swap the found value with list[i]
A picture is worth a thousand words, so we provide a figure (10.14) that shows the Selection Sort algorithm in action. The five pictures show the different stages of a list being sorted using the Selection Sort algorithm. The list’s white portions are unsorted. The original list at the left is all white, indicating that it is entirely unsorted. The list’s shaded portions are sorted. The list at the right is all shaded, indicating that it is entirely sorted. The bidirectional arrows show what happens after a smallest value is found. The smallest value (at the bottom of the bidirectional arrow) gets swapped up to the top of the unsorted portion of the list. For ex- ample, in going from the first picture to the second picture, the smallest value, 􏰂3, gets swapped up to 5’s position at the top of the unsorted portion of the list.
Now let’s implement a Java version of the Selection Sort algorithm. You can use either an instance method or a class method. In the previous section, we implemented binary search with a class method. For additional practice, we’ll do the same here for selection sort. By implementing selection sort with a class
10.8 Sorting an Array 393