| Lab Due: | Mon, Dec. 4 by midnight |
| Turn-in: | your two versions of the program: qsort_vec_it.cpp and qsort_list.cpp |
For this lab, you will be modifying a version of the quicksort algorithm to use iterators instead of array indexing. An initial implementation is provided using the C++ vector class, using array indexing, and you will first convert that version to use vector iterators, and then create a second version using the list class and list iterators.
We will discuss the algorithm for quicksort on Monday, prior to the lab.
An initial version of the quicksort code, using the vector class and array-based indexing, is provided for you: qsort_vec.cpp.
Your basic task is to modify the array-based implementation of the code, converting it to a vector-based implementation. In doing so, you will generate two new versions that use iterators, one for the vector class, and one for the list class:
To aid you in understanding the current version, a boolean debug field has been provided, which when turned on (set to true), prints out a lot of information about the quicksort sorting process. You'll need to get comfortable with how the current version works in order to convert to the new version.
Before you start modifying the existing version, copy it over to qsort_vec_it.cpp so that you can keep the original version intact, while modifying the new copy to create your iterator-based implementation.
Beyond the usual changes for converting array-based indexing to iterator access, such as converting the int indices to iterators, and the access method from at(i) or [i] to *it, you'll also need to make some changes some of the conditions being tested to ensure that the left and right pointers stop incrementing/decrementing at the appropriate times. Likewise, you'll need to make modifications or add conditions to ensure that the final swap (swapping the pivot value to correct location based on the list partitioning) happens correctly...
The key part of this conversion is in the fact that list iterators are more limiting than vector iterators, in that they only allow incrementing (++), decrementing (--), and comparison for equality (==) and inequality (!=), and do not allow some of the other capabilities of vector iterators, such as relational comparisons like less than and greater than. Therefore, the conversion to using iterators with the list class is more challenging, and you'll need to be even more careful in ensuring that the left and right pointer movements, and the final swap, occur correctly.