The question is basically to implement the 2 functions, selection sort and quick
ID: 3903481 • Letter: T
Question
The question is basically to implement the 2 functions, selection sort and quicksort functions. As you can see in the source code below, the functions are empty in the VectorSorting.cpp
I also included 2 other source code files and a input text file. They are separated by *****************
The VectorSorting.cpp program is partially completed - it contains empty methods representing the programming interface used to interact with the linked list. You will need to add logic to the methods to implement the necessary behavior. Here are the methods in VectorSorting.cpp that you have to complete:
void selectionSort(vector& bids)
void quickSort(vector& bids, int begin, int end)
int partition(vector& bids, int begin, int end)
Task 1: Implement the selection sort algorithm:
Code the selection sort logic using bid.title as the sort field.
Invoke the selectionSort() method from the main() method including collecting and reporting timing results.
Task 2: Implement the quicksort algorithm:
Code the quicksort logic using bid.title as the sort field.
Invoke the quickSort() method from the main() method including collecting and reporting timing results.
********************************************* VectorSorting.cpp ****************************************
#include
#include
#include
#include "CSVparser.hpp"
using namespace std;
//============================================================================
// Global definitions visible to all methods and classes
//============================================================================
// forward declarations
double strToDouble(string str, char ch);
// define a structure to hold bid information
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
//============================================================================
// Static methods used for testing
//============================================================================
/**
* Display the bid information to the console (std::out)
*
* @param bid struct containing the bid info
*/
void displayBid(Bid bid) {
cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
<< bid.fund << endl;
return;
}
/**
* Prompt user for bid information using console (std::in)
*
* @return Bid struct containing the bid info
*/
Bid getBid() {
Bid bid;
cout << "Enter Id: ";
cin.ignore();
getline(cin, bid.bidId);
cout << "Enter title: ";
getline(cin, bid.title);
cout << "Enter fund: ";
cin >> bid.fund;
cout << "Enter amount: ";
cin.ignore();
string strAmount;
getline(cin, strAmount);
bid.amount = strToDouble(strAmount, '$');
return bid;
}
/**
* Load a CSV file containing bids into a container
*
* @param csvPath the path to the CSV file to load
* @return a container holding all the bids read
*/
vector loadBids(string csvPath) {
cout << "Loading CSV file " << csvPath << endl;
// Define a vector data structure to hold a collection of bids.
vector bids;
// initialize the CSV Parser using the given path
csv::Parser file = csv::Parser(csvPath);
try {
// loop to read rows of a CSV file
for (int i = 0; i < file.rowCount(); i++) {
// Create a data structure and add to the collection of bids
Bid bid;
bid.bidId = file[i][1];
bid.title = file[i][0];
bid.fund = file[i][8];
bid.amount = strToDouble(file[i][4], '$');
//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
// push this bid to the end
bids.push_back(bid);
}
} catch (csv::Error &e) {
std::cerr << e.what() << std::endl;
}
return bids;
}
// FIXME (2a): Implement the quick sort logic over bid.title
/**
* Partition the vector of bids into two parts, low and high
*
* @param bids Address of the vector instance to be partitioned
* @param begin Beginning index to partition
* @param end Ending index to partition
*/
int partition(vector& bids, int begin, int end) {
}
/**
* Perform a quick sort on bid title
* Average performance: O(n log(n))
* Worst case performance O(n^2))
*
* @param bids address of the vector instance to be sorted
* @param begin the beginning index to sort on
* @param end the ending index to sort on
*/
void quickSort(vector& bids, int begin, int end) {
}
// FIXME (1a): Implement the selection sort logic over bid.title
/**
* Perform a selection sort on bid title
* Average performance: O(n^2))
* Worst case performance O(n^2))
*
* @param bid address of the vector
* instance to be sorted
*/
void selectionSort(vector& bids) {
}
/**
* Simple C function to convert a string to a double
* after stripping out unwanted char
*
* credit: http://stackoverflow.com/a/24875936
*
* @param ch The character to strip out
*/
double strToDouble(string str, char ch) {
str.erase(remove(str.begin(), str.end(), ch), str.end());
return atof(str.c_str());
}
/**
* The one and only main() method
*/
int main(int argc, char* argv[]) {
// process command line arguments
string csvPath;
switch (argc) {
case 2:
csvPath = argv[1];
break;
default:
csvPath = "eBid_Monthly_Sales_Dec_2016.csv";
}
// Define a vector to hold all the bids
vector bids;
// Define a timer variable
clock_t ticks;
int choice = 0;
while (choice != 9) {
cout << "Menu:" << endl;
cout << " 1. Load Bids" << endl;
cout << " 2. Display All Bids" << endl;
cout << " 3. Selection Sort All Bids" << endl;
cout << " 4. Quick Sort All Bids" << endl;
cout << " 9. Exit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
bids = loadBids(csvPath);
cout << bids.size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 2:
// Loop and display the bids read
for (int i = 0; i < bids.size(); ++i) {
displayBid(bids[i]);
}
cout << endl;
break;
// FIXME (1b): Invoke the selection sort and report timing results
// FIXME (2b): Invoke the quick sort and report timing results
}
}
cout << "Good bye." << endl;
return 0;
}
******************************************* CSVparser.hpp ********************************************
#ifndef _CSVPARSER_HPP_
# define _CSVPARSER_HPP_
# include
# include
# include
# include
# include
namespace csv
{
class Error : public std::runtime_error
{
public:
Error(const std::string &msg):
std::runtime_error(std::string("CSVparser : ").append(msg))
{
}
};
class Row
{
public:
Row(const std::vector &);
~Row(void);
public:
unsigned int size(void) const;
void push(const std::string &);
bool set(const std::string &, const std::string &);
private:
const std::vector _header;
std::vector _values;
public:
template
const T getValue(unsigned int pos) const
{
if (pos < _values.size())
{
T res;
std::stringstream ss;
ss << _values[pos];
ss >> res;
return res;
}
throw Error("can't return this value (doesn't exist)");
}
const std::string operator[](unsigned int) const;
const std::string operator[](const std::string &valueName) const;
friend std::ostream& operator<<(std::ostream& os, const Row &row);
friend std::ofstream& operator<<(std::ofstream& os, const Row &row);
};
enum DataType {
eFILE = 0,
ePURE = 1
};
class Parser
{
public:
Parser(const std::string &, const DataType &type = eFILE, char sep = ',');
~Parser(void);
public:
Row &getRow(unsigned int row) const;
unsigned int rowCount(void) const;
unsigned int columnCount(void) const;
std::vector getHeader(void) const;
const std::string getHeaderElement(unsigned int pos) const;
const std::string &getFileName(void) const;
public:
bool deleteRow(unsigned int row);
bool addRow(unsigned int pos, const std::vector &);
void sync(void) const;
protected:
void parseHeader(void);
void parseContent(void);
private:
std::string _file;
const DataType _type;
const char _sep;
std::vector _originalFile;
std::vector _header;
std::vector _content;
public:
Row &operator[](unsigned int row) const;
};
}
#endif /*!_CSVPARSER_HPP_*/
*************************************************** CSVparser.cpp *******************************************
#include
#include
#include
#include "CSVparser.hpp"
namespace csv {
Parser::Parser(const std::string &data, const DataType &type, char sep)
: _type(type), _sep(sep)
{
std::string line;
if (type == eFILE)
{
_file = data;
std::ifstream ifile(_file.c_str());
if (ifile.is_open())
{
while (ifile.good())
{
getline(ifile, line);
if (line != "")
_originalFile.push_back(line);
}
ifile.close();
if (_originalFile.size() == 0)
throw Error(std::string("No Data in ").append(_file));
parseHeader();
parseContent();
}
else
throw Error(std::string("Failed to open ").append(_file));
}
else
{
std::istringstream stream(data);
while (std::getline(stream, line))
if (line != "")
_originalFile.push_back(line);
if (_originalFile.size() == 0)
throw Error(std::string("No Data in pure content"));
parseHeader();
parseContent();
}
}
Parser::~Parser(void)
{
std::vector::iterator it;
for (it = _content.begin(); it != _content.end(); it++)
delete *it;
}
void Parser::parseHeader(void)
{
std::stringstream ss(_originalFile[0]);
std::string item;
while (std::getline(ss, item, _sep))
_header.push_back(item);
}
void Parser::parseContent(void)
{
std::vector::iterator it;
it = _originalFile.begin();
it++; // skip header
for (; it != _originalFile.end(); it++)
{
bool quoted = false;
int tokenStart = 0;
unsigned int i = 0;
Row *row = new Row(_header);
for (; i != it->length(); i++)
{
if (it->at(i) == '"')
quoted = ((quoted) ? (false) : (true));
else if (it->at(i) == ',' && !quoted)
{
row->push(it->substr(tokenStart, i - tokenStart));
tokenStart = i + 1;
}
}
//end
row->push(it->substr(tokenStart, it->length() - tokenStart));
// if value(s) missing
if (row->size() != _header.size())
throw Error("corrupted data !");
_content.push_back(row);
}
}
Row &Parser::getRow(unsigned int rowPosition) const
{
if (rowPosition < _content.size())
return *(_content[rowPosition]);
throw Error("can't return this row (doesn't exist)");
}
Row &Parser::operator[](unsigned int rowPosition) const
{
return Parser::getRow(rowPosition);
}
unsigned int Parser::rowCount(void) const
{
return _content.size();
}
unsigned int Parser::columnCount(void) const
{
return _header.size();
}
std::vector Parser::getHeader(void) const
{
return _header;
}
const std::string Parser::getHeaderElement(unsigned int pos) const
{
if (pos >= _header.size())
throw Error("can't return this header (doesn't exist)");
return _header[pos];
}
bool Parser::deleteRow(unsigned int pos)
{
if (pos < _content.size())
{
delete *(_content.begin() + pos);
_content.erase(_content.begin() + pos);
return true;
}
return false;
}
bool Parser::addRow(unsigned int pos, const std::vector &r)
{
Row *row = new Row(_header);
for (auto it = r.begin(); it != r.end(); it++)
row->push(*it);
if (pos <= _content.size())
{
_content.insert(_content.begin() + pos, row);
return true;
}
return false;
}
void Parser::sync(void) const
{
if (_type == DataType::eFILE)
{
std::ofstream f;
f.open(_file, std::ios::out | std::ios::trunc);
// header
unsigned int i = 0;
for (auto it = _header.begin(); it != _header.end(); it++)
{
f << *it;
if (i < _header.size() - 1)
f << ",";
else
f << std::endl;
i++;
}
for (auto it = _content.begin(); it != _content.end(); it++)
f << **it << std::endl;
f.close();
}
}
const std::string &Parser::getFileName(void) const
{
return _file;
}
/*
** ROW
*/
Row::Row(const std::vector &header)
: _header(header) {}
Row::~Row(void) {}
unsigned int Row::size(void) const
{
return _values.size();
}
void Row::push(const std::string &value)
{
_values.push_back(value);
}
bool Row::set(const std::string &key, const std::string &value)
{
std::vector::const_iterator it;
int pos = 0;
for (it = _header.begin(); it != _header.end(); it++)
{
if (key == *it)
{
_values[pos] = value;
return true;
}
pos++;
}
return false;
}
const std::string Row::operator[](unsigned int valuePosition) const
{
if (valuePosition < _values.size())
return _values[valuePosition];
throw Error("can't return this value (doesn't exist)");
}
const std::string Row::operator[](const std::string &key) const
{
std::vector::const_iterator it;
int pos = 0;
for (it = _header.begin(); it != _header.end(); it++)
{
if (key == *it)
return _values[pos];
pos++;
}
throw Error("can't return this value (doesn't exist)");
}
std::ostream &operator<<(std::ostream &os, const Row &row)
{
for (unsigned int i = 0; i != row._values.size(); i++)
os << row._values[i] << " | ";
return os;
}
std::ofstream &operator<<(std::ofstream &os, const Row &row)
{
for (unsigned int i = 0; i != row._values.size(); i++)
{
os << row._values[i];
if (i < row._values.size() - 1)
os << ",";
}
return os;
}
}
********************************************* eBid_Monthly_Sales_Dec_2016.csv ***************************************
ArticleTitle,ArticleID,Department ,CloseDate ,WinningBid ,InventoryID,VehicleID,ReceiptNumber ,Fund
Hoover Steam Vac,97991,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/1/16,$27.00 ,PPEU-031C-149,,3689905552,Enterprise
Table,97990,GENERAL SERVICES,12/1/16,$6.00 ,109886,,3689973013,General Fund
Table,97989,GENERAL SERVICES,12/1/16,$6.00 ,109885,,3689912834,General Fund
Table,97988,GENERAL SERVICES,12/1/16,$1.00 ,109887,,Cashiers Check,General Fund
Swann Security System,97987,POLICE STATE DRUG FUND,12/1/16,$218.00 ,PSDF-028-008,,Money Order,Enterprise
Sony Laptop,97986,POLICE STATE DRUG FUND,12/1/16,$283.00 ,PSDF-028-014,,3689705726,Enterprise
XBox 360,97985,POLICE STATE DRUG FUND,12/1/16,$33.00 ,PSDF-028-017,,3689703535,Enterprise
Apple iPad,97983,POLICE STATE DRUG FUND,12/1/16,$103.00 ,PSDF-028-010,,3689705721,Enterprise
Canon EOS 7D Digital Camera,97982,POLICE STATE DRUG FUND,12/1/16,$570.00 ,PSDF-028-015,,3689716165,Enterprise
2 Lorex Digital Wireless Cameras,97981,POLICE STATE DRUG FUND,12/1/16,$62.00 ,PSDF-028-007,,3689905550,Enterprise
2 Cobra Walkie Talkies,97980,POLICE STATE DRUG FUND,12/1/16,$47.00 ,PSDF-028-006,,3690146153,Enterprise
Flips Audio Head Phones,97979,POLICE STATE DRUG FUND,12/1/16,$42.00 ,PSDF-028-005,,3689988791,Enterprise
Beats by Dr. Dre Head Phones,97978,POLICE STATE DRUG FUND,12/1/16,$111.00 ,PSDF-028-004,,3690573953,Enterprise
Kent Bicycle,98021,POLICE VEHICLE IMPOUND,12/5/16,$42.00 ,IM-1066412,,Money Order,General Fund
Kent Bicycle,98020,POLICE VEHICLE IMPOUND,12/5/16,$47.00 ,IM-185301,,Money Order,General Fund
Diamond Back Bicycle,98019,POLICE VEHICLE IMPOUND,12/5/16,$39.00 ,IM-1067043,,Money Order,General Fund
Nishiki 21-Speed Bicycle,98017,POLICE VEHICLE IMPOUND,12/5/16,$53.00 ,IM-167532,,3690374823,General Fund
Pacific 21-Speed Bicycle,98016,POLICE VEHICLE IMPOUND,12/5/16,$25.00 ,IM-164977,,3690527641,General Fund
Next 14-Speed Bicycle,98015,POLICE VEHICLE IMPOUND,12/5/16,$21.00 ,IM-1074187,,3690141071,General Fund
Breezer 24-Speed Bicycle,98014,POLICE VEHICLE IMPOUND,12/5/16,$209.00 ,IM-148995,,3690056324,General Fund
GMC 21-Speed Bicycle,98013,POLICE VEHICLE IMPOUND,12/5/16,$57.00 ,IM-172876,,Money Order,General Fund
Magna 15-Speed Bicycle,98012,POLICE VEHICLE IMPOUND,12/5/16,$27.00 ,IM-149000,,3690095346,General Fund
Dell Laptop,98011,ITS,12/5/16,$118.50 ,110140,,3689973470,General Fund
Dell Laptop,98010,ITS,12/5/16,$88.05 ,110538,,3690146276,General Fund
Dell Laptop,98009,ITS,12/5/16,$84.00 ,110532,,3690050066,General Fund
Office Supplies,98008,REGISTER OF DEEDS,12/5/16,$21.00 ,"108082, 108079, 108081, 108070, 108080, 108076, 108072",,3690258278,General Fund
Printer,98006,REGISTER OF DEEDS,12/5/16,$52.00 ,108063,,3690258275,General Fund
Printer,98005,REGISTER OF DEEDS,12/5/16,$50.00 ,108064,,3690072277,General Fund
Printer,98004,REGISTER OF DEEDS,12/5/16,$45.00 ,108062,,3690072273,General Fund
Printer,98003,REGISTER OF DEEDS,12/5/16,$42.00 ,108061,,3689967871,General Fund
Microwave,98002,REGISTER OF DEEDS,12/5/16,$22.89 ,108078,,3691033939,General Fund
Microwave,98001,REGISTER OF DEEDS,12/5/16,$20.01 ,108077,,3690930820,General Fund
Printer,98000,REGISTER OF DEEDS,12/5/16,$40.50 ,108060,,3690267190,General Fund
Lamp,97999,GENERAL SERVICES,12/5/16,$11.00 ,109827,,Cashiers Check,General Fund
3 Chairs,97998,GENERAL SERVICES,12/5/16,$2.00 ,"109973, 109977, 109978",,3690961483,General Fund
Binders,97995,POLICE DEPARTMENT,12/5/16,$4.00 ,108948A,,3689963867,General Fund
3 Chairs,97994,POLICE DEPARTMENT,12/5/16,$4.00 ,"110872, 110873, 110874",,3690550867,General Fund
Popcorn Popper w/Stand,97993,ECD COMMUNICATIONS,12/5/16,$130.00 ,ECD-110883,,Cashiers Check,Enterprise
Electric Impact Wrench,98045,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$42.00 ,PPEU-034-031,,3690241644,Enterprise
DeWalt VSR Versa-Clutch Screwdriver,98044,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$20.00 ,PPEU-034-023,,3690241982,Enterprise
"Black & Decker 1/2"" Electric Impact Wrench",98043,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$29.02 ,PPEU-034-033,,3690067279,Enterprise
Hilti Angle Grinder,98042,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$21.00 ,PPEU-034-027,,3690137617,Enterprise
AmBico Bag w/Camera Accessories,98041,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$32.60 ,PPEU-034-036,,3690060900,Enterprise
Innova Car Scan,98040,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$201.00 ,PPEU-034-032,,3690551269,Enterprise
Tool Box w/Tools,98039,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/6/16,$54.26 ,PPEU-034-042,,3690389639,Enterprise
Copier,98029,SCHOOL BOARD WAREHOUSE,12/6/16,$113.00 ,SBS-7963,,3690094896,Enterprise
Mixer,98027,SCHOOL BOARD FOOD SERVICE,12/6/16,$870.00 ,FSBS-0312,,3690053834,Enterprise
Ice Maker,98025,SCHOOL BOARD FOOD SERVICE,12/6/16,$640.00 ,FSBS-0315,,Cashiers Check,Enterprise
Ice Cream Box,98024,SCHOOL BOARD FOOD SERVICE,12/6/16,$2.00 ,FSBS-0313,,3690791030,Enterprise
Refrigerator,98023,SCHOOL BOARD FOOD SERVICE,12/6/16,$106.01 ,FSBS-0316,,3690542151,Enterprise
Freezer,98022,SCHOOL BOARD FOOD SERVICE,12/6/16,$135.99 ,FSBS-0314,,3690791023,Enterprise
2009 Chevolet Impala,98086,OFM-POLICE,12/7/16,$164.00 ,,1884 JI,Money Order,Enterprise
2008 Ford F-550,98085,OFM-WATER SERVICES,12/7/16,"$6,350.00 ",,1577 JG,Cashiers Check,Enterprise
2005 CM Dakota 2 Stall Horse Trailer,98084,POLICE DEPARTMENT,12/7/16,"$2,425.00 ",,07S 4686,Cashiers Check,General Fund
2005 CM Dakota 2 Stall Horse Trailer,98083,POLICE DEPARTMENT,12/7/16,"$2,425.00 ",,07S 4687,Cashiers Check,General Fund
Compaq Laptop,98077,POLICE STATE DRUG FUND,12/7/16,$48.00 ,PSDF-027C-183,,3690163275,Enterprise
2 PS3 Controllers,98076,POLICE STATE DRUG FUND,12/7/16,$6.99 ,PSDF-027C-181,,3690594168,Enterprise
"Dynex 60"" Tripod",98075,POLICE STATE DRUG FUND,12/7/16,$22.01 ,PSDF-027C-198,,3690163339,Enterprise
RCA Blu-ray Player,98072,POLICE STATE DRUG FUND,12/7/16,$10.50 ,PSDF-027C-202,,Money Order,Enterprise
Sony Blu-ray Player,98071,POLICE STATE DRUG FUND,12/7/16,$28.44 ,PSDF-027C-173,,Money Order,Enterprise
Apex DVD Player,98070,POLICE STATE DRUG FUND,12/7/16,$13.00 ,PSDF-027C-203,,Money Order,Enterprise
Onkyo Receiver,98068,POLICE STATE DRUG FUND,12/7/16,$97.99 ,PSDF-027C-194,,3690389647,Enterprise
Hoshizaki Ice Machine,98062,SCHOOL BOARD FOOD SERVICE,12/7/16,$311.00 ,FSBS-0337,,3690245129,Enterprise
Hoshizaki Ice Machine,98061,SCHOOL BOARD FOOD SERVICE,12/7/16,$311.00 ,FSBS-0336,,3690245126,Enterprise
3 Televisions,97961,DRUG TASK FORCE,12/8/16,$15.01 ,"TF-336-016, TF-336-018, TF-336-021",,3690771293,Enterprise
"Marantz 50"" Plasma Monitor",97960,DRUG TASK FORCE,12/8/16,$10.11 ,TF-336-017,,3691175249,Enterprise
"Sanyo 55"" LCD TV",97959,DRUG TASK FORCE,12/8/16,$362.44 ,TF-336-039,,Money Order,Enterprise
"Samsung 43"" Plasma TV",97958,DRUG TASK FORCE,12/8/16,$93.00 ,TF-336-025,,3690624968,Enterprise
"Samsung 43"" Plasma TV",97957,DRUG TASK FORCE,12/8/16,$57.00 ,TF-336-026,,Money Order,Enterprise
"Samsung 43"" Plasma TV",97956,DRUG TASK FORCE,12/8/16,$96.00 ,TF-336-027,,3690556422,Enterprise
Dell Monitor,97955,DRUG TASK FORCE,12/8/16,$13.00 ,TF-332-106,,3690528491,Enterprise
Gateway Laptop,97954,DRUG TASK FORCE,12/8/16,$25.00 ,TF-332-030,,3690255090,Enterprise
Weight Bench,97953,DRUG TASK FORCE,12/8/16,$103.00 ,TF-332-108,,3690389635,Enterprise
Horizon Elliptical Machine,97952,DRUG TASK FORCE,12/8/16,$25.00 ,TF-332-115,,3690791017,Enterprise
Weider Club Work Out Gym Set,97951,DRUG TASK FORCE,12/8/16,$190.00 ,"TF-332-107, TF-332-034",,3690389633,Enterprise
Weight Bar w/Assorted Weights,97950,DRUG TASK FORCE,12/8/16,$195.00 ,TF-332-111,,3690977738,Enterprise
2 Weight Stands w/Weights,97949,DRUG TASK FORCE,12/8/16,$94.00 ,"TF-332-109, TF-332-110",,3690389631,Enterprise
"Samsung 40"" LED TV",97947,DRUG TASK FORCE,12/8/16,$130.00 ,TF-332-119,,Money Order,Enterprise
"Hisense 40"" LED TV",97946,DRUG TASK FORCE,12/8/16,$157.00 ,TF-332-040,,3690249163,Enterprise
"Chicago 7"" Tile Saw",98199,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/12/16,$43.00 ,PPEU-034-012,,Money Order,Enterprise
Whirlpool Washer & Dryer,98109,POLICE STATE DRUG FUND,12/12/16,$225.46 ,"PSDF-027E-263, PSDF-027E-264",,3690663876,Enterprise
Toshiba Laptop,98107,POLICE STATE DRUG FUND,12/12/16,$91.00 ,PSDF-027E-261,,3690631508,Enterprise
2 PS4 Games,98105,POLICE STATE DRUG FUND,12/12/16,$11.00 ,PSDF-027B-108B,,3690624521,Enterprise
3 Ticket Booths,98104,TENNESSEE STATE FAIR,12/12/16,$395.01 ,"SF-111291, SF-111292, SF-111293",,3691012440,Enterprise
Battery Cart,98102,SCHOOL BOARD WAREHOUSE,12/12/16,$42.00 ,SBS-7875D,,3690965201,Enterprise
Credenza,98094,GENERAL SERVICES,12/12/16,$57.00 ,111117,,3690729974,General Fund
Printer,98129,WATER SERVICES,12/13/16,$52.00 ,WS-110943,,3690662011,Enterprise
Copier,98128,ASSESSOR OF PROPERTY,12/13/16,$83.00 ,111052,,3690662143,General Fund
2 Chairs,98127,HEALTH,12/13/16,$4.00 ,"110866, 110867",,Money Order,General Fund
Dell Laptop,98126,ITS,12/13/16,$68.00 ,110954,,3690637101,General Fund
Dell Laptop,98124,ITS,12/13/16,$68.00 ,110952,,3690637096,General Fund
Dell Laptop,98123,ITS,12/13/16,$64.00 ,110959,,3690697845,General Fund
Dell Laptop,98121,ITS,12/13/16,$74.04 ,110950,,3690697840,General Fund
Dell Laptop,98119,ITS,12/13/16,$68.00 ,110956,,3690767551,General Fund
Dell Laptop,98118,ITS,12/13/16,$106.00 ,110967,,3690697839,General Fund
Dell Computer,98113,ITS,12/13/16,$81.01 ,110981,,3690696620,General Fund
Dell Computer,98112,ITS,12/13/16,$79.88 ,110978,,3691147309,General Fund
Dell Computer,98111,ITS,12/13/16,$84.00 ,110982,,3690696615,General Fund
Dell Computer,98110,ITS,12/13/16,$90.88 ,110985,,3690697835,General Fund
2004 Thomas School Bus,98260,SCHOOL BOARD,12/14/16,"$1,680.00 ",,26-Apr,Cashiers Check,Enterprise
2004 Thomas School Bus,98259,SCHOOL BOARD,12/14/16,"$1,701.01 ",,Apr-73,Cashiers Check,Enterprise
2004 Thomas School Bus,98258,SCHOOL BOARD,12/14/16,"$2,351.10 ",,Apr-69,Cashiers Check,Enterprise
2001 Honda CBR 929RR,98256,POLICE STATE DRUG FUND,12/14/16,"$1,745.99 ",,1014297,Cashiers Check,Enterprise
2005 Mercury Montego,98255,POLICE STATE DRUG FUND,12/14/16,$945.00 ,,1066554,Money Order,Enterprise
2004 Chevrolet Tahoe,98250,POLICE STATE DRUG FUND,12/14/16,"$4,025.00 ",,170547,Cashiers Check,Enterprise
2006 Infiniti M45,98245,POLICE STATE DRUG FUND,12/14/16,"$3,125.60 ",,908862,Cashiers Check,Enterprise
2005 Honda Civic,98242,POLICE STATE DRUG FUND,12/14/16,"$1,375.00 ",,167387,3690705447,Enterprise
Main Stays Bath Set,98149,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/14/16,$24.00 ,PPEU-033-005,,3690705498,Enterprise
2 Bongo Head Wraps,98143,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/14/16,$12.00 ,PPEU-033-040,,3691102200,Enterprise
Husky Tool Bag w/Tools,98133,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/14/16,$35.00 ,PPEU-033-035A,,3690890767,Enterprise
Black & Decker Electric Weed Eater,98132,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/14/16,$13.26 ,PPEU-033-048,,3690969478,Enterprise
5 Extron Control Systems,98269,PUBLIC LIBRARY,12/15/16,$25.00 ,"105168, 105169, 105170, 105171, 105172",,3691172347,General Fund
Dayton Pallet Jack,98268,SURPLUS WAREHOUSE,12/15/16,$78.85 ,111091,,3690890770,Enterprise
White Industries Battery Charger,98262,SURPLUS WAREHOUSE,12/15/16,$73.00 ,111090,,3690967304,Enterprise
5 Dollies,98261,SURPLUS WAREHOUSE,12/15/16,$132.00 ,"111097, 111098, 111099, 111100, 111101",,3691172343,Enterprise
XBox 360,98172,POLICE STATE DRUG FUND,12/15/16,$36.35 ,PSDF-027C-204,,3691622675,Enterprise
5 Yamaha Surround Sound Speakers,98171,POLICE STATE DRUG FUND,12/15/16,$34.00 ,PSDF-027C-191,,3691035750,Enterprise
Lenovo Laptop,98168,POLICE STATE DRUG FUND,12/15/16,$117.00 ,PSDF-027C-195,,3690781738,Enterprise
Acer Laptop,98167,POLICE STATE DRUG FUND,12/15/16,$32.00 ,PSDF-027C-182,,3690781524,Enterprise
Samsung Speaker,98166,POLICE STATE DRUG FUND,12/15/16,$27.00 ,PSDF-027C-177,,Money Order,Enterprise
Sink,98164,SCHOOL BOARD FOOD SERVICE,12/15/16,$132.50 ,FSBS-0334,,Cashiers Check,Enterprise
Cashier,98163,SCHOOL BOARD FOOD SERVICE,12/15/16,$103.00 ,FSBS-0328,,Money Order,Enterprise
2 Rolling Carts,98162,SCHOOL BOARD FOOD SERVICE,12/15/16,$150.00 ,FSBS-0325B,,Cashiers Check,Enterprise
2 Rolling Carts,98161,SCHOOL BOARD FOOD SERVICE,12/15/16,$240.00 ,FSBS-0325A,,Cashiers Check,Enterprise
CVap,98159,SCHOOL BOARD FOOD SERVICE,12/15/16,$106.00 ,FSBS-0332,,Cashiers Check,Enterprise
CVap,98158,SCHOOL BOARD FOOD SERVICE,12/15/16,$431.00 ,FSBS-0330,,3691158852,Enterprise
CVap,98157,SCHOOL BOARD FOOD SERVICE,12/15/16,$411.00 ,FSBS-0331,,3691158848,Enterprise
File Cabinet,98156,GENERAL SERVICES,12/15/16,$21.00 ,108712,,3690796952,General Fund
File Cabinet,98155,GENERAL SERVICES,12/15/16,$20.30 ,108710,,3690796832,General Fund
File Cabinet,98154,GENERAL SERVICES,12/15/16,$16.00 ,108711,,3690796638,General Fund
Cabinet,98153,GENERAL SERVICES,12/15/16,$33.02 ,110469,,3690985841,General Fund
Nike Tennis Shoes Size: 11,98279,DRUG TASK FORCE,12/19/16,$51.57 ,TF-337-014CCC,,3690970094,Enterprise
Nike Tennis Shoes Size: 11.5,98276,DRUG TASK FORCE,12/19/16,$83.99 ,TF-337-014EEE,,3691117022,Enterprise
Nike Tennis Shoes Size: 11.5,98273,DRUG TASK FORCE,12/19/16,$84.00 ,TF-337-014YY,,3690969188,Enterprise
"Work Foce 24"" Bolt Cutters",98203,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$27.00 ,PPEU-034-025,,3691100393,Enterprise
Canon Digital Camera,98202,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$169.01 ,PPEU-034-040,,3691046336,Enterprise
Bose Bluetooth Mobile Speaker,98201,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$128.00 ,PPEU-034-041,,Cashiers Check,Enterprise
Auto Craft 2.25-Ton Floor Jack,98198,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$51.00 ,PPEU-034-006B,,3691063804,Enterprise
Michael Kors Purse & Wallet,98195,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$73.00 ,PPEU-034-001F,,3691154993,Enterprise
Michael Kors Wallet,98194,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/19/16,$86.00 ,PPEU-034-001E,,3691102202,Enterprise
Office Electronics,98190,HEALTH,12/19/16,$26.50 ,"110912, 110911, 110901, 11091-, 110909, 110908, 110886, 110913, 110904, 110907, 110898, 110888, 110887, 110899",,3691046335,General Fund
Slide,98188,SCHOOL BOARD FOOD SERVICE,12/19/16,$240.00 ,FSBS-0342,,3691117927,Enterprise
Ice Maker,98187,SCHOOL BOARD FOOD SERVICE,12/19/16,$411.00 ,FSBS-0343,,3690975374,Enterprise
Freezer,98186,SCHOOL BOARD FOOD SERVICE,12/19/16,$382.00 ,FSBS-0344,,Cashiers Check,Enterprise
Double Oven,98185,SCHOOL BOARD FOOD SERVICE,12/19/16,"$1,301.00 ",FSBS-0341,,3690975369,Enterprise
4 Chairs,98181,GENERAL SERVICES,12/19/16,$37.00 ,"109703, 109705, 109704, 109700",,Cashiers Check,General Fund
Copier,98177,WATER SERVICES,12/19/16,$173.00 ,WS-110939,,3690998234,Enterprise
"10"" Kicker Subwoofers w/Kenwood Amplifier",98336,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/20/16,$115.00 ,PPEU-035-019,,Cashiers Check,Enterprise
Laser Labs Tint Meter,98335,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/20/16,$21.00 ,PPEU-035-027,,3691127254,Enterprise
Ridgid Collated Screwdriver,98333,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/20/16,$42.00 ,PPEU-035-003,,3691105153,Enterprise
Glacier Bay Bathroom Faucet,98332,POLICE STATE FELONY FORFEITURE,12/20/16,$35.00 ,PSFF-035B-191,,3691144464,Enterprise
Sony DVD Home Theater System,98323,POLICE STATE FELONY FORFEITURE,12/20/16,$68.01 ,PSFF-035B-177,,3691035757,Enterprise
JVC Stereo Receiver,98322,POLICE STATE FELONY FORFEITURE,12/20/16,$75.44 ,PSFF-035B-178,,3691115894,Enterprise
"Hero 24"" Rims",98319,POLICE STATE FELONY FORFEITURE,12/20/16,$530.00 ,PSFF-035B-133,,3691172236,Enterprise
Serving Line,98293,SCHOOL BOARD FOOD SERVICE,12/20/16,$239.00 ,"FSBS-0327, FSBS-0329",,Money Order,Enterprise
Jordan Tennis Shoes Size: 11,98289,DRUG TASK FORCE,12/20/16,$70.01 ,TF-337-014PPP,,3691167684,Enterprise
Jordan Tennis Shoes Size: 11,98288,DRUG TASK FORCE,12/20/16,$75.99 ,TF-337-014OOO,,3691593466,Enterprise
Jordan Tennis Shoes Size: 11,98287,DRUG TASK FORCE,12/20/16,$132.00 ,TF-337-014NNN,,3691091478,Enterprise
Jordan Tennis Shoes Size: 11,98284,DRUG TASK FORCE,12/20/16,$89.01 ,TF-337-014JJJ,,3691270016,Enterprise
Jordan Tennis Shoes Size: 11,98283,DRUG TASK FORCE,12/20/16,$160.00 ,TF0337-014III,,3691143712,Enterprise
Perforated Paper,98218,ITS,12/20/16,$185.99 ,110620,,Money Order,General Fund
Television,98217,GENERAL SERVICES,12/20/16,$38.00 ,109634,,3691078188,General Fund
File Cabinet,98208,GENERAL SERVICES,12/20/16,$70.00 ,109606,,3691190858,General Fund
File Cabinet,98207,GENERAL SERVICES,12/20/16,$83.00 ,109608,,3691190715,General Fund
2 Camcorders,98205,POLICE DEPARTMENT,12/20/16,$156.00 ,"110401, 110402",,Cashiers Check,General Fund
File Cabinet,98204,POLICE DEPARTMENT,12/20/16,$37.13 ,109609,,3691032793,General Fund
Federal Signal Siren Amps (Emergency Provider Only),98385,SURPLUS WAREHOUSE,12/21/16,$25.00 ,111049,,3691103103,Enterprise
2006 Honda Ridgeline,98384,POLICE STATE DRUG FUND,12/21/16,"$3,333.01 ",,1066401,Cashiers Check,Enterprise
1999 Honda Civic,98383,POLICE STATE DRUG FUND,12/21/16,"$1,728.59 ",,191553,Cashiers Check,Enterprise
2001 Dodge Durango,98382,POLICE STATE DRUG FUND,12/21/16,"$1,205.00 ",,1054086,3691132411,Enterprise
1998 Chevrolet Astro,98376,POLICE STATE DRUG FUND,12/21/16,"$1,325.00 ",,166581,Cashiers Check,Enterprise
"Samsung 46"" LED TV",98375,POLICE STATE DRUG FUND,12/21/16,$150.00 ,PSDF-028-002,,3691130877,Enterprise
"Samsung 51"" Plasma Smart TV",98372,POLICE STATE DRUG FUND,12/21/16,$202.18 ,PSDF-028-009,,3691121338,Enterprise
"Ryobi 7-1/4"" Miter Saw",98346,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/21/16,$43.00 ,PPEU-035-021,,3691097124,Enterprise
Husqvarna Back Pack Blower,98344,POLICE PROPERTY AND EVIDENCE UNCLAIMED,12/21/16,$160.01 ,PPEU-035-033,,Money Order,Enterprise
Table,98235,GENERAL SERVICES,12/21/16,$22.01 ,110048,,3691153763,General Fund
5 Chairs,98233,GENERAL SERVICES,12/21/16,$19.00 ,"109697, 109715, 109699, 109698, 110053",,Cashiers Check,General Fund
2 Chairs,98225,GENERAL SERVICES,12/21/16,$20.00 ,"109716, 109967",,3691257436,General Fund
Chair,98223,GENERAL SERVICES,12/21/16,$71.88 ,109303,,3691190923,General Fund
Explanation / Answer
main.cpp
#include <algorithm>
#include <iostream>
#include <time.h>
#include "CSVparser.hpp"
using namespace std;
//============================================================================
// Global definitions visible to all methods and classes
//============================================================================
// forward declarations
double strToDouble(string str, char ch);
// define a structure to hold bid information
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
//============================================================================
// Static methods used for testing
//============================================================================
/**
* Display the bid information to the console (std::out)
*
* @param bid struct containing the bid info
*/
void displayBid(Bid bid) {
cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
<< bid.fund << endl;
return;
}
/**
* Prompt user for bid information using console (std::in)
*
* @return Bid struct containing the bid info
*/
Bid getBid() {
Bid bid;
cout << "Enter Id: ";
cin.ignore();
getline(cin, bid.bidId);
cout << "Enter title: ";
getline(cin, bid.title);
cout << "Enter fund: ";
cin >> bid.fund;
cout << "Enter amount: ";
cin.ignore();
string strAmount;
getline(cin, strAmount);
bid.amount = strToDouble(strAmount, '$');
return bid;
}
/**
* Load a CSV file containing bids into a container
*
* @param csvPath the path to the CSV file to load
* @return a container holding all the bids read
*/
vector<Bid> loadBids(string csvPath) {
cout << "Loading CSV file " << csvPath << endl;
// Define a vector data structure to hold a collection of bids.
vector<Bid> bids;
// initialize the CSV Parser using the given path
csv::Parser file = csv::Parser(csvPath);
try {
// loop to read rows of a CSV file
for (unsigned int i = 0; i < file.rowCount(); i++) {
// Create a data structure and add to the collection of bids
Bid bid;
bid.bidId = file[i][1];
bid.title = file[i][0];
bid.fund = file[i][8];
bid.amount = strToDouble(file[i][4], '$');
//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
// push this bid to the end
bids.push_back(bid);
}
} catch (csv::Error &e) {
std::cerr << e.what() << std::endl;
}
return bids;
}
// FIXME (2a): Implement the quick sort logic over bid.title
/**
* Partition the vector of bids into two parts, low and high
*
* @param bids Address of the vector<Bid> instance to be partitioned
* @param begin Beginning index to partition
* @param end Ending index to partition
*/
int partition(vector<Bid>& bids, int begin, int end) {
int l = begin;
int h = end;
int pivot = (begin + (end - begin) / 2);
bool finished = false;
// this while loops continually increments the low point as long as it's below the pivot
// then continually decrements the high point as long as it's above the pivot
while(!finished) {
while(bids[l].title.compare(bids[pivot].title) < 0) {
++l;
}
while(bids[pivot].title.compare(bids[h].title) < 0) {
--h;
}
if (l >= h) {
finished = true;
// if variable l is not greater than or equal to h the two bids are swapped
} else {
swap(bids[l] , bids[h]);
//bring end points closer to one another
++l;
--h;
}
}
return h;
}
/**
* Perform a quick sort on bid title
* Average performance: O(n log(n))
* Worst case performance O(n^2))
*
* @param bids address of the vector<Bid> instance to be sorted
* @param begin the beginning index to sort on
* @param end the ending index to sort on
*/
void quickSort(vector<Bid>& bids, int begin, int end) {
unsigned int middle = 0;
// make sure the algorithm stops running if there are 1 or 0 bids left to sort
if (begin >= end) {
return;
}
// this code partitions the bids into lower and higher sections
middle = partition(bids, begin, end);
// function is called recursively to sort the individual partitions
// first call sorts the initial element to the midpoint
quickSort(bids, begin, middle);
// second call sorts the middle + 1th element to the endpoint
quickSort(bids, middle + 1, end);
}
// FIXME (1a): Implement the selection sort logic over bid.title
/**
* Perform a selection sort on bid title
* Average performance: O(n^2))
* Worst case performance O(n^2))
*
* @param bid address of the vector<Bid>
* instance to be sorted
*/
void selectionSort(vector<Bid>& bids) {
// this creates an index to the smallest minimum bid found
unsigned int smallest;
unsigned int largest = bids.size();
// place designates the position at which bids are sorted/unsorted
for (unsigned place = 0; place < largest; ++place) {
smallest = place;
for (unsigned j = place + 1; j < largest; ++j) {
if (bids[j].title.compare(bids[smallest].title) < 0) {
smallest = j;
}
}
if (smallest != place)
swap(bids[place], bids[smallest]);
}
}
/**
* Simple C function to convert a string to a double
* after stripping out unwanted char
*
* credit: http://stackoverflow.com/a/24875936
*
* @param ch The character to strip out
*/
double strToDouble(string str, char ch) {
str.erase(remove(str.begin(), str.end(), ch), str.end());
return atof(str.c_str());
}
/**
* The one and only main() method
*/
int main(int argc, char* argv[]) {
// process command line arguments
string csvPath;
switch (argc) {
case 2:
csvPath = argv[1];
break;
default:
csvPath = "eBid_Monthly_Sales_Dec_2016.csv";
}
// Define a vector to hold all the bids
vector<Bid> bids;
// Define a timer variable
clock_t ticks;
int choice = 0;
while (choice != 9) {
cout << "Menu:" << endl;
cout << " 1. Load Bids" << endl;
cout << " 2. Display All Bids" << endl;
cout << " 3. Selection Sort All Bids" << endl;
cout << " 4. Quick Sort All Bids" << endl;
cout << " 9. Exit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
bids = loadBids(csvPath);
cout << bids.size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 2:
// Loop and display the bids read
for (unsigned int i = 0; i < bids.size(); ++i) {
displayBid(bids[i]);
}
cout << endl;
break;
// FIXME (1b): Invoke the selection sort and report timing results
case 3:
ticks = clock();
// call selectionSort method to sort the loaded bids
selectionSort(bids);
cout << bids.size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
// FIXME (2b): Invoke the quick sort and report timing resultscase 3:
case 4:
ticks = clock();
// call quickSort method to sort the loaded bids
quickSort(bids, 0, bids.size() - 1);
cout << bids.size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
}
}
cout << "Good bye." << endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.