If we handed you a set of index cards with names and asked you to put them in order by name, you would probably go through the cards looking for the name that comes first in the alphabet. You would then put that card as the first in a new stack. How would you determine which card comes first? You might turn the first card sideways to remember it. If you found one that comes before the turned card, you could turn the first card back and turn the new “first” card to remember it. When you have examined all the cards, the one that is turned up is the first one. You pull it out to start the sorted deck of cards. This process would continue until all the index cards have been moved to the new stack.

The selection sort algorithm is probably the easiest because it mirrors how we would sort a list of values if we had to do it by hand. Our deck of index cards is an array of names. The new deck is an array of sorted names. We remove items from the first and put them into successive places in the second. We remember the smallest so far by saving its position in a temporary variable.

This algorithm is simple, but it has one drawback: It requires space for two complete decks (arrays). Although we have not talked about memory space considerations, this duplication is clearly wasteful. A slight adjustment to this by-hand approach does away with the need to duplicate space, however. As you move the smallest item to the new array, a free space opens up where it used to be. Instead of writing this name on a second list, we can exchange it with the name currently in the position where the new name should go. This “by-hand list” is represented in an array.

Let’s look at an example—sorting the five-element array shown in FIGURE 7.11. Because of this algorithm’s simplicity, it is usually the first sorting method that students learn.

Let’s visualize the array as containing two parts: the unsorted part (not shaded) and the sorted part (shaded). Each time we add an item into its proper place, we are shrinking the unsorted part and extending the sorted part. Sorting begins with all of the items in the unsorted part and ends with all of the items in the sorted part. Here is the algorithm written to mirror this visualization:

This algorithm includes only three abstract steps (colored in red): determining when the array is sorted, finding the index of the smallest element, and swapping the contents of two places. In moving from Figure 7.11(d) to 7.11(e), we added the last two items to the shaded part of the array. This is always the case because when the smaller of the last two items is put into its proper place, the last item is also in its proper place. Thus the loop continues as long as firstUnsorted is less than the length of array 2 1.

How would you find the name that comes first in the alphabet in the unsorted portion of the list if you were sorting it by hand? You see (and mentally record) the first one, and then you scan down the list (turning index cards) until you see one that comes before the first one. You remember this smaller one and continue scanning the list for a name that comes before this one in the alphabet. The process of remembering the smallest so far until you find a smaller one is repeated until you reach the end of the list. This by-hand algorithm is exactly the one we use here, except that we must remember the index of the smallest item because we will swap it with the item in the firstUnsorted position. Stated in terms of our list, we look for the smallest item in the unsorted portion, which runs from firstUnsorted through length – 1.

How many glasses does it take to swap the contents of two glasses? Three. You need a glass to temporarily hold the contents of one glass while you pour the contents of the other glass into the first. Swapping the contents of two places in memory is exactly the same problem. The swap algorithm must have the indexes of the two items to be swapped.

The bubble sort is a selection sort that uses a different scheme for finding the minimum value. Starting with the last array element, we compare successive pairs of elements, swapping them whenever the bottom element of the pair is smaller than the one above it [FIGURE 7.12(a) ]. In this way, the smallest element “bubbles up” to the top of the array. Each iteration puts the smallest unsorted item into its correct place using the same technique, but it also changes the locations of the other elements in the array [FIGURE 7.12(b)].

Before we write this algorithm, we must make an observation: The bubble sort is a very slow sorting algorithm. Sorting algorithms are usually compared based on the number of iterations it takes to sort an array, and this approach takes one iteration for every item in the array except the last. Also, during each algorithm a lot of swapping goes on. Why, then, do we bother to mention the bubble sort if it is so inefficient? Because a very slight change in the sorting algorithm makes it an excellent choice to use in certain circumstances. Let’s apply the algorithm to an already sorted array. See the rightmost column in Figure 7.12(b).

We compare Phil with John and do not swap them. We compare John with Jim and do not swap them. We compare Jim with Bob and do not swap them. We compare Bob with Al and do not swap them. If no values are swapped during an iteration, then the array is sorted. We set a Boolean variable to FALSE before we enter the loop and set it to TRUE if a swap occurs. If the Boolean variable is still FALSE, then the array is sorted.

Compare the processing of the bubble sort to the selection sort on an already sorted array. The selection sort algorithm gives us no way to determine whether the array is sorted; therefore, we will go through the entire algorithm.

If you have only one item in the array, it is sorted. If you have two items, you can compare and swap them if necessary. Now the first two are sorted with respect to themselves. Take the third item and put it into its place relative to the first two. Now the first three items are sorted with respect to one another. The item being added to the sorted portion can be bubbled up as in the bubble sort. When you find a place where the item being inserted is smaller than the item in the array, you store the item there. current is the item being inserted into the sorted portion. See FIGURE 7.13.

At each iteration of a selection sort, one more item is put into its permanent place. At each iteration of an insertion sort, one more item is put into its proper place with respect to those above it.