CPSC 220
Fall 2006
HW 3: Comparisons and Exchanges

1. Most sorting techniques require both comparisons and exchanges. A comparison checks one value against another (e.g., is a[i]>a[j]?). An exchange moves a value from one place to another or exchanges two values (we won't distinguish between these two.) Thus the first pass in Selection Sort will make N-1 comparisons but only one exchange (swapping the first element with the smallest one).

   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