Lab: Selection and Insertion Sorts

Introduction

Many applications require the maintenance of ordered data. In Java (and many other languages), such data often are structured in an array (or vector). The readings for the Selection Sort and the Insertion Sort provide considerable detail on both the selection sort and the insertion sort.

The Selection Sort

as noted in the reading for the selection sort.,xs the main code for this sorting algorithm is:

 for (k = n; k ≥ 1; k--} {
     //find the index of the maximum array element in A[0], ..., A[k]
     int maxIndex = 0;  // as the search begins, the largest is at index 0
     for (index = 1; index ≤ k; index++) {   //proceed through the array
         if (A[maxIndex] < A[index]) {       // update maxIndex when
            maxIndex = index;                // something bigger is found
          }
     }

     //swap largest with A[k]
     temp = A[k];
     A[k] = A[maxIndex];
     A[maxIndex] = temp;

1. In your own words, explain how ths code works. Your explanation should include the following.

   1. What is the motivating idea for this algorithm?
   2. Why does the outer loop go from n to 1 rather than to 0? What would happen if the outer loop did go to 0?
   3. Why does the algorithm keep track of the index maxIndex of the largest element rather than the largest value itself?

2. Insert this code into a method SelectionSort, and test it within a program for several different starting arrays.

   • If no errors are encountered, explain why your testing is adequate to conclude that the code works in all cases.
   • If errors are detected, explain them and indicate how they might be corrected.

3. The reading discussed putting the largest element in the array at A[n], the second largest at A[n-1], the third largest at A[n-2], etc. An analogous approach would be to put the smallest element into A[0], the next smallest at A[1], the third smallest at A[2], etc.

   Write and test an alternative method SelectionSortAlt following this alternative approach.

The Insertion Sort (Review)

The insertion sort assumes that the first part of an array is ordered and then adds successive items to this array segment until the entire array is sorted.

A main helper method adds add one item to an ordered array segment. More specifically, suppose items A[0], ..., A[k-1] are ordered in array A. The following code inserts an item into the array, so that items A[0], ..., A[k] become ordered:

int i = k-1;
while ((i >= 0) && a[i] > item){
   a[i+1] = a[i];
   i--;
}
a[i+1] = item;

4. Consider the array

   

   Review the steps in the above code for this array segment with k-1 = 7 and with item having the value 17. Explain what happens and why.

Using this basic insertion step, an array A can be sorted iteratively. This outline gives rise the the following code, called an insertion sort.

public static void insertionSort (int [] a) {
// method to sort using the insertion sort
   for (int k = 1; k < a.length; k++) {
      int item = a[k];
      int i = k-1;
      while ((i >= 0) && a[i] > item){
         a[i+1] = a[i];
         i--;
      }
      a[i+1] = item;
   }
}

5. Write a few sentences explaining in your own words how this code works.

6. The code given sorts the array with numbers in ascending order. Revise and test the code, so that the numbers at the end will be in descending order. (Make as few changes as possible for this step.)

Broader View

7. Review Class InsertionSortProc1.java. Copy this to Eclipse, and run it with several different arrays.

   1. Does this code properly sort any array of integers? If not, how could the code be corrected? Explain.
   2. Does this code implement a Selection Sort, an Insertion Sort, or something else? Explain.

8. Repeat Step 7 for Class InsertionSortProc2.java.

9. Repeat Step 7 for Class InsertionSortProc3.java.

created 24 April 2001 revised 28 April 2006 revised 11-13 March 2012 revised 2-3 November 2018 revised and reorganized 23-24 January 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.