For this assignment, we want to implement a straightforward bucket sort. The ass
ID: 3681834 • Letter: F
Question
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:
BucketsCollection(int bucketCapacity, int numBuckets); ~BucketsCollection();
void addItem(int bucket, unsigned long item);
int getNumBuckets();
};
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:
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.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <thread> //C++11 support! Visual studio 2012+ users can use this if they want.
#include <mutex>
//To prevent those using g++ from trying to use a library
//they don't have
#ifndef __GNUC__
#include <conio.h>
#else
#include <stdio.h>
#endif
using namespace std;
//*** Prototypes ***
void recQuickSort(unsigned long *arr, int first, int last);
//TIMING CODE
#ifndef _RCTIMER_H_
#define _RCTIMER_H_
#if defined(_WIN32) || defined(WIN32)
#define ONWINDOWS
#define BIGNUM ULONG64
#elif defined(__APPLE__) || defined(__MACH__)
#define ONMAC
#define BIGNUM uint64_t
#elif defined(unix) || defined(__unix) || defined (__unix__) // Includes Linux.
#define ONUNIX
#define BIGNUM uint64_t
#warning "Gotta link it with librt on Linux."
#warning "g++ -o out <sources> -lrt"
#endif
extern "C" {
#if defined(ONWINDOWS)
#include <windows.h>
#elif defined(ONMAC)
#include <mach/mach.h>
#include <mach/mach_time.h>
#include <stdint.h> // uint64_t (for nanoseconds)
#elif defined(ONUNIX)
#include <time.h>
#include <stdint.h> // uint64_t (for nanoseconds)
#endif
}
class RCTimer{
public:
RCTimer();
~RCTimer();
void clear();
void start();
void stop();
double getElapsedSeconds();
double getElapsedMilliseconds();
double getElapsedMicroseconds();
private:
#if defined(ONWINDOWS)
LARGE_INTEGER begin;
LARGE_INTEGER end;
LARGE_INTEGER frequency;
void setCurrentTime(LARGE_INTEGER&);
#elif defined(ONMAC)
uint64_t begin;
uint64_t end;
mach_timebase_info_data_t sTimebaseInfo;
void setCurrentTime(uint64_t&);
#elif defined(ONUNIX)
timespec begin;
timespec end;
void setCurrentTime(timespec&);
#endif
BIGNUM getElapsedNanoseconds();
};
RCTimer::RCTimer(){
#if defined(ONWINDOWS)
QueryPerformanceFrequency(&this->frequency);
#elif defined(ONMAC)
mach_timebase_info(&this->sTimebaseInfo);
#endif
this->clear();
}
RCTimer::~RCTimer(){
}
void RCTimer::clear(){
#if defined(ONWINDOWS)
this->begin.QuadPart = 0;
this->end.QuadPart = 0;
#elif defined(ONMAC)
this->begin = 0;
this->end = 0;
#elif defined(ONUNIX)
this->begin.tv_sec = 0;
this->begin.tv_nsec = 0;
this->end.tv_sec = 0;
this->end.tv_nsec = 0;
#endif
}
void RCTimer::start(){
setCurrentTime(this->begin);
}
void RCTimer::stop(){
setCurrentTime(this->end);
}
double RCTimer::getElapsedSeconds(){
return ((double)this->getElapsedMilliseconds() / 1000.0);
}
double RCTimer::getElapsedMilliseconds(){
return ((double)this->getElapsedMicroseconds() / 1000.0);
}
double RCTimer::getElapsedMicroseconds(){
return ((double)this->getElapsedNanoseconds() / 1000.0);
}
BIGNUM RCTimer::getElapsedNanoseconds(){
BIGNUM elapsedNano;
#if defined(ONWINDOWS)
elapsedNano = (double)(end.QuadPart - begin.QuadPart) / (double)frequency.QuadPart * 1000000000;
#elif defined(ONMAC)
elapsedNano = (end - begin) * this->sTimebaseInfo.numer / this->sTimebaseInfo.denom;
#elif defined(ONUNIX)
elapsedNano = (end.tv_sec - begin.tv_sec) * 1000000000;
elapsedNano += (end.tv_nsec - begin.tv_nsec);
#endif
return elapsedNano;
}
#if defined(ONWINDOWS)
void RCTimer::setCurrentTime(LARGE_INTEGER& t){
QueryPerformanceCounter(&t);
}
#elif defined(ONMAC)
void RCTimer::setCurrentTime(uint64_t& t){
t = mach_absolute_time();
}
#elif defined(ONUNIX)
void RCTimer::setCurrentTime(timespec& t){
clock_gettime(CLOCK_MONOTONIC_RAW, &t);
}
#endif
#endif // _RCTIMER_H_
//END OF TIMING CODE
//***************************************
class Buckets{
public:
Buckets(int bucketCapacity, int numBuckets);
~Buckets();
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(Buckets& smallBucket);
void printAllBuckets();
private:
unsigned long **buckets;
int *itemCounter;
int bucketSize;
int numBuckets;
};
//***GLOBAL VARIABLES***
unsigned long *list;
int listSize;
int numBuckets;
int numThreads;
Buckets *globalBuckets;
unsigned long ULONGMAX = 4294967295;
mutex myMutex;
//*** Provide methods for the bucket class ***
Buckets::Buckets(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;
}
}
Buckets::~Buckets() {
for (int i = 0; i < numBuckets; i++) {
delete[] buckets[i];
}
delete[] buckets;
delete[] itemCounter;
}
void Buckets::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 Buckets::getNumBuckets() {
return numBuckets;
}
int Buckets::getNumItemsInABucket(int bucket) {
//You pass in the bucket #, it returns how many items that bucket contains.
return itemCounter[bucket];
}
void Buckets::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 * Buckets::getBucketArray(int bucket) {
//You pass in the bucket #, it returns the array that contains the bucket's data.
return buckets[bucket];
}
void Buckets::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 Buckets::copyOneBucketsIntoAnotherBuckets(Buckets& smallBucket) {
//Copies all items in all buckets from one Buckets object into another Buckets object.
for (int i = 0; i < numBuckets; i++) {
unsigned long * smallBucketArray = smallBucket.getBucketArray(i);
//printf("Copying %d items between bucket %d ", getNumItemsInABucket(i), i);
for (int j = 0; j < smallBucket.getNumItemsInABucket(i); j++) {
//printf("Copying %8X at index %d from small into big between bucket %d ", smallBucketArray[i], j, i);
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;
}
}
// Global Variables
/*unsigned long *list;
int listSize;
int numBuckets;
int numThreads;*/
// public variables / functions
//Buckets(int bucketCapacity, int numBuckets);
//~Buckets();
//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(Buckets& smallBucket);
//void printAllBuckets();
// private bucket variables
//unsigned long **buckets;
//int *itemCounter;
//int bucketSize;
//int numBuckets;
void placeIntoBuckets(int threadID) { // MultiThreaded
//TODO: Put the values into the appropriate buckets.
Buckets *threadBuckets = new Buckets(listSize, numBuckets);
int startingIndex = listSize / numThreads * threadID;
int endingIndex = listSize / numThreads * (threadID + 1);
for (int i = startingIndex; i < endingIndex; i++){
threadBuckets->addItem((list[i] / (ULONGMAX / numBuckets)), list[i]);
}
myMutex.lock();
globalBuckets->copyOneBucketsIntoAnotherBuckets(*threadBuckets);
delete threadBuckets;
myMutex.unlock();
}
void sortEachBucket(int threadID) {
//TODO: Sort each individual bucket
//for (int i = threadID; i < numBuckets; i += numThreads){ // un-equal threads to buckets
// recQuickSort(globalBuckets->getBucketArray(i), 0, globalBuckets->getNumItemsInABucket(i) + 1);
//}
recQuickSort(globalBuckets->getBucketArray(threadID), 0, globalBuckets->getNumItemsInABucket(threadID));//equal threads to buckets
}
void combineBuckets(int threadID) {
//TODO: Copy each bucket back out to the original list[] array
unsigned int listIndex = 0;
//for (int i = threadID; i < numBuckets; i += numThreads){ // un-equal threads to buckets
// listIndex = 0;
// for (int j = 0; j < i; j++){
// listIndex += globalBuckets->getNumItemsInABucket(j);
// }
// myMutex.lock();
// globalBuckets->copyBucketToAnotherArray(i, list, listIndex);
// myMutex.unlock();
//}
for (int i = 0; i < threadID; i++){ // equal threads to buckets
listIndex += globalBuckets->getNumItemsInABucket(i);
}
myMutex.lock();
globalBuckets->copyBucketToAnotherArray(threadID, list, listIndex);
myMutex.unlock();
}
void bucketSort() {
//creating an array of threads
thread *threads = new thread[numThreads];
//-----------------------------------------placeIntoBuckets
for (int i = 0; i < numThreads; i++) {
threads[i] = thread(placeIntoBuckets, i);
}
//create a barrier
for (int i = 0; i < numThreads; i++) {
threads[i].join();
}
//placeIntoBuckets();
//------------------------------------------sort buckets
for (int i = 0; i < numThreads; i++) {
threads[i] = thread(sortEachBucket, i);
}
//create a barrier
for (int i = 0; i < numThreads; i++) {
threads[i].join();
}
//---------------------------------------combinedBuckets
for (int i = 0; i < numThreads; i++) {
threads[i] = thread(combineBuckets, i);
}
//create a barrier
for (int i = 0; i < numThreads; i++) {
threads[i].join();
}
}
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); // removed minus 1
recQuickSort(arr, pivotLocation + 1, last);
}
}
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
}
void verifySort() {
for (int i = 1; i < listSize; i++) {
if (list[i - 1] > list[i]) {
printf("***Error***, the list was not sorted at index %d ", i);
return;
}
}
printf(" ***Success***, the list was sorted ");
}
int main() {
//Set the listSize, numBuckets, and numThreads global variables.
listSize = 100;
RCTimer timer;
numBuckets = 2;
numThreads = 2;
createList();
globalBuckets = new Buckets(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();
printf("Displaying each bucket's contents: ");
globalBuckets->printAllBuckets();
pressAnyKeyToContinue();
printf("Displaying what is hopefully a sorted array: ");
printList(); //See if it's all sorted.
verifySort();
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 Buckets(listSize, numBuckets);
printf("Displaying the unsorted list array: ");
printList(); //useful for debugging small amounts of numbers.
pressAnyKeyToContinue();
bucketSort();
printf("Displaying each bucket's contents: ");
globalBuckets->printAllBuckets();
pressAnyKeyToContinue();
printf("Displaying what is hopefully a sorted array: ");
printList(); //See if it's all sorted.
verifySort();
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 Buckets(listSize, numBuckets);
printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d, this is effectively a quick sort ", listSize, numBuckets, numThreads);
timer.clear();
timer.start();
bucketSort();
timer.stop();
printf("Finished quick sort simulation in %1.3lf milliseconds ", timer.getElapsedMilliseconds());
verifySort();
delete globalBuckets;
delete[] list;
listSize = 4000000;
numBuckets = 2;
numThreads = 2;
createList();
globalBuckets = new Buckets(listSize, numBuckets);
printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads);
timer.clear();
timer.start();
bucketSort();
timer.stop();
printf("Finished bucket sort in %1.3lf milliseconds ", timer.getElapsedMilliseconds());
verifySort();
delete globalBuckets;
delete[] list;
numBuckets = 4;
numThreads = 4;
createList();
globalBuckets = new Buckets(listSize, numBuckets);
printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads);
timer.clear();
timer.start();
bucketSort();
timer.stop();
printf("Finished bucket sort in %1.3lf milliseconds ", timer.getElapsedMilliseconds());
verifySort();
delete globalBuckets;
delete[] list;
numBuckets = 8;
numThreads = 8;
createList();
globalBuckets = new Buckets(listSize, numBuckets);
printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads);
timer.clear();
timer.start();
bucketSort();
timer.stop();
printf("Finished bucket sort in %1.3lf milliseconds ", timer.getElapsedMilliseconds());
verifySort();
delete globalBuckets;
delete[] list;
numBuckets = 16;
numThreads = 16;
createList();
globalBuckets = new Buckets(listSize, numBuckets);
printf("Starting bucket sort for listSize = %d, numBuckets = %d, numThreads = %d ", listSize, numBuckets, numThreads);
timer.clear();
timer.start();
bucketSort();
timer.stop();
printf("Finished bucket sort in %1.3lf milliseconds ", timer.getElapsedMilliseconds());
verifySort();
delete globalBuckets;
delete[] list;
pressAnyKeyToContinue();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.