Lab 4: Sorting
Lab Structure
 Pick a partner.
 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.
 Make sure that your partner understands the quicksort enough to
take a test over it.
 Put your partner's name with yours in the header of the
sort.c file.
 If your partner is unable to complete the lab, your maximum grade is a 90%.
Quicksort pp. 279284
 Description: The fastest known generic sorting algorithm in practice.
Like the mergesort, it is a recursive divideandconquer algorithm.
 Quicksort Algorithm:
 Pick any element v. This is called the pivot.
 Put all elements less than v on the left of the array. The others go on the right.
This is called partitioning.
 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:
 Choose a pivot and move it out of the way. (See below)
 Create two counter integers (
i and j ). Start i at left and j
at right1 .
 As long as
array[i] is less than the pivot, increment i .
 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.
 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.)
 Continue with steps 36 as long as
i is less than j .
 After the partitioning is complete, swap the pivot into the center (element
i ).
 Quicksort elements
left through i1 .
 Quicksort elements
i+1 through right .
 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:
 Take the first, middle, and last elements of the section to sort.
 Determine which element is the middle of the other two values. That middle value will be
the pivot.
 Put the smallest element at the leftmost location. It is in the correct location,
since we know it is less than the pivot.
 Put the largest element on the rightmost location. It is in the correct location,
since we know it is greater than the pivot.
 Put the middle value at location right1. 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
 Copy
/users/smatzko/212/public/main.c to use for testing.
 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[j1]; j) {
list[j] = list[j1];
}
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[right1]);
return list[right1];
}
 Turn in your code and a Makefile to create
a.out .
Use sendlab.212.302 4 *.cpp *.h Makefile
