There are 3 parts, each one implements a new function to read a series of items

ID: 3825842 • Letter: T

Question

There are 3 parts, each one implements a new function to read a series of items from an input file.

The first one:

Program

Implement the following template functions in a header file called sorts.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template
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
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.

A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part1/assign8.cpp.

/*********************************************************************
PROGRAM: CSCI 241 Assignment 8, Part 1
PROGRAMMER: your name
LOGON ID: your z-ID
DUE DATE: due date of assignment

FUNCTION: This program builds and sorts lists using the quick
sort algorithm.
*********************************************************************/

#include
#include
#include
#include
#include "sorts.h"

using std::cout;
using std::fixed;
using std::left;
using std::setprecision;
using std::string;
using std::vector;

// Data files

#define D1 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8a.txt"
#define D2 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8b.txt"
#define D3 "/home/turing/t90kjm1/CS241/Data/Spring2017/Assign8/data8c.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 8 - Part 1 Output *** ";

// Build and print first list

cout << "First list: ";
buildList(v1, D1);
printList(v1, INT_SZ, INT_LN);

// Build and print second list

cout << fixed << setprecision(2);

cout << " Second list: ";
buildList(v2, D2);
printList(v2, FLT_SZ, FLT_LN);

// Build and print third list

cout << left;

cout << " Third list: ";
buildList(v3, D3);
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.

For this part of the assignment you will write a number of C++ template functions to sort a list of items using the recursive quick sort algorithm.

The second one:

Program

Add the following template functions to your sorts.h file. The header file should contain both the prototypes and definitions for these functions.

template
bool lessThan(const T& item1, const T& item2)

This function should return true if item1 is less than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

template
bool greaterThan(const T& item1, const T& item2)

This function should return true if item1 is greater than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

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
void quickSort(vector& set, bool (*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 set.size() - 1), and the pointer to the comparison function (compare), e.g.:

quickSort(set, 0, set.size()-1, compare);
template
void quickSort(vector& set, int start, int end, bool (*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
int partition(vector& set, int start, int end, bool (*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))
{
pivotIndex++;
Swap elements pivotIndex and scan of the vector
}
}

Swap elements start and pivotIndex of the vector

return pivotIndex;
A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part2/assign8.cpp.

/*********************************************************************
PROGRAM: CSCI 241 Assignment 8, Part 2
PROGRAMMER: your name
LOGON ID: your z-ID
DUE DATE: due date of assignment

FUNCTION: This program builds and sorts lists using the quick
sort algorithm.
*********************************************************************/

#include
#include
#include
#include
#include "sorts.h"
#include "quicksort.h"

using std::cout;
using std::fixed;
using std::left;
using std::setprecision;
using std::string;
using std::vector;

// Data files

// 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 8 - Part 2 Output *** ";

// sort and print first list

cout << "First list - ascending order: ";
buildList(v1, D1);
quickSort(v1, &lessThan);
printList(v1, INT_SZ, INT_LN);

// Sort and print second list

cout << fixed << setprecision(2);

cout << " Second list - descending order: ";
buildList(v2, D2);
quickSort(v2, &greaterThan);
printList(v2, FLT_SZ, FLT_LN);

// Sort and print third list

cout << left;

cout << " Third list - ascending order: ";
buildList(v3, D3);
quickSort(v3, &lessThan);
printList(v3, STR_SZ, STR_LN);

// print termination message
cout << " *** End of program execution *** ";

return 0;
}

THE FINAL ONE:

Implement the following template functions in a header file called mergesort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template
void mergeSort(vector& set, bool (*compare)(const T&, const T&))

This function should sort the items in the vector set using the merge 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 merge 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 set.size() - 1), and the pointer to the comparison function (compare), e.g.:

mergeSort(set, 0, set.size()-1, compare);
template
void mergeSort(vector& set, int low, int high, bool (*compare)(const T&, const T&))

This recursive function divides a vector into two subvectors, sorts them, and then merges the two sorted subvectors.

int mid;

if (low < high)
{
mid = (low + high) / 2;

// Divide and conquer

mergeSort(set, low, mid, compare);
mergeSort(set, mid+1, high, compare);

// Combine
merge(set, low, mid, high, compare);
}
}
template
void merge(vector& set, int low, int mid, int high, bool (*compare)(const T&, const T&))

This function merges two sorted subvectors.

// Create temporary vector to hold merged subvectors
vector temp(high - low + 1);

int i = low; // Subscript for start of left sorted subvector
int j = mid+1; // Subscript for start of right sorted subvector
int k = 0; // Subscript for start of merged vector

// While not at the end of either subvector
while (i <= mid && j <= high)
{
if (compare(set[j], set[i]))
{
Copy element j of set into element k of temp
Add one to j
Add one to k
}
else
{
Copy element i of set into element k of temp
Add one to i
Add one to k
}
}

// Copy over any remaining elements of left subvector
while (i <= mid)
{
Copy element i of set into element k of temp
Add one to i
Add one to k
}

// Copy over any remaining elements of right subvector
while (j <= high)
{
Copy element j of set into element k of temp
Add one to j
Add one to k
}

// Copy merged elements back into original vector
for (i = 0, j = low; j <= high; i++, j++)
Copy element i of temp into element j of set
A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part3/assign8.cpp.

/*********************************************************************
PROGRAM: CSCI 241 Assignment 8
PROGRAMMER: your name
LOGON ID: your z-ID
DUE DATE: due date of assignment

FUNCTION: This program builds and sorts lists using the quick
sort algorithm.
*********************************************************************/

#include
#include
#include
#include
#include "sorts.h"
#include "quicksort.h"
#include "mergesort.h"

using std::cout;
using std::fixed;
using std::left;
using std::setprecision;
using std::string;
using std::vector;

// Data files

// 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 8 - Output *** ";

// sort and print first list

cout << "First list - ascending order: ";
buildList(v1, D1);
quickSort(v1, &lessThan);
printList(v1, INT_SZ, INT_LN);

v1.clear();

cout << " First list - descending order: ";
buildList(v1, D1);
mergeSort(v1, &greaterThan);
printList(v1, INT_SZ, INT_LN);

// Sort and print second list

cout << fixed << setprecision(2);

cout << " Second list - descending order: ";
buildList(v2, D2);
quickSort(v2, &greaterThan);
printList(v2, FLT_SZ, FLT_LN);

v2.clear();

cout << " Second list - ascending order: ";
buildList(v2, D2);
mergeSort(v2, &lessThan);
printList(v2, FLT_SZ, FLT_LN);

// Sort and print third list

cout << left;

cout << " Third list - ascending order: ";
buildList(v3, D3);
quickSort(v3, &lessThan);
printList(v3, STR_SZ, STR_LN);

v3.clear();

cout << " Third list - descending order: ";
buildList(v3, D3);
mergeSort(v3, &greaterThan);
printList(v3, STR_SZ, STR_LN);

// print termination message
cout << " *** End of program execution *** ";

return 0;
}

Data8a.txt:_____________________

28   -647   -382   69   895   -655   404   -546
-9   -749   -831   -220   -444   -263   966   71
531   293   534   560   646   -695   251   -369
-305   834   40   -197   213   571   863   739
733   349   517   164   -220   -288   -598   654
-167   -72   958   -746   -573   916   475   -181
560   516   913   -942   -361   514   -513   179
-912   912   -361   -880   -115   830   144   -761
139   -495   -7   -525   -45   -187   746   -145
-282   -235   -912   -677   45   393   -804   -197
547   -509   -313   -539   -403   -390   774   -925
302   -202   352   465   875   -532   677   934
557   -136   348   618

Data8b.txt___________________________________
-126.17 -329.04 -170.40 163.42 -279.66 355.67 -207.22 59.06
184.38 189.87 454.23 -834.74 64.03 -630.81 -191.03 -251.65
398.76 -1.87 468.44 378.53 -280.54 580.12 350.48 299.95
-441.58 387.50 -290.67 0.63 -680.65 -728.50 565.64 -497.48
-492.66 132.27 -323.52 -688.54 -361.08 -391.15 -254.70 -152.79
711.98 -330.79 -648.02 113.42 455.87 580.20 -397.21 167.67
-18.69 337.60 -239.58 -208.58 -209.56 -583.92 -286.04 200.05
346.79 199.22 168.89 -327.15 365.32 -430.49 177.14 -176.99
42.38 118.35 -393.01 87.63 105.74 76.02 -286.83 197.70
104.55 721.75 -473.20 -391.86 499.40 873.65 225.40 -32.23
-567.73 878.72 2.91 -10.69 136.53 -237.10 -40.34 -180.62
486.99 -778.98 -267.60 88.52 29.85 6.82 344.29 201.17
-587.31 -157.06 974.89 425.67

data8c.txt___________________
PREFACE This is
a book about
the computer language
called C If
you are seeking
a book to
increase your typing
speed expand on
your knowledge of
word processing or
learn the secrets
of chip fabrication
and design this
is not the
one for you
However if you
want to become
thoroughly familiar with
the C programming
language then you
have made a
wise choice For
this book is
devoted to just
that help you
become proficient in
C It is
one thing to
read about a
language it is
quite another to
get involved in
it The best
and

Part 1 output:_________________________________

First list:

28 -647 -382 69 895 -655 404 -546 -9 -749 -831 -220 -444 -263 966
71 531 293 534 560 646 -695 251 -369 -305 834 40 -197 213 571
863 739 733 349 517 164 -220 -288 -598 654 -167 -72 958 -746 -573
916 475 -181 560 516 913 -942 -361 514 -513 179 -912 912 -361 -880
-115 830 144 -761 139 -495 -7 -525 -45 -187 746 -145 -282 -235 -912
-677 45 393 -804 -197 547 -509 -313 -539 -403 -390 774 -925 302 -202
352 465 875 -532 677 934 557 -136 348 618

Second list:

-126.17 -329.04 -170.40 163.42 -279.66 355.67 -207.22 59.06 184.38
189.87 454.23 -834.74 64.03 -630.81 -191.03 -251.65 398.76 -1.87
468.44 378.53 -280.54 580.12 350.48 299.95 -441.58 387.50 -290.67
0.63 -680.65 -728.50 565.64 -497.48 -492.66 132.27 -323.52 -688.54
-361.08 -391.15 -254.70 -152.79 711.98 -330.79 -648.02 113.42 455.87
580.20 -397.21 167.67 -18.69 337.60 -239.58 -208.58 -209.56 -583.92
-286.04 200.05 346.79 199.22 168.89 -327.15 365.32 -430.49 177.14
-176.99 42.38 118.35 -393.01 87.63 105.74 76.02 -286.83 197.70
104.55 721.75 -473.20 -391.86 499.40 873.65 225.40 -32.23 -567.73
878.72 2.91 -10.69 136.53 -237.10 -40.34 -180.62 486.99 -778.98
-267.60 88.52 29.85 6.82 344.29 201.17 -587.31 -157.06 974.89
425.67

Third list:

PREFACE This is a book
about the computer language called
C If you are seeking
a book to increase your
typing speed expand on your
knowledge of word processing or
learn the secrets of chip
fabrication and design this is
not the one for you
However if you want to
become thoroughly familiar with the
C programming language then you
have made a wise choice
For this book is devoted
to just that help you
become proficient in C It
is one thing to read
about a language it is
quite another to get involved
in it The best and

*** End of program execution ***

Part 2 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

Second list - descending order:

974.89 878.72 873.65 721.75 711.98 580.20 580.12 565.64 499.40
486.99 468.44 455.87 454.23 425.67 398.76 387.50 378.53 365.32
355.67 350.48 346.79 344.29 337.60 299.95 225.40 201.17 200.05
199.22 197.70 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.40 -176.99 -180.62 -191.03
-207.22 -208.58 -209.56 -237.10 -239.58 -251.65 -254.70 -267.60 -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.20 -492.66 -497.48
-567.73 -583.92 -587.31 -630.81 -648.02 -680.65 -688.54 -728.50 -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

*** End of program execution ***

Part 3 and final output_________________________

First list - ascending order:

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 - descending order:

Second list - ascending order:

-834.74 -778.98 -728.50 -688.54 -680.65 -648.02 -630.81 -587.31 -583.92
-567.73 -497.48 -492.66 -473.20 -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.60 -254.70 -251.65 -239.58 -237.10 -209.56 -208.58
-207.22 -191.03 -180.62 -176.99 -170.40 -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.70
199.22 200.05 201.17 225.40 299.95 337.60 344.29 346.79 350.48
355.67 365.32 378.53 387.50 398.76 425.67 454.23 455.87 468.44
486.99 499.40 565.64 580.12 580.20 711.98 721.75 873.65 878.72
974.89

Third list - ascending order:

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

Hi, I have implemented required functions.

Please let me know in case of any issue.

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 buildList(vector<T>& set, const char* fileName){

T item;
ifstream inFile(fileName);

   if(inFile.fail()){
       cout<<"Error in opening file"<<endl;
       return;
   }

   // reading file
   inFile>>item
   while(!inFile.eof()){
       set.push_back(item);
       inFile>>item;
   }

inFile.close();
}

template <class T>
void printList(const vector<T>& set, int itemWidth, int numPerLine){

int count = 0;

for(int i=0; i<set.size(); i++){

cout<<setw(itemWidth)<<set[i];

count++;

       if(count == numPerLine){
           cout<<endl;
           count = 0;
       }
   }
}

Navigate

There are 3 pages to this Lab...the first page is just an example of how they ca

There are 3 parts, each one implements a new function to read a series of items

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

There are 3 parts, each one implements a new function to read a series of items

Question

Explanation / Answer

Related Questions

Navigate