Lab 4: Sorting

Lab Structure

  1. Pick a partner.
  2. Help each other with the code as needed. Do not type for your partner and avoid dictatation, but make sure your partner is able to finish the assignment.
  3. Make sure that your partner understands the quicksort enough to take a test over it.
  4. Put your partner's name with yours in the header of the sort.c file.
  5. If your partner is unable to complete the lab, your maximum grade is a 90%.

Quicksort pp. 279-284

  • Description: The fastest known generic sorting algorithm in practice. Like the mergesort, it is a recursive divide-and-conquer algorithm.
  • Quicksort Algorithm:
    1. Pick any element v. This is called the pivot.
    2. Put all elements less than v on the left of the array. The others go on the right. This is called partitioning.
    3. Recursively quicksort each half of the array.
  • Implementation Details
    • If the number of elements in the array is less than 10, use the insertion sort. (There are several extra error conditions we can avoid by using the insertion sort instead.)
    • Partitioning:
      1. Choose a pivot and move it out of the way. (See below)
      2. Create two counter integers (i and j). Start i at left and j at right-1.
      3. As long as array[i] is less than the pivot, increment i.
      4. Now starting with the other end, as long as j is greater than (or equal to) the pivot, decrement j. At this point, element i and j are both holding elements that are out of position.
      5. Make sure that i is still an index to the left of j. If it isn't, we're done with partitioning. If is, swap elements i and j. (Write a swap function.)
      6. Continue with steps 3-6 as long as i is less than j.
      7. After the partitioning is complete, swap the pivot into the center (element i).
      8. Quicksort elements left through i-1.
      9. Quicksort elements i+1 through right.
      10. The pivot is already in the right position. You are finished.
    • Picking a pivot: You can use the first element in the section to be the pivot. However if the array is partially sorted or reverse sorted, the first element is likely an awful choice. Therefore you should use the median of three approach:
      1. Take the first, middle, and last elements of the section to sort.
      2. Determine which element is the middle of the other two values. That middle value will be the pivot.
      3. Put the smallest element at the leftmost location. It is in the correct location, since we know it is less than the pivot.
      4. Put the largest element on the rightmost location. It is in the correct location, since we know it is greater than the pivot.
      5. Put the middle value at location right-1. We need the pivot out of the way while we sort.
    • Sorting in place: A benefit the quicksort has over the mergesort (in addition to speed) is that it requires no extra memory for sorting, because we sort it in the source array. This approach means that we must keep track of which section of the array we are sorting. We do this by passing the recursive function left and right indexes specifying what section to sort.

Assignment

  1. Copy /users/smatzko/212/public/main.c to use for testing.
  2. Write the quicksort using the starter code below.
    #include <iostream>
    #include <vector>
    #include <string>
    using std::cout;
    using std::endl;
    using std::vector;
    using std::string;

    // Calls the recursive quicksort function
    template<typename T> void quicksort (vector<T> &list);
    template<typename T> void quicksort (vector<T> &list, int left, int right);
    template<typename T> void insertionsort (vector<T> &list);
    template<typename T> void swap (T &first, T &second);
    template<typename T> const T &median3 (vector<T> &list, int left, int right);

    template <typename T>
    void insertionsort (vector<T> &list) {
       int j;
       for (unsigned int i=1; i < list.size(); ++i) {
          T temp = list[i];
          for (j=i; j > 0 && temp < list[j-1]; --j) {
             list[j] = list[j-1];
          }
          list[j] = temp;
       }
    }

    template<typename T>
    const T &median3 (vector<T> &list, int left, int right) {
       int center = (left+right)/2;

       if (list[center] < list[left]) swap (list[left], list[center]);
       if (list[right] < list[left]) swap (list[left], list[right]);
       if (list[right] < list[center]) swap (list[center], list[right]);
       swap (list[center], list[right-1]);
       return list[right-1];
    }
  3. Turn in your code and a Makefile to create a.out.
    Use sendlab.212.302 4 *.cpp *.h Makefile