For this assignment, we want to implement a straightforward bucket sort. The assignment is split into three parts. 1) Moving items into a bucket, 2) Sorting each bucket, and 3) Moving buckets back into the input array. The rest of the assignment's structure has been given to you. What will be most helpful for you is a Buckets class that allows you to move data into and out of buckets, so you don't have to worry about managing a collection of collections.

The Buckets object is organized like so:

class BucketsCollection{ public: 

BucketsCollection(int bucketCapacity, int numBuckets); ~BucketsCollection(); void addItem(int bucket, unsigned long item); int getNumBuckets();

 int getNumItemsInABucket(int bucket); unsigned long * getBucketArray(int bucket); void copyBucketToAnotherArray(int bucket, 

 unsigned long * destinationArray, 

 int destinationArrayOffsetIndex); void copyOneBucketsIntoAnotherBuckets(BucketsCollection& smallBucket); 

 void printAllBuckets(); 

private: unsigned long **buckets; int *itemCounter; int bucketSize; int numBuckets; 

};

The constructor simply lets you create a buckets object signifying how big each bucket should be, and how many buckets this collection contains. For example, if (100,4) were passed in, each bucket could hold 100 items, and there would be 4 buckets. As a good rule of thumb, if you have 100 items in your input, you should still make each bucket max out to 100 as well. It's inefficient, but you don't know if all items will distribute nicely across all buckets or fall into one bucket.

The addItem() method simply adds a number into the specified bucket.

The getNumBuckets() method returns how many buckets this collection holds. If you passed in 4 buckets in the constructor, then this method will return 4.

The getNumItemsInABucket() will tell how much of a bucket is currently used, not the overall capacity. If the capacity is 100 but only 27 items have been placed into that bucket, this method will return 27.

The getBucketArray() method returns a pointer to the bucket as if it were an array. For example, if you pass in 2, it will return the address of the first item in bucket 2.

The copyBucketToAnotherArray() method allows you to dump all items in a bucket into an array. You specify which bucket, the output array, and where it should start writing the results in the output array.

The printAllBuckets() method is used for debugging purposes. It displays all buckets contents to the console. It also prints all items in hexadecimal, which greatly aids in determining which item should go into which bucket.

There are also a few global variables which will assist you in completing this assignment:

unsigned long *list; int listSize; int numBuckets; int numThreads; BucketsCollection *globalBuckets; unsigned long ULONGMAX = 4294967295; 

list is your array of items. listSize is the capacity of the array. numBuckets holds how many buckets are in the collection object. numThreads will help with a future assignment globalBuckets is your container holding all the individual buckets. ULONGMAX will help with math to determine which value goes into which bucket.

These were made global for the upcoming multithreaded assignment.

Regarding the three parts of the assignment:

1) Moving items into a bucket. You need to go through the list array, element by element, and put each element into the appropriate bucket. To do that, you need to do some math to figure out in which bucket it belongs. Note that the values in list will be randomly generated and will be between (and including) 0 through ULONGMAX.

2) Sorting each bucket. I provided a recQuickSort method for you. You simply need to get the bucket as an array, and specify the starting point in the array, and the capacity of the bucket.

3) Moving buckets back into the input array. For each bucket, you need to simply copy the bucket back out to the list array, making sure to offset it correctly based on how many items have been written to up to that point.

#include  #include  #include  #include  //C++11 support! Visual studio 2012+ users can use this if they want. #include  //To prevent those using g++ from trying to use a library //they don't have #ifndef __GNUC__ #include  #else #include  #endif using namespace std; //*** Prototypes *** void recQuickSort(unsigned long *arr, int first, int last); void pressAnyKeyToContinue(); class BucketsCollection { public: BucketsCollection(int bucketCapacity, int numBuckets); ~BucketsCollection(); void addItem(int bucket, unsigned long item); int getNumBuckets(); int getNumItemsInABucket(int bucket); unsigned long * getBucketArray(int bucket); void copyBucketToAnotherArray(int bucket, unsigned long * destinationArray, int destinationArrayOffsetIndex); void copyOneBucketsIntoAnotherBuckets(BucketsCollection& smallBucket); void printAllBuckets(); private: unsigned long **buckets; int *itemCounter; int bucketSize; int numBuckets; }; //***GLOBAL VARIABLES*** unsigned long *list; int listSize; int numBuckets; int numThreads; BucketsCollection *globalBuckets; unsigned long ULONGMAX = 4294967295; //*** Provide methods for the bucket class *** BucketsCollection::BucketsCollection(int bucketCapacity, int numBuckets) { //Each bucket should be as bg as roughly the size of the list divided by number of buckets. //But some buckets will be bigger than others, so give an extra room. this->numBuckets = numBuckets; //Worst case scenario is that every value falls into one bucket. Assume the worst case could //happen and make sure each bucket could handle that much data. buckets = new unsigned long*[numBuckets]; for (int i = 0; i < numBuckets; i++) { //printf("Requsting %d items for this bucket ", listSize); buckets[i] = new unsigned long[bucketCapacity]; } itemCounter = new int[numBuckets]; for (int i = 0; i < numBuckets; i++) { itemCounter[i] = 0; } } BucketsCollection::~BucketsCollection() { for (int i = 0; i < numBuckets; i++) { delete[] buckets[i]; } delete[] buckets; delete[] itemCounter; } void BucketsCollection::addItem(int bucket, unsigned long item) { //Pass in a bucket #, and the data, and it assigns that data to the bucket. buckets[bucket][itemCounter[bucket]] = item; itemCounter[bucket]++; } int BucketsCollection::getNumBuckets() { return numBuckets; } int BucketsCollection::getNumItemsInABucket(int bucket) { //You pass in the bucket #, it returns how many items that bucket contains. return itemCounter[bucket]; } void BucketsCollection::printAllBuckets() { //Displays the contents of all buckets to the screen. printf("****** "); for (int i = 0; i < numBuckets; i++) { printf("Bucket number %d ", i); for (int j = 0; j < itemCounter[i]; j++) { //cout << buckets[i][j] << " "; printf("%08X ", buckets[i][j]); } printf(" "); } printf(" "); } unsigned long * BucketsCollection::getBucketArray(int bucket) { //You pass in the bucket #, it returns the array that contains the bucket's data. return buckets[bucket]; } void BucketsCollection::copyBucketToAnotherArray(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]; } } void BucketsCollection::copyOneBucketsIntoAnotherBuckets(BucketsCollection& smallBucket) { //Copies all items in all buckets from one BucketsCollection object into another BucketsCollection object. for (int i = 0; i < numBuckets; i++) { unsigned long * smallBucketArray = smallBucket.getBucketArray(i); //printf("Copying %d items between bucket %d ", getNumItemsInABucket(bucket), bucket); for (int j = 0; j < smallBucket.getNumItemsInABucket(i); j++) { //printf("Copying %8X at index %d from small into big between bucket %d ", smallBucketArray[i], i, bucket); addItem(i, smallBucketArray[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 = new unsigned long[listSize]; //generate random numbers srand(time(NULL)); unsigned long num1; unsigned long num2; unsigned long num3; //generates 32 bit numbers for (int i = 0; i < listSize; i++) { //Make 15 bit numbers. On Windows they're already 15 bit. //But in case the rand() gives us bigger random numbers, lets just make //everything 15 bit by only preserving the last 15 bits. Then work with //what we've got and combine it back into a 32 bit number. num1 = rand() & 0x00007FFF; num2 = rand() & 0x00007FFF; num3 = rand() & 0x00007FFF; //shift num1 over 15 bits num1 = num1 << 15; //make a 30 bit number num1 = num1 | num2; //get two more bits num3 = num3 << 30; num3 = num3 & 0xC0000000; //make it a 32 bit number list[i] = num3 | num1; } } void placeIntoBuckets() { //TODO: Put the values into the appropriate buckets. } void sortEachBucket() { //TODO: Sort each individual bucket } void combineBuckets() { //TODO: Copy each bucket back out to the original 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. } } void swap(unsigned long *arr, int first, int second) { unsigned long temp; temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; } int partition(unsigned long *arr, int first, int last) { unsigned long pivot; int index, smallIndex; //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(arr, smallIndex, index); } } //Move pivot into the sorted location swap(arr, first, smallIndex); //Tell where the pivot is return smallIndex; } void recQuickSort(unsigned long *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(unsigned long *arr, unsigned int arraySize) { for (int i = 1; i < arraySize; i++) { if (arr[i] < arr[i - 1]) { printf("ERROR, this list was not sorted correctly. At index %d is value %08X. At index %d is value %08X ", i - 1, arr[i - 1], i, arr[i]); return; } } printf("PASSED SORT TEST - The list was sorted correctly "); } 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() { //Set the listSize, numBuckets, and numThreads global variables. listSize = 100; numBuckets = 2; numThreads = 2; createList(); globalBuckets = new BucketsCollection(listSize, 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); pressAnyKeyToContinue(); delete globalBuckets; delete[] list; numBuckets = 4; numThreads = 4; createList(); printf(" Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads); globalBuckets = new BucketsCollection(listSize, numBuckets); pressAnyKeyToContinue(); bucketSort(true); verifySort(list, listSize); pressAnyKeyToContinue(); delete globalBuckets; delete[] list; printf(" For timing purposes, please make sure all printf statements are commented out "); pressAnyKeyToContinue(); listSize = 4000000; numBuckets = 1; numThreads = 1; createList(); globalBuckets = new BucketsCollection(listSize, 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(); std::chrono::duration diff = end - start; printf("Finished quick sort simulation in %1.3lf milliseconds ", diff.count()); verifySort(list, listSize); delete globalBuckets; delete[] list; listSize = 4000000; numBuckets = 2; numThreads = 2; createList(); globalBuckets = new BucketsCollection(listSize, 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; printf("Finished bucket sort in %1.3lf milliseconds ", diff.count()); verifySort(list, listSize); delete globalBuckets; delete[] list; numBuckets = 4; numThreads = 4; createList(); globalBuckets = new BucketsCollection(listSize, 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; printf("Finished bucket sort in %1.3lf milliseconds ", diff.count()); verifySort(list, listSize); delete globalBuckets; delete[] list; numBuckets = 8; numThreads = 8; createList(); globalBuckets = new BucketsCollection(listSize, 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; printf("Finished bucket sort in %1.3lf milliseconds ", diff.count()); verifySort(list, listSize); delete globalBuckets; delete[] list; numBuckets = 16; numThreads = 16; createList(); globalBuckets = new BucketsCollection(listSize, 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; printf("Finished bucket sort in %1.3lf milliseconds ", diff.count()); verifySort(list, listSize); delete globalBuckets; delete[] list; pressAnyKeyToContinue(); return 0; }