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:
   • A trace of the first call to findPartition. Show the values of partitionelement, left, right, data[left] and data[right] as you proceed through the while loop and its two inner loops.

   • The value of indexofpartition when findPartition returns.

   • The parameters that are passed to the first top-level recursive call to quickSort.

   • The parameters that are passed to the second top-level recursive call to quickSort.