This is my programming assignment. I am stuck on the addItem method. At approxim

Question

This is my programming assignment. I am stuck on the addItem method. At approximately line 77 I did something wrong. I need you to help my get that line correct. This is using a vector array doing bucket sorting.

#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 BucketsCollection;

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

const unsigned long ULONGMAX = 4294967295;

class BucketsCollection {
public:
   BucketsCollection(const unsigned int numBuckets);
   ~BucketsCollection() {}
   void addItem(unsigned long item);
   unsigned int getNumBuckets() const;
   unsigned int getNumItemsInABucket(const unsigned int bucket) const;
   vector& getBucket(const unsigned int bucket);
   void copyOneBucketsIntoAnotherBuckets(BucketsCollection& smallBucket);
   void printAllBuckets() const;

private:
   vector< vector > arr;
   unsigned int buckets;
   unsigned long range;

};

//*** Provide methods for the bucket class ***
BucketsCollection::BucketsCollection(const unsigned int numBuckets) {
   arr.resize(numBuckets);
   buckets = numBuckets;
   if (numBuckets > 1) {
       range = (ULONGMAX / buckets) + 1;
   }
   else {
       range = ULONGMAX;
   }
}

void BucketsCollection::addItem(unsigned long item) {
   //TODO:
   //vector &myBucket = item;
  

   arr[index].push_back(item / range);

   //push.back arr = data div range;
   // put in all pieces of data with a loop
}

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

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

void BucketsCollection::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& BucketsCollection::getBucket(const unsigned int bucket) {
   return arr[bucket];
}

void BucketsCollection::copyOneBucketsIntoAnotherBuckets(BucketsCollection& smallBucket) {
   //Copies all items in all buckets from one BucketsCollection object into another BucketsCollection object.
   //Not for the first part of the homework assignment, only the multithreaded part.

   //for ( )

}

//***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 t he values into the appropriate buckets.
   //globalBuckets->
   //call additem

   //passes it and says here is what I need you to pass in
}

void sortEachBucket() {

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

   //sort the bucket. grab the buckets one by one as many times as there are buckets
   //getbucket grabs the bucket
}

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.

}

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(" For timing purposes, please make sure any debugging printf statements you added are commented 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;
}

Explanation / Answer

// C++ program to sort an array using bucket sort #include #include #include using namespace std; // Function to sort arr[] of size n using bucket sort void bucketSort(float arr[], int n) { // 1) Create n empty buckets vector b[n]; // 2) Put array elements in different buckets for (int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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