CPSC 220
Fall 2005
HW 3: More Bubblesort and Quicksort

  1. As we have discussed, most sorting techniques require both comparisons and exchanges. Fill in the tables below to give the big-O complexities of Selection Sort, Insertion Sort, and Bubble Sort for each of these operations on sorted and reverse-sorted arrays.

    1. For an already sorted array of N elements.

      Sort Comparisons Exchanges
      Selection Sort    
      Insertion Sort    
      Bubble Sort    

    2. For a reverse-sorted array of N elements.

      Sort Comparisons Exchanges
      Selection Sort    
      Insertion Sort    
      Bubble Sort    

  2. Consider the array a of integers below:
    6  4  8  3  7  9  1  4  5    
    
    Assuming you have called method quickSort(a, 0, 8), using quickSort as written on page 352 of L&C, show the following: