vbs In this exercise, you will explore C++ classes and implement the bucket sort as discussed in class. Your program will consist of 2 modules (files): main.cpp and VectorBucketSort.h. Use the definitions that appear below and complete all of the TODOs. Your main should thoroughly test your code. Email your work to me and our wonderful TA with the required subject of DAA grad vbs. For extra credit, implement a more efficient version of the get function called get2. Clearly describe in the comment for get2 your approach and why and how it is better.

#pragma once

// file : VectorBucketSort.h // author: ... // desc. : this file contains the VectorBucketSort class definition.

#include #include #include #include #include

using namespace std;

//#define GRAD //un-comment this if you are a grad student //#define EXTRA_CREDIT //un-comment this if you are attempting extra credit

class VectorBucketSort { private: int mSize = 0; //# of buckets vector< double >* mBucketList = nullptr; //treat as an array bool mIsSorted = false; //true when sorted

public: //bucket sort ctor. default size is 10 buckets. VectorBucketSort ( int size = 10 ) { cout << "in VectorBucketSort() ctor" << endl; assert( size > 0 ); if (size < 1) return; mSize = size; //create the bucket list array of the appropriate size. mBucketList = new vector< double >[ size ]; if (mBucketList == nullptr) return; } //----------------------------------------------------------------------- //bucket sort dtor. ~VectorBucketSort ( void ) { cout << "in ~VectorBucketSort() dtor" << endl; //if there is no list, there's nothing to do. if (mBucketList == nullptr) return; //delete the bucket list itself delete[] mBucketList; mBucketList = nullptr; mSize = 0; } //----------------------------------------------------------------------- // \TODO this function should add a new element to the appropriate list // _in arbitrary order_. void add ( double value ) { mIsSorted = false; // \TODO // ... } //----------------------------------------------------------------------- //this function sorts all of the lists. void sortAll ( void ) { if (mBucketList == nullptr) return; for (int i = 0; i < mSize; i++) { sort( mBucketList[ i ].begin(), mBucketList[ i ].end() ); } mIsSorted = true; } //----------------------------------------------------------------------- // \TODO return the ith (starting at 0) value in the list. // if there is no such entry, then return NAN. // // NAN is Not-A-Number. one cannot do comparisons (or arithmetic) with // NAN so only use isnan. for example, assuming that 12 does not exist, // the first, third, and fifth will print for the following: // if (isnan( bs->get( 12 ) )) cout << "NAN1" << endl; // if (bs->get( 12 ) == NAN) cout << "NAN2" << endl; // if (NAN == NAN) cout << "NAN3" << endl; /* if (isnan( bs->get( 12 ) )) cout << "NAN1" << endl; if (bs->get( 12 ) == NAN) cout << "NAN2" << endl; if (bs->get( 12 ) != NAN) cout << "NAN3" << endl; if (NAN == NAN) cout << "NAN4" << endl; if (NAN != NAN) cout << "NAN5" << endl; */ // vc++ supports NAN, but not all compilers do. // see me if your compiler doesn't support NAN. double get ( int i ) { // \TODO // ... return NAN; } //----------------------------------------------------------------------- #if defined(GRAD) && defined(EXTRA_CREDIT) // \TODO double get2 ( int i ) { // \TODO // ... return NAN; } #endif //----------------------------------------------------------------------- #ifdef GRAD // \TODO this function returns the number of entries in a particular bucket // list (i.e., the chain length). int getCount ( int which ) { // \TODO // ... return 0; } #endif //----------------------------------------------------------------------- #ifdef GRAD // \TODO this function calculates and returns the load factor (LF). // the LF is the average chain length (# of data values added / total # // of bucket lists). double getLoadFactor ( void ) { // \TODO // ... return 0; } #endif //----------------------------------------------------------------------- //pretty print the contents of the bucket list to an output stream. friend ostream& operator<< ( ostream& os, const VectorBucketSort& bs ) { os << " mSize=" << bs.mSize; os << " mBucketList=0x" << hex << (unsigned long) (bs.mBucketList) << dec << endl;

for (int i = 0; i < bs.mSi