Quick sort For this program you will write a number of C++ functions to sort the
ID: 3633495 • Letter: Q
Question
Quick sort
For this program you will write a number of C++ functions to sort the items in several input files using the recursive quick sort algorithm.
Program
Implement the following template functions in a header file called quicksort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.
• template <class T>
int ascendCompare(const T& item1, const T& item2)
This function should return -1 if item1 is less than item2, 1 if item1 is greater than item2, and 0 if item1 is equal to item2. You may assume that the data type T can be compared using the standard relational operators.
• template <class T>
int descendCompare(const T& item1, const T& item2)
This function should return 1 if item1 is less than item2, -1 if item1 is greater than item2, and 0 if item1 is equal to item2. You may assume that the data type T can be compared using the standard relational operators.
• template <class T>
void buildList(vector& set, const char* fileName)
This function should read items from an input file and put them into a vector. The first argument to this function is a reference to a vector object that will be used to store the items. The second argument is a C-style string containing the full pathname of the input file.
The function should first open the file for input, then read items from the file using the >> operator one at a time until end of file, inserting them into the vector. Finally, it should close the input file. Here's some pseudocode for the logic:
T item;
ifstream inFile;
Open inFile for input using fileName as the name of the file to open
Check that the file has been successfully opened
Read item from input file
while (not end of file)
{
set.push_back(item);
Read item from input file
}
Close the input file
• template <class T>
void printList(const vector& set, int itemWidth, int numPerLine)
This function should print a list of items stored in a vector. The first argument to this function is a reference to a constant vector object that will contain the items to print. The second argument is an integer specifying the width an individual item should occupy when printed. The third argument is an integer specifying the maximum number of items that should be printed in a single line of output.
• template <class T>
void sortList(vector& set, int (*compare)(const T&, const T&))
This function should sort the items in the vector set using the quick sort algorithm. The first argument to this function is a reference to a vector object containing the list of items to sort. The second argument is a pointer to a comparison function that can be used to compare two items of the template type.
This function should call the recursive quick sort function, passing it the vector, the subscript of the first vector element (which is 0), the subscript of the last vector element (which is (int) set.size() - 1), and the pointer to the comparison function (compare), e.g.:
quickSort(set, 0, (int) set.size()-1, compare);
• template <class T>
void quickSort(vector& set, int start, int end, int (*compare)(const T&, const T&))
This function performs the recursive calls to implement the quick sort algorithm. The logic is:
int pivotPoint;
if (start < end)
{
pivotPoint = partition(set, start, end, compare); // Get the pivot point
quickSort(set, start, pivotPoint - 1, compare); // Sort first sublist
quickSort(set, pivotPoint + 1, end, compare); // Sort second sublist
}
• template <class T>
int partition(vector& set, int start, int end, int (*compare)(const T&, const T&))
This function selects a pivot element and then partitions the vector around the pivot. The logic is:
int pivotIndex, mid;
T pivotValue;
mid = (start + end) / 2;
Swap elements start and mid of the vector
pivotIndex = start;
pivotValue = set[start];
for (int scan = start + 1; scan <= end; scan++)
{
if (compare(set[scan], pivotValue) < 0)
{
pivotIndex++;
Swap elements pivotIndex and scan of the vector
}
}
Swap elements start and pivotIndex of the vector
return pivotIndex;
A driver program, assign9.cpp is provided for this assignment. The purpose of a driver program is to test other pieces that you code.
/*********************************************************************
FUNCTION: This program builds and sorts lists using the quick
sort algorithm.
*********************************************************************/
#include
#include
#include
#include "quicksort.h"
using std::cout;
using std::string;
using std::vector;
// Data files
#define D1 "/home/turing/t90kjm1/CS241/Data/Fall2011/Assign9/data9a.txt"
#define D2 "/home/turing/t90kjm1/CS241/Data/Fall2011/Assign9/data9b.txt"
#define D3 "/home/turing/t90kjm1/CS241/Data/Fall2011/Assign9/data9c.txt"
// Output formatting constants
#define INT_SZ 4 // width of integer
#define FLT_SZ 7 // width of floating-pt number
#define STR_SZ 12 // width of string
#define INT_LN 15 // no of integers on single line
#define FLT_LN 9 // no of floating-pt nums on single line
#define STR_LN 5 // no of strings on single line
int main()
{
vector v1; // vector of integers
vector v2; // vector of floating-pt nums
vector v3; // vector of strings
// print header message
cout << "*** CSCI 241: Assignment 9 - Output *** ";
// sort and print first list
cout << "First list - ascending order: ";
buildList(v1, D1);
sortList(v1, &ascendCompare);
printList(v1, INT_SZ, INT_LN);
v1.clear();
cout << " First list - descending order: ";
buildList(v1, D1);
sortList(v1, &descendCompare);
printList(v1, INT_SZ, INT_LN);
// Sort and print second list
cout << " Second list - ascending order: ";
buildList(v2, D2);
sortList(v2, &ascendCompare);
printList(v2, FLT_SZ, FLT_LN);
v2.clear();
cout << " Second list - descending order: ";
buildList(v2, D2);
sortList(v2, &descendCompare);
printList(v2, FLT_SZ, FLT_LN);
// Sort and print third list
cout << " Third list - ascending order: ";
buildList(v3, D3);
sortList(v3, &ascendCompare);
printList(v3, STR_SZ, STR_LN);
v3.clear();
cout << " Third list - descending order: ";
buildList(v3, D3);
sortList(v3, &descendCompare);
printList(v3, STR_SZ, STR_LN);
// print termination message
cout << " *** End of program execution *** ";
return 0;
}
The STL Vector Class
The vector class is part of the C++ Standard Template Library. It is a template class that provides an alternative to using an array.
The vector class is implemented as a dynamic array. Just like a regular array, a vector has its elements stored in contiguous storage locations. But unlike regular arrays, storage in a vector is handled automatically, allowing it to be expanded and contracted as needed.
Vectors are good at:
• Accessing individual elements by their position index.
• Iterating over the elements in any order.
• Adding to and removing elements from the tail end of the vector.
Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. They usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).
Example Vector Operations
To create an empty vector, you can use the default constructor:
vector v1; // Create an empty vector of integers
You can also create a vector of a specific initial size:
vector v1(20); // Create a vector of integers with size 20
To add a new element to the tail end of a vector, you can use the push_back() method:
v1.push_back(12); // Add a new element with value 12 to the tail end of the vector
You can use a for loop and the subscript operator to loop through the elements of a vector, similar to the way you would loop through an array:
for (int i = 0; i < (int) v1.size(); i++)
cout << v1[i] << ' ';
cout << endl;
(The size() method typically returns an unsigned int, so we need to perform a type cast to avoid a warning from the compiler.)
Vectors also have an at() method that will throw an out_of_range exception if you try to access an element outside the bounds of the dynamic array.
Output
*** CSCI 241: Assignment 9 - Output ***
First list - ascending order:
-942 -925 -912 -912 -880 -831 -804 -761 -749 -746 -695 -677 -655 -647 -598
-573 -546 -539 -532 -525 -513 -509 -495 -444 -403 -390 -382 -369 -361 -361
-313 -305 -288 -282 -263 -235 -220 -220 -202 -197 -197 -187 -181 -167 -145
-136 -115 -72 -45 -9 -7 28 40 45 69 71 139 144 164 179
213 251 293 302 348 349 352 393 404 465 475 514 516 517 531
534 547 557 560 560 571 618 646 654 677 733 739 746 774 830
834 863 875 895 912 913 916 934 958 966
First list - descending order:
966 958 934 916 913 912 895 875 863 834 830 774 746 739 733
677 654 646 618 571 560 560 557 547 534 531 517 516 514 475
465 404 393 352 349 348 302 293 251 213 179 164 144 139 71
69 45 40 28 -7 -9 -45 -72 -115 -136 -145 -167 -181 -187 -197
-197 -202 -220 -220 -235 -263 -282 -288 -305 -313 -361 -361 -369 -382 -390
-403 -444 -495 -509 -513 -525 -532 -539 -546 -573 -598 -647 -655 -677 -695
-746 -749 -761 -804 -831 -880 -912 -912 -925 -942
Second list - ascending order:
-834.74 -778.98 -728.5 -688.54 -680.65 -648.02 -630.81 -587.31 -583.92
-567.73 -497.48 -492.66 -473.2 -441.58 -430.49 -397.21 -393.01 -391.86
-391.15 -361.08 -330.79 -329.04 -327.15 -323.52 -290.67 -286.83 -286.04
-280.54 -279.66 -267.6 -254.7 -251.65 -239.58 -237.1 -209.56 -208.58
-207.22 -191.03 -180.62 -176.99 -170.4 -157.06 -152.79 -126.17 -40.34
-32.23 -18.69 -10.69 -1.87 0.63 2.91 6.82 29.85 42.38
59.06 64.03 76.02 87.63 88.52 104.55 105.74 113.42 118.35
132.27 136.53 163.42 167.67 168.89 177.14 184.38 189.87 197.7
199.22 200.05 201.17 225.4 299.95 337.6 344.29 346.79 350.48
355.67 365.32 378.53 387.5 398.76 425.67 454.23 455.87 468.44
486.99 499.4 565.64 580.12 580.2 711.98 721.75 873.65 878.72
974.89
Second list - descending order:
974.89 878.72 873.65 721.75 711.98 580.2 580.12 565.64 499.4
486.99 468.44 455.87 454.23 425.67 398.76 387.5 378.53 365.32
355.67 350.48 346.79 344.29 337.6 299.95 225.4 201.17 200.05
199.22 197.7 189.87 184.38 177.14 168.89 167.67 163.42 136.53
132.27 118.35 113.42 105.74 104.55 88.52 87.63 76.02 64.03
59.06 42.38 29.85 6.82 2.91 0.63 -1.87 -10.69 -18.69
-32.23 -40.34 -126.17 -152.79 -157.06 -170.4 -176.99 -180.62 -191.03
-207.22 -208.58 -209.56 -237.1 -239.58 -251.65 -254.7 -267.6 -279.66
-280.54 -286.04 -286.83 -290.67 -323.52 -327.15 -329.04 -330.79 -361.08
-391.15 -391.86 -393.01 -397.21 -430.49 -441.58 -473.2 -492.66 -497.48
-567.73 -583.92 -587.31 -630.81 -648.02 -680.65 -688.54 -728.5 -778.98
-834.74
Third list - ascending order:
C C C For However
If It PREFACE The This
a a a a about
about and and another are
become become best book book
book called chip choice computer
design devoted expand fabrication familiar
for get have help if
in in increase involved is
is is is is it
it just knowledge language language
language learn made not of
of on one one or
processing proficient programming quite read
secrets seeking speed that the
the the the then thing
this this thoroughly to to
to to to typing want
wise with word you you
you you you your your
Third list - descending order:
your your you you you
you you word with wise
want typing to to to
to to thoroughly this this
thing then the the the
the that speed seeking secrets
read quite programming proficient processing
or one one on of
of not made learn language
language language knowledge just it
it is is is is
is involved increase in in
if help have get for
familiar fabrication expand devoted design
computer choice chip called book
book book best become become
are another and and about
about a a a a
This The PREFACE It If
However For C C C
*** End of program execution ***
Explanation / Answer
#include 02 #include 03 #include 04 05 using namespace std; 06 07 void quicksort(int *lp, int *rp); 08 int passes = 0; 09 10 int main() 11 { 12 int arraylength = 5000; 13 int sortarray[arraylength]; 14 srand(time(NULL)); 15 for (int i = 0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.