CPSC 220
Fall 2005
HW 3: More Bubblesort and Quicksort
 As we have discussed, most sorting techniques require both
comparisons and exchanges. Fill in the tables below
to give the bigO complexities of Selection Sort, Insertion Sort, and
Bubble Sort for each of these operations on sorted and reversesorted arrays.

For an already sorted array of N elements.
Sort
 Comparisons
 Exchanges

Selection Sort



Insertion Sort



Bubble Sort




For a reversesorted array of N elements.
Sort
 Comparisons
 Exchanges

Selection Sort



Insertion Sort



Bubble Sort



 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 toplevel recursive call
to quickSort.
 The parameters that are passed to the second toplevel recursive call
to quickSort.