For this assignment, we want to implement a straightforward bucket sort. The ass
ID: 3682142 • 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
C++ Code for bucket sort using arrays:
#include <iostream>
#include <iomanip>
using namespace std;
#define NARRAY 8 /* array size */
#define NBUCKET 5 /* bucket size */
#define INTERVAL 10 /* bucket range */
struct Node
{
int data;
struct Node *next;
};
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);
void BucketSort(int arr[])
{
int i,j;
struct Node **buckets;
/* allocate memory for array of pointers to the buckets */
buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET);
/* initialize pointers to the buckets */
for(i = 0; i < NBUCKET;++i) {
buckets[i] = NULL;
}
/* put items into the buckets */
for(i = 0; i < NARRAY; ++i) {
struct Node *current;
int pos = getBucketIndex(arr[i]);
current = (struct Node *) malloc(sizeof(struct Node));
current->data = arr[i];
current->next = buckets[pos];
buckets[pos] = current;
}
/* check what's in each bucket */
for(i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}
/* sorting bucket using Insertion Sort */
for(i = 0; i < NBUCKET; ++i) {
buckets[i] = InsertionSort(buckets[i]);
}
/* check what's in each bucket */
cout << "-------------" << endl;
cout << "Bucktets after sorted" << endl;
for(i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}
/* put items back to original array */
for(j =0, i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while(node) {
arr[j++] = node->data;
node = node->next;
}
}
/* free memory */
for(i = 0; i < NBUCKET;++i) {
struct Node *node;
node = buckets[i];
while(node) {
struct Node *tmp;
tmp = node;
node = node->next;
free(tmp);
}
}
free(buckets);
return;
}
/* Insertion Sort */
struct Node *InsertionSort(struct Node *list)
{
struct Node *k,*nodeList;
/* need at least two items to sort */
if(list == 0 || list->next == 0) {
return list;
}
nodeList = list;
k = list->next;
nodeList->next = 0; /* 1st node is new list */
while(k != 0) {
struct Node *ptr;
/* check if insert before first */
if(nodeList->data > k->data) {
struct Node *tmp;
tmp = k;
k = k->next;
tmp->next = nodeList;
nodeList = tmp;
continue;
}
for(ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
if(ptr->next->data > k->data) break;
}
if(ptr->next!=0){
struct Node *tmp;
tmp = k;
k = k->next;
tmp->next = ptr->next;
ptr->next = tmp;
continue;
}
else{
ptr->next = k;
k = k->next;
ptr->next->next = 0;
continue;
}
}
return nodeList;
}
int getBucketIndex(int value)
{
return value/INTERVAL;
}
void print(int ar[])
{
int i;
for(i = 0; i < NARRAY; ++i) {
cout << setw(3) << ar[i];
}
cout << endl;
}
void printBuckets(struct Node *list)
{
struct Node *cur = list;
while(cur) {
cout << setw(3) << cur->data;
cur = cur->next;
}
}
int main(void)
{
int array[NARRAY] = {29,25,3,49,9,37,21,43};
cout << "Initial array" << endl;
print(array);
cout << "-------------" << endl;
BucketSort(array);
cout << "-------------" << endl;
cout << "Sorted array" << endl;
print(array);
return 0;
}
Output:
Initial array
29 25 3 49 9 37 21 43
-------------
Bucket[0] : 9 3
Bucket[1] :
Bucket[2] : 21 25 29
Bucket[3] : 37
Bucket[4] : 43 49
-------------
Bucktets after sorted
Bucket[0] : 3 9
Bucket[1] :
Bucket[2] : 21 25 29
Bucket[3] : 37
Bucket[4] : 43 49
-------------
Sorted array
3 9 21 25 29 37 43 49
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.