Lab 10 - Quicksort (12/04/2021)

---

Lab requirements:

1. Your program should be able to successfully sort all the numbers in an array, using your partition function.
2. Your partition function should return the correct pivot index of the subarray.
3. You must use a dynamically-allocated array for this lab; no other data structures may be used.
4. You are required to implement the given abstract interface class (QSInterface.)

5. The following summarizes the commands used in the Quicksort lab:

COMMAND	DESCRIPTION	OUTPUT
QuickSort <capacity>	Dynamically allocate a QuickSort array of size capacity. Set current number of elements (Size) to 0.	OK Error
AddToArray <data1> <data2>...	Add data element(s) to QuickSort array. Duplicates are allowed. Dynamically increase array size as needed (by doubling array capacity.)	OK Error
Capacity	Return the capacity of the QuickSort array.	size
Clear	Remove all inserted elements from the QuickSort array. (Do not delete QuickSort array - capacity stays the same.)	OK
Size	Return the number of elements currently in the QuickSort array.	elements
Sort <left> <right>	Revised quickSort the elements in the QuickSort array from index <left> to index <right> (where <right> is one past last element) using median-of-3 and partition functions.	OK Error
SortAll	Revised quickSort all the elements in the QuickSort array using median-of-3 and partition functions.	OK Error
MedianOfThree <left> <right>	1) Calculate the middle index (middle = (left + right)/2). 2) Bubble-sort the values at the left, middle, and right indices. 3) Output the index of the (<right> is one past last element.)	Index of the pivot (middle index); -1 if provided with invalid input
Partition <left> <right> <pivot>	Using the revised pivot algorithm, partition the QuickSort array (<left>, <right> and <pivot> indexes) around the pivot value. Values smaller than or equal to the pivot should be placed to the left of the pivot while values larger than the pivot should be placed to the right of the pivot. (<right> is one past last element.)	Pivot's ending index, -1 if provided with invalid input
PrintArray	Print the contents of the QuickSort array as comma separated values (using a friend insertion (<<) operator and toString() function.)	Array values. Empty
BONUS: Stats	Output the number of comparisons and exchanges of array data used by the sort commands (SortAll and Sort <left> <right> - reset the counts for each sort command.)	Comparisons,Exchanges

Steps to Success:

• Step 1 - Begin with a main function.
  1. As with all labs this semester, you will need to write your own main function.
  2. Use command line arguments for input and output files.

• Step 2 - Add your QuickSort class.
  1. The templated QuickSort class is derived from the abstract template interface class (QSInterface.)
  2. Your QuickSort class should contain a dynamically-allocated templated array. Before you focus too much on the actual sorting algorithm, make sure the logistics of the class work correctly. Focus on addToArray(), clear(), getSize(), and toString() member functions.

• Step 3 - Write your medianOfThree() function in the QuickSort class.
  1. The Median-of-Three function takes left and right indexes as parameters and then calculates the index in the middle of the indexes (rounding down if necessary).
  2. Sort the left, middle, and right numbers from smallest to largest in the array.
  3. Finally, return the index of the middle value. This will be your pivot value in the sortAll() function.
  4. Note that medianOfThree() is not used in your partition() function. The pivot value will be supplied by an input file Partition command.

• Step 4 - Write your partition() function in the QuickSort class.
  1. The partition() function should begin by swapping the leftmost element of the array with the pivot index element.
  2. Now, follow the revised pivot algorithm presented in the textbook (pg. 611) to partition the array such that all elements less than or equal to the pivot value are left of the pivot and all elements great than the pivot value are to the right of the pivot.
  3. The partition() function should return the new location of the pivot index.

• Step 5 - Write the sortAll() function, using your medianOfThree() and partition() functions.
  1. Note that this function will be recursive. Most people use sortAll() as a recursive starter function that then call another function to do the sorting.
  2. To revised quicksort, first call your medianOfThree() function to sort the first, middle, and last elements and return the pivot index.
  3. Now, call your partition() function, using the index returned from medianOfThree() as the pivot index. This function will return a new pivot index where your array is split.
  4. Finally, recursively call your sort() function on the two halves of your array, with one half from the left to the pivot and the other half from the pivot to the right.
  5. Note: Reset exchange and comparison counters at the beginning of Sort and SortAll commands for the Bonus test.

Finding Memory Leaks.

Understanding VS_MEM_CHECK Output._(collapse)

Understanding Valgrind Output._(collapse)

Instructions for submitting your lab:

• Zip all your lab source files (.cpp, .hpp, .h) into one folder. DO NOT INCLUDE YOUR WHOLE PROJECT!
• Submit your zipped lab source using the "Labs" tab on the class website.
• Your submitted lab source will be compiled and executed using a lab gcc compiler.
• Both input and output files will be specified by command line arguments.
• An auto-grader will compare your output files with expected results and you will shortly receive an accumulative score.
• The auto-grade process may abort on the first error. If so, correct the error and try again.
• You may re-submit your zipped source as many times as you like.

Use the following input and resulting output files in testing the Quicksort lab:

The auto-grader will be expecting to find in your output file the following sections:

The lab source will be peer reviewed using the following rubric: