6.7. Searching Arrays

[Page 188 ( continued )]

6.8. Sorting Arrays

Sorting, like searching, is a common task in computer programming. It would be used, for instance, if you wanted to display the grades from Listing 6.2 in alphabetical order. Many different algorithms have been developed for sorting. This section introduces two simple, intuitive sorting algorithms: selection sort and insertion sort .

6.8.1. Selection Sort

Suppose that you want to sort a list in ascending order. Selection sort finds the largest number in the list and places it last. It then finds the largest number remaining and places it next to last, and so on until the list contains only a single number. Figure 6.12 shows how to sort a list { 2 , 9 , 5 , 4 , 8 , 1 , 6 } using selection sort.

Figure 6.12. Selection sort repeatedly selects the largest number and swaps it with the last number in the list.

(This item is displayed on page 189 in the print version)

You know how the selection sort approach works. The task now is to implement it in Java. Beginners find it difficult to develop a complete solution on the first attempt. Start by writing the code for the first iteration to find the largest element in the list and swap it with the last element, and then observe what would be different for the second iteration, the third, and so on. The insight this gives will enable you to write a loop that generalizes all the iterations.

The solution can be described as follows :

    for   (   int   i = list.length -   1   ; i >=   1   ; i--) { select the largest element in list[0..i]; swap the largest with list[i], if necessary;  // list[i] is in its correct position   // The next iteration apply on list[0..i-1]  }  

Listing 6.8 implements the solution.

Listing 6.8. SelectionSort.java

(This item is displayed on pages 188 - 189 in the print version)

 1   public class   SelectionSort { 2  /** The method for sorting the numbers */  3   public static void   selectionSort(   double   [] list) { 4    for   (   int   i = list.length -   1   ; i >= 1; i--)  5  // Find the maximum in the list[0..i]  6   double   currentMax = list[     ]; 7   int   currentMaxIndex =     ; 

---

[Page 189]

 8 9  {   for   (   int   j =   1   ; j <= i; j++) {  10   if   (currentMax < list[j]) { 11 currentMax = list[j]; 12 currentMaxIndex = j; 13 } 14 } 15 16  // Swap list[i] with list[currentMaxIndex] if necessary;  17   if   (currentMaxIndex != i) { 18 list[currentMaxIndex] = list[i]; 19 list[i] = currentMax; 20 } 21 } 22 } 23 } 

---

[Page 190]

The selectionSort(double[] list) method sorts any array of double elements. The method is implemented with a nested for loop. The outer loop (with the loop control variable i ) (line 4) is iterated in order to find the largest element in the list, which ranges from list[0] to list[i] , and exchange it with the current last element, list[i] .

The variable i is initially list.length “1 . After each iteration of the outer loop, list[i] is in the right place. Eventually, all the elements are put in the right place; therefore, the whole list is sorted.

Please trace the method with the following statements:

 selectionSort(   new   double[]{   2   ,   1   }); selectionSort(   new   double[]{   2   ,   3   ,   1   }); selectionSort(   new   double[]{   1   ,   2   ,   1   }); 

6.8.2. (Optional) Insertion Sort

Suppose that you want to sort a list in ascending order. The insertion-sort algorithm sorts a list of values by repeatedly inserting a new element into a sorted sublist until the whole list is sorted. Figure 6.13 shows how to sort a list { 2 , 9 , 5 , 4 , 8 , 1 , 6 } using insertion sort.

Figure 6.13. Insertion sort repeatedly inserts a new element into a sorted sublist.

The algorithm can be described as follows:

   for   (   int   i =   1   ; i < list.length; i++) {  insert list[i] into a sorted sublist list[0..i-1] so that   list[0..i] is sorted.  } 

To insert list[i] into list[0..i-1] , save list[i] into a temporary variable, say currentElement . Move list[i-1] to list[i] if list[i-1] > currentElement , move list[i-2] to list[i-1] if list[i-2] > currentElement , and so on, until list[i-k] <= currentElement . Assign currentElement to list[i-k+1] . For example, to insert 4 into { 2 , 5 , 9 } in Step 3 in Figure 6.13, move list[2] ( 9 ) to list[3] since 9 > 4 , move list[1] (5) to list[2] since 5 > 4 . Finally, move currentElement (4) to list[1] , as shown in Figure 6.14.

---

[Page 191]

Figure 6.14. A new element is inserted into a sorted sublist.

The algorithm can be expanded and implemented in Listing 6.9.

Listing 6.9. InsertionSort.java

 1   public class   InsertionSort { 2  /** The method for sorting the numbers */  3   public static void   insertionSort(   double   [] list) { 4   for   (   int   i =   1   ; i < list.length; i++) { 5  /** insert list[i] into a sorted sublist list[0..i-1] so that  6  list[0..i] is sorted. */  7   double   currentElement = list[i]; 8   int   k; 9   for   (k = i -   1   ; k >=     && list[k] > currentElement; k ” ”) { 10 list[k +   1   ] = list[k]; 11 } 12 13  // Insert the current element into list[k+1]  14 list[k + 1] = currentElement; 15 } 16 } 17 } 

The insertionSort(double[] list) method sorts any array of double elements. The method is implemented with a nested for loop. The outer loop (with the loop control variable i ) (line 4) is iterated in order to obtain a sorted sublist, which ranges from list[0] to list[i] . The inner loop (with the loop control variable k ) inserts list[i] into the sublist from list[0] to list[i-1] .

Please trace the method with the following statements:

 insertionSort(   new double   []{   2   ,   1   }); insertionSort(   new double   []{   2   ,   3   ,   1   }); insertionSort(   new double   []{   1   ,   2   ,   1   });