Quicksort computer science c++

Assg 05: Quicksort

COSC 2336 Data Structures

Objectives

• Practice writing functions

• Practice writing recursive functions.

• Learn about Analysis of algorithms and O(n log n) sorts

Description

In this assignment we will be implementing one of the most popular sorting algorithms used in libraries (like the C++ STL library, and the UNIX qsort function) to provide basic sorting abilities, the Quicksort algorithm. I would recommend that you at least read section 7.5 from our supplemental Shaffer textbook on Quicksort, if not sections 7.1-7.5 talking about three well known O(n log n) sorting algorithms, and the 3 O(n2) algorithms we discussed last week.

Quicksort, when properly implemented, is very attractive because it pro- vides a way to do a fast sort completely in-place (without having to allocate additional memory to do the sort, beyond a single value needed when swap- ping two values in the list being sorted). In the worst case, Quicksort is actually O(n2), no better than bubble sort. But this worse case only occurs when every pivot selected is the wort possible, and does not divide the list at all. This is very unlikely to happen, unless you know how the pivot is selected, and specifically design the input list to always choose the worst possible pivot. On average the cost of Quicksort is O(n log n), and it is usually very likely that average case performance will result when lists to be sorted are relatively random.

The most direct implementation of Quicksort is as a recursive algorithm. Quicksort is an example of a divide and conquer approach to solving the problem of sorting the list. We are given a list of items, A and indexes left

1

and right that indicate a sub-portion of the list to be sorted. left and right indicate the actual indexes, so if the list is a regular C array of integers, and the array is of size 10

int left; int right; const inst SIZE = 10; int A[size];

Then to sort the whole list we set left = 0 and right = 9 to initially call the Quicksort function:

left = 0; right = size-1; quicksort(A, left, right);

Conceptually the steps of the Quicksort algorithm are as follows:

1. if list size is 0 or 1 (left <= right) return (lists of this size are sorted by definition).

2. Choose a pivot value and swap the pivot value to the end of the list swap(pivotIndex, right)

3. Partition the list. Partitioning means all values less than the pivot value should end up on the left of the list, and all values greater will be on the right. The first index k where a value >= to the pivot value is at indicates the new left and right side sub-lists.

4. Swap the pivot value to its correct position k swap(k, right)

5. Recursively call Quicksort on the new left and right sub-lists

• quicksort(A, left, k-1)

• quicksort(A, k+1, right)

Most of the real work happens in the function/code to partition the list. The partitioning of the list, for Quicksort to be an in-place sort, must work by swapping values in-place in the list of items. All values smaller than the pivot value must end up on the left side, and all values greater on the right. The algorithm to partition the list is traditionally done with these steps:

2

1. do a linear search from the left of list, stop at first value on left that is >= pivot

2. do a linear search from the right of list, stop at first value that is < than the pivot.

3. swap(left, right) assuming you were incrementing left and decre- menting right to point to indexes of values that are on wrong sides

4. if left < right goto 1

Conceptually we search from both ends of the list, and when we find values that are on wrong sides with respect to the pivot value, we swap them. Eventually the search from both ends will meet somewhere. The location where they meet should be the index of the first value that is >= to the pivot (going from the left side of the list). This is the index where the pivot value should actually go in the list, because all values before this are smaller than the pivot, and all values at or after are greater than the pivot. Thus at the end of partitioning the list on some pivot value, we are able to swap 1 value each time to its correct final position in the list. But the values to the left and right will not be sorted, thus we call Quicksort recursively on these sub-lists to get them sorted.

In order to help you implement your own version of Quicksort, we have broken the problem down into useful sub-functions. If you implement the sub-functions as specified, in the order given, the final implementation of the Quicksort function is relatively straight forward, using these smaller func- tions.

For this assignment you need to perform the following tasks.

1. Write a function called swapListValues(). This functions takes an array of integers as its first parameter, and two indexes (the left and right indexes). This function does not return a value explicitly. Recall arrays are passed by reference. As the name implies, the two values in the array at the indicated left and right indexes are to be swapped, and since the array is passed by reference, after returning they will be swapped for the caller of this function.

2. Write a function called findAndSwapPivot(). This function takes the same 3 parameters, an array of integers, and two indexes indicating the left and right sides of a sub-portion of the list. The function should find the value in the middle of the left and right ends, which will be chosen as the pivot. The function should use the previous swapListValues()

3

function to swap the chosen pivot value to the end of the list of integers. This function returns a value. This is different from how the textbook implements the find pivot function. Our function should return the actual pivot value that was chosen (not the pivotIndex, which we know should be the last index of the sub-list after calling this function).

3. Write a function called partitionList(). This will implement the al- gorithm described preciously. This functions takes the 3 same param- eters for the previous functions, an integer array, and left and right indexes for the sub-portion of the list we are currently partitioning. In addition, this function takes a fourth parameter, the pivot value). This function should make use of the swapListValues() function de- fined previously when swapping values in-place in the list of integers. When this function is called, the pivot has been swapped to the end of the sub-portion of the list, so the right index will be one less than this. This function needs to correctly return the index, described as k above, where the pivot value should actually go. At the end, the location where the left search and right search meet will be this index, the final location found for the pivot value.

4. Finally write a function called quickSort() using the described algo- rithm above. This function will use all of the 3 previous functions to do its work. If implemented correctly, there is almost nothing to be done in this function besides calling the other 3 functions, and recursively calling itself (except to check for the base case of your recursion).

You will again be given 3 starting template files like before, an assg- 05.cpp file of tests of your code, and a QuickSort.hpp and QuickSort.cpp header and implementation file. As before, you should practice incremental development, and uncomment the tests in the assg-05.cpp file one at a time, and implement the functions in the order specified. If you implement your code correctly and uncomment all of the tests, you should get the following correct output:

Test swapListValues() ------------------------------------------ swapListValues() test 1, swap 2 values

expected: List length: 2 [10, 5] actual : List length: 2 [10, 5]

swapListValues() test 2, same index expected: List length: 2 [8, 6]

4

actual : List length: 2 [8, 6]

swapListValues() test 3, swap 2 values from inside of list expected: List length: 12 [2, 7, 6, 3, 8, 4, 2, 9, 5, 8, 9, 1] actual : List length: 12 [2, 7, 6, 3, 8, 4, 2, 9, 5, 8, 9, 1]

swapListValues() test 4, reverse the previous swap expected: List length: 12 [2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1] actual : List length: 12 [2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1]

swapListValues() test 5, swap with index 0 expected: List length: 12 [4, 7, 9, 3, 8, 2, 2, 9, 5, 8, 6, 1] actual : List length: 12 [4, 7, 9, 3, 8, 2, 2, 9, 5, 8, 6, 1]

swapListValues() test 6, swap with last index expected: List length: 12 [4, 7, 9, 3, 8, 2, 1, 9, 5, 8, 6, 2] actual : List length: 12 [4, 7, 9, 3, 8, 2, 1, 9, 5, 8, 6, 2]

Test findAndSwapPivot() ---------------------------------------- findAndSwapPivot() test 1, basic test

expected: List length: 3 [5, 8, 3] expected pivot: 3

actual: List length: 3 [5, 8, 3] actual pivot: 3

findAndSwapPivot() test 2, test list size 1 expected: List length: 1 [5]

expected pivot: 5 actual: List length: 1 [5]

actual pivot: 5

findAndSwapPivot() test 3, bigger list with even number of values expected: List length: 10 [5, 2, 8, 7, 8, 9, 1, 4, 5, 3]

expected pivot: 3 actual: List length: 10 [5, 2, 8, 7, 8, 9, 1, 4, 5, 3]

actual pivot: 3

findAndSwapPivot() test 4, bigger list with odd number of values expected: List length: 15 [5, 2, 8, 7, 3, 9, 1, 18, 5, 8, 10, 11, 15, 22, 42]

5

expected pivot: 42 actual: List length: 15 [5, 2, 8, 7, 3, 9, 1, 18, 5, 8, 10, 11, 15, 22, 42]

actual pivot: 42

Test partitionList() ------------------------------------------- partitionList() test 1, basic test

expected: List length: 10 [1, 3, 4, 2, 9, 6, 7, 8, 8, 5] expected pivot: 4

actual: List length: 10 [1, 3, 4, 2, 9, 6, 7, 8, 8, 5] actual pivot: 4

partitionList() test 2, bigger test and some duplicates of the pivot expected: List length: 15 [4, 7, 6, 6, 19, 18, 12, 15, 10, 10, 12, 13, 11, 17, 10]

expected pivot: 4 actual: List length: 15 [4, 7, 6, 6, 19, 18, 12, 15, 10, 10, 12, 13, 11, 17, 10]

actual pivot: 4

partitionList() test 3, everything is smaller than pivot value expected: List length: 6 [4, 3, 7, 6, 5, 10]

expected pivot: 5 actual: List length: 6 [4, 3, 7, 6, 5, 10]

actual pivot: 5

partitionList() test 4, everything is bigger than pivot value expected: List length: 6 [4, 3, 7, 6, 5, 2]

expected pivot: 0 actual: List length: 6 [4, 3, 7, 6, 5, 2]

actual pivot: 0

partitionList() test 5, small list that needs a swap expected: List length: 3 [2, 8, 4]

expected pivot: 1 actual: List length: 3 [2, 8, 4]

actual pivot: 1

partitionList() test 6, list of size 1 (and pivot value) expected: List length: 2 [8, 4]

expected pivot: 0 actual: List length: 2 [8, 4]

6

actual pivot: 0

partitionList() test 7, list of size 1, pivot value is larger expected: List length: 2 [8, 12]

expected pivot: 1 actual: List length: 2 [8, 12]

actual pivot: 1

partitionList() test 8 (sort by hand) after first partition: List length: 5 [5, 3, 6, 7, 8] after second partition (left): List length: 5 [3, 5, 6, 7, 8] after third partition (right): List length: 5 [3, 5, 6, 7, 8]

expected: List length: 5 [3, 5, 6, 7, 8] actual: List length: 5 [3, 5, 6, 7, 8]

Test quickSort() ----------------------------------------------- quickSort() test 1, sort list of size 1

expected: List length: 1 [8] actual: List length: 1 [8]

quickSort() test 2, sort list of size 2 already ordered expected: List length: 2 [3, 9]

actual: List length: 2 [3, 9]

quickSort() test 3, sort list of size 2 out of order expected: List length: 2 [3, 9]

actual: List length: 2 [3, 9]

quickSort() test 4, sort odd sized list expected: List length: 9 [2, 3, 4, 5, 5, 6, 7, 8, 9]

actual: List length: 9 [2, 3, 4, 5, 5, 6, 7, 8, 9]

quickSort() test 5, sort even sized list expected: List length: 14 [2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 10, 11]

actual: List length: 14 [2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 10, 11]

quickSort() test 6, sort already sorted list expected: List length: 17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

actual: List length: 17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

7

quickSort() test 7, sort a reversed list expected: List length: 17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

actual: List length: 17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

quickSort() test 7, sort a reversed list expected: List length: 14 [4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8]

actual: List length: 14 [4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8]

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp source files to the submission folder to complete this assignment. You really do not need to give me the assg-05.cpp file again, as I will have my own file with additional tests of your functions. However, please leave the names of the other two files as QuickSort.hpp and QuickSort.cpp when you submit them.

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.

2. (15 pts.) swapListValues() function implemented as specified and working.

3. (15 pts.) findAndSwapPivot() function implemented as specified and working.

4. (30 pts.) partitionList() function implemented as specified and working.

5. (30 pts.) quickSort() function implemented as specified and working.

6. (5 pts.) All output is correct and matches the correct example output.

7. (5 pts.) Followed class style guidelines, especially those mentioned below.

8

Program Style

Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.

2. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.

9