C++ ASSIGNMENT!

We provide a starter console program that uses a menu to enable testing of the sort logic you will complete. It also allows you to pass in the path to the bids CSV file to be loaded, enabling you to try both files. In this version, the following menu is presented when the program is run:

Menu:

1. 1. Load Bids
   2. Display All Bids
   3. Selection Sort All Bids
   4. QuickSort All Bids
   9. Exit

Enter choice:

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 must complete:

void selectionSort(vector& bids) void quickSort(vector& bids, int begin, int end) int partition(vector& bids, int begin, int end)

Prompt

You will need to perform the following steps to complete this activity:

Setup: Begin by creating a new C++ project with a project type of "Hello World C++ Project".

1. Name the project VectorSorting. Remember to pick the correct compiler in Toolchains and click Finish. This will create a simple VectorSorting.cpp source file under the /src directory.
2. Download the starter program files and copy them to the projects /src directory, replacing the existing auto-generated ones. Remember to right-click on the project in the Project Explorer pane on the left and Refresh the project so it adds all the new files to the src folder underneath.
3. Because this activity uses C++ 11 features, you may need to add the -std=c++11 compiler switch to the miscellaneous settings.

Task 1: Implement the selection sort algorithm:

1. Code the selection sort logic using bid.title as the sort field.
2. Invoke the selectionSort() method from the main() method including collecting and reporting timing results.

Task 2: Implement the quicksort algorithm:

1. Code the quicksort logic using bid.title as the sort field.
2. Invoke the quickSort() method from the main() method including collecting and reporting timing results.

Here is sample output from running the completed program:

> ./VectorSorting ~/Downloads/eBid_Monthly_Sales.csv > VectorSorting.exe Downloads\eBid_Monthly_Sales.csv

THIS IS THE CODE I NEED TO FIX CAN SOMEONE SHOW ME STEP BY STEP THE ADDED/CHANGE IN CODE:

// 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) {

//set low and high equal to begin and end

// pick the middle element as pivot point

// while not done

// keep incrementing low index while bids[low] < bids[pivot]

// keep decrementing high index while bids[pivot] < bids[high]

/* If there are zero or one elements remaining,

all bids are partitioned. Return high */

// else swap the low and high bids (built in vector method)

// move low and high closer ++low, --high

//return high;

}

/**

* 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) {

//set mid equal to 0

/* Base case: If there are 1 or zero bids to sort,

partition is already sorted otherwise if begin is greater

than or equal to end then return*/

/* Partition bids into low and high such that

midpoint is location of last element in low */

// recursively sort low partition (begin to mid)

// recursively sort high partition (mid+1 to 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) {

//define min as int (index of the current minimum bid)

// check size of bids vector

// set size_t platform-neutral result equal to bid.size()

// pos is the position within bids that divides sorted/unsorted

// for size_t pos = 0 and less than size -1

// set min = pos

// loop over remaining elements to the right of position

// if this element's title is less than minimum title

// this element becomes the minimum

// swap the current minimum with smaller one found

// swap is a built in vector method

}

/**

* 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

}

}