## CPSC 220Fall 2005HW 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.