Having about 3 errors with this C++ code. Please help me get this running.

#include

#include

#include //C++11 support! Visual studio 2012+ users can use this if they want.

#include

#include

#include

#include

#include

//To prevent those using g++ from trying to use a library

//they don't have

#ifndef __GNUC__

#include

#else

#include

#endif

using std::cout;

using std::endl;

using std::vector;

using std::unique_ptr;

using std::string;

//*** Prototypes *** void recQuickSort(vector& arr, int first, int last); void pressAnyKeyToContinue(); class ManyBuckets;

//***GLOBAL VARIABLES*** unique_ptr list; int listSize; int numBuckets; int numThreads; unique_ptr globalBuckets;

const unsigned long ULONGMAX = 4294967295;

class ManyBuckets { public: ManyBuckets(const unsigned int numBuckets); ~ManyBuckets() {} void addItem(int bucket, unsigned long item); unsigned int getNumBuckets() const; unsigned int getNumItemsInABucket(const unsigned int bucket) const; vector& getBucket(const unsigned int bucket); //void copyManyBucketsToManyBuckets(ManyBuckets& smallBucket); void copyManyBucketsToManyBuckets(int bucket, unsigned long * destinationArray, int destinationArrayOffsetIndex); void printAllBuckets() const;

private: unsigned long **buckets; int *itemCounter; int bucketSize; int numBuckets; vector< vector > arr; unsigned int buckets; int *itemCounter;

};

//*** Provide methods for the bucket class *** ManyBuckets::ManyBuckets(const unsigned int numBuckets) { arr.resize(numBuckets); buckets = numBuckets;

}

void ManyBuckets::addItem( int bucket, unsigned long item) { //TODO:

//Added--------------------------------------------------------- buckets[bucket][itemCounter[bucket]] = item; itemCounter[bucket]++; }

unsigned int ManyBuckets::getNumBuckets() const { return buckets; }

unsigned int ManyBuckets::getNumItemsInABucket(const unsigned int bucket) const { return arr[bucket].size(); }

void ManyBuckets::printAllBuckets() const { //Displays the contents of all buckets to the screen.

// just uncomment this code when you have arr properly declared as a data member printf("****** "); for (int i = 0; i < numBuckets; i++) { printf("bucket number %d ", i); for (unsigned int j = 0; j < arr[i].size(); j++) { printf("%08x ", arr[i][j]);

} printf(" "); } printf(" "); }

vector& ManyBuckets::getBucket(const unsigned int bucket) { return arr[bucket]; }

void ManyBuckets::copyManyBucketsToManyBuckets(int bucket, unsigned long * destinationArray, int destinationArrayOffsetIndex) { //Copies a bucket to an array. You pass in the bucket #, the array, and the starting index (offset) or the array you are copying to //This then copies that bucket # into that array starting at that index (offset).

for (int j = 0; j < itemCounter[bucket]; j++) { destinationArray[destinationArrayOffsetIndex + j] = buckets[bucket][j]; }

}

//***Functions that help our bucket sort work.*** void printList() { for (int i = 0; i < listSize; i++) { //cout << list[i] << " "; printf("%08x ", list[i]); } }

void createList() { list = std::make_unique(listSize);

std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(0, ULONGMAX);

for (int i = 0; i < listSize; i++) { list[i] = dis(gen); } } void placeIntoBuckets() {

//TODO: Put the values into the appropriate buckets. //globalBuckets->

//Added--------------------------------------------------------- int bucketNum; int bucketRange; bucketRange = (ULONGMAX / numBuckets);

for (int i = 0; i < listSize; i++) { //divide the elements of the array to get the bucket number bucketNum = (list[i] / bucketRange);

//place the elements in the correct bucket globalBuckets->addItem(bucketNum, list[i]); }

}

void sortEachBucket() {

//TODO: Sort each individual bucket //vector &myBucket = blahblablah->getBucket(blah blah blah);

//Added--------------------------------------------------------- for (int i = 0; i < numBuckets; i++) { recQuickSort(globalBuckets->getBucket(i), 0, globalBuckets->getNumItemsInABucket(i)); } }

void combineBuckets() { //TODO: Copy each bucket back out to the original list[] array

//Loop for the amount of buckets //Get the individual bucket out of the globalBuckets //Copy all items from that individual bucket into the list array. //Added--------------------------------------------------------- int offset = 0; for (int i = 0; i < numBuckets; i++) { globalBuckets->copyManyBucketsToManyBuckets(i, list, offset); offset = offset + globalBuckets->getNumItemsInABucket(i); } }

void bucketSort(bool displayOutput) {

//For the upcoming homeowork assignment, I think it will help you the most to split your work into these three functions. placeIntoBuckets();

if (displayOutput) { printf("Displaying each bucket's contents before sorting: "); globalBuckets->printAllBuckets(); }

sortEachBucket();

combineBuckets();

if (displayOutput) { printf("Displaying each bucket's contents after sorting: "); globalBuckets->printAllBuckets(); pressAnyKeyToContinue(); printf("Displaying what is hopefully a sorted array: "); printList(); //See if it's all sorted. } }

int partition(vector& arr, int first, int last) { unsigned long pivot; int index, smallIndex;

unsigned long temp;

//Take the middle value as the pivot. //swap(first, (first + last) / 2); pivot = arr[first]; smallIndex = first; for (index = first + 1; index < last; index++) { if (arr[index] < pivot) { smallIndex++; //swap the two temp = arr[smallIndex]; arr[smallIndex] = arr[index]; arr[index] = temp; } }

//Move pivot into the sorted location temp = arr[first]; arr[first] = arr[smallIndex]; arr[smallIndex] = temp;

//Tell where the pivot is return smallIndex;

}

void recQuickSort(vector& arr, int first, int last) { //first is the first index //last is the one past the last index (or the size of the array //if first is 0)

if (first < last) { //Get this sublist into two other sublists, one smaller and one bigger int pivotLocation = partition(arr, first, last); recQuickSort(arr, first, pivotLocation); recQuickSort(arr, pivotLocation + 1, last); } }

void verifySort(unique_ptr& arr, unsigned int arraySize, std::chrono::duration& diff, const string& sortTest) { double val = diff.count(); for (unsigned int i = 1; i < arraySize; i++) { if (arr[i] < arr[i - 1]) { printf(" "); printf("------------------------------------------------------ "); printf("SORT TEST %s ", sortTest.c_str());

if (val != 0.0) { printf("Finished bucket sort in %1.16lf milliseconds ", diff.count()); } printf("ERROR - This list was not sorted correctly. At index %d is value %08X. At index %d is value %08X ", sortTest.c_str(), i - 1, arr[i - 1], i, arr[i]); printf("------------------------------------------------------ ");

return; } } printf(" "); printf("------------------------------------------------------ "); printf("SORT TEST %s ", sortTest.c_str()); if (val != 0.0) { printf("Finished bucket sort in %1.16lf milliseconds ", diff.count()); } printf("PASSED SORT TEST - The list was sorted correctly ", sortTest.c_str()); printf("------------------------------------------------------ "); }

void pressAnyKeyToContinue() { printf("Press any key to continue ");

//Linux and Mac users with g++ don't need this //But everyone else will see this message. #ifndef __GNUC__ _getch(); #else int c; fflush(stdout); do c = getchar(); while ((c != ' ') && (c != EOF)); #endif

}

int main() {

std::chrono::duration diff{ 0 };

//Set the listSize, numBuckets, and numThreads global variables. listSize = 100;

numBuckets = 2; numThreads = 2; createList(); globalBuckets = std::make_unique(numBuckets); printf(" Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); // printf("Displaying the unsorted list array: "); // printList(); //useful for debugging small amounts of numbers. pressAnyKeyToContinue(); bucketSort(true); verifySort(list, listSize, diff, "2 buckets"); pressAnyKeyToContinue();

numBuckets = 4; numThreads = 4; createList(); printf(" Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); globalBuckets = std::make_unique(numBuckets); pressAnyKeyToContinue(); bucketSort(true); verifySort(list, listSize, diff, "4 buckets"); pressAnyKeyToContinue();

printf(" If you manually placed any printf statements, remove them from here on out "); pressAnyKeyToContinue();

listSize = 4000000; numBuckets = 1; numThreads = 1; createList(); globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d, this is effectively a quick sort ", listSize, numBuckets, numThreads); auto start = std::chrono::high_resolution_clock::now(); bucketSort(false); auto end = std::chrono::high_resolution_clock::now(); verifySort(list, listSize, diff, "4000000 items in 1 bucket - BASELINE");

listSize = 4000000; numBuckets = 2; numThreads = 2; createList(); globalBuckets = std::make_unique(numBuckets); // printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 2 buckets");

numBuckets = 4; numThreads = 4; createList(); globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 4 buckets");

numBuckets = 8; numThreads = 8; createList(); globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 8 buckets");

numBuckets = 16; numThreads = 16; createList(); globalBuckets = std::make_unique(numBuckets); //printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); start = std::chrono::high_resolution_clock::now(); bucketSort(false); end = std::chrono::high_resolution_clock::now(); diff = end - start; verifySort(list, listSize, diff, "4000000 items in 16 buckets");

pressAnyKeyToContinue(); return 0; }