Insertion Sort

  public void insertionSort(T[] items) {

    for (int i = 1; i < items.length; i++) { // Insert i'th record
      for (int j = i; (j > 0) && (items[j].compareTo(items[j - 1]) < 0); j--) {
        swap(items, j, j - 1);
      }
    }
  }

• Trace the execution of insertion sort as it sorts the following sequence of records. In this case, the key is the number, and the superscript indicates the record.

  \([7^A, 1^B, 11^C, 7^D, 1^E, 1^F]\)

  After first iteration of outer loop:

  \([\mathbf{1^B, 7^A}, 11^C, 7^D, 1^E, 1^F]\)

  
  
  
  

• Was insertion sort stable in this case?

  
  
  
  

• If so, is insertion sort always stable? Justify your answer.

  
  
  
  

Selection Sort

public void selectionSort(T[] items) {

  for (int i = 0; i < items.length - 1; i++) {       // Select i'th biggest record
    int bigindex = 0;                                // Current biggest index
    for (int j = 1; j < items.length - i; j++) {     // Find the max value
      if (items[j].compareTo(items[bigindex]) > 0) { // Found something bigger
        bigindex = j; // Remember bigger index
      }
    }
    swap(items, bigindex, items.length - i - 1);     // Put it into place
  }
}

• Trace the execution of selection sort as it sorts the following sequence of records. In this case, the key is the number, and the superscript indicates the record.

  \([7^A, 1^B, 11^C, 7^D, 1^E, 1^F]\)

  
  
  
  
  
  
  
  
  

• Was selection sort stable in this case?
  
  
  

• If so, is selection sort always stable? Justify your answer.
  
  
  

Comparing Sorts

• On average, insertion sort is faster than selection sort by a constant factor. Why?

  
  
  

• Provide an example of a length-three worst case-input for insertion sort. How many comparisons will insertion sort perform on your input? How many swaps?

  
  
  
  
  
  
  

• For the input you created above, how many comparisons will selection sort perform? How many swaps?
  
  
  

• Our textbook presents a worst-case analysis of both insertion sort and selection sort through an illustration of stacked boxes. Instead of this approach, analyze the sorts above by developing summations that describe the number of comparisons performed. Solve the summations.
  
  
  
  
  
  
  
  

• Here is the implementation of the swap operation used by the two algorithms above:

  public void swap(T[] items, int i, int j) {
     T tmp = items[i];
     items[i] = items[j];
     items[j] = tmp;
  }

  Notice that each swap operation requires three assignments. For this reason, most insertion sort implementations don’t call a swap method. Instead, they follow the following steps for each sorting pass:

  Place the item being inserted into a temporary variable.
  
  Iterate to the left, shifting each element to the right if it is
  greater than the element being inserted. (This requires only one
  assignment per item.)
  
  Place the item into its final sorted position.

  Rewrite the insertion sort algorithm to use this approach.