Question

Please use the code I provided!! Use either bubble sort or selection sort!! Thank you in advance

This lab involves adding a sorting function to an existing C++ template.

In this module, a file is provided for you -- SortableBag.h -- that implements a simple "bag" (unsorted collection of numbers) structure with array storage.

Part 1

Add a sort() method to this template, which should not return any values or take any arguments ('void' for both the return type and arguments). When it is called, the bag should be sorted in ascending order, with no other changes. You can use any algorithm from the Chapter 11 readings, your choice (selection, bubble, insertion, merge, quick or radix sort).

Part 2

To test the new method, write some test driver code (with a new .cpp file) that does the following:

1) Generates a list of 100 random integers. Use srand(time(0)) to seed the random number generator. The integers should be within some range, such as 1 to 100, or any other reasonable value.

2) Inserts the integers into the bag.

3) Requests a sort of the bag with your new method as implemented above.

4) Verifies the bag is sorted, by first converting it to a vector using the provided toVector() method, then verifying that v[i] <= v[i+ 1] for all elements of the vector v.

5) Outputs the result of the test (pass or fail).

You can use either a recursive or iterative version of the sort function. Your new .cpp file should #include the provided SortableBag.h with your additions for new method.

Example Output

Your output does not need to be exactly like this, but should contain all the same information.

Requesting sort...
The bag contains 100 items:

4 41 8 32 74 1 14 61 35 13 72 92 11 58 28 65 57 83 15 22
14 77 70 16 11 30 37 17 19 54 64 23 48 24 7 22 78 74 84 13
39 8 57 50 66 86 67 75 21 82 97 35 11 20 3 23 2 40 40 21
46 56 96 46 33 56 69 11 30 5 24 69 13 33 71 32 71 90 7 92
25 57 79 36 77 34 59 79 26 51 52 25 8 48 71 93 56 92 4 86

Here's the new bag...
The bag contains 100 items:

1 2 3 4 4 5 7 7 8 8 8 11 11 11 11 13 13 13 14 14
15 16 17 19 20 21 21 22 22 23 23 24 24 25 25 26 28 30 30 32
32 33 33 34 35 35 36 37 39 40 40 41 46 46 48 48 50 51 52 54
56 56 56 57 57 57 58 59 61 64 65 66 67 69 69 70 71 71 71 72
74 74 75 77 77 78 79 79 82 83 84 86 86 90 92 92 92 93 96 97

What to Submit

Submit two files:

1) The modified SortableBag.h, with your sort method added (from Part 1).

2) The .cpp file of your test driver (from Part 2).

/*
* This header file implements a simple (template) 'bag' of items with a fixed
* capacity.
*/

#ifndef SORTABLE_BAG_
#define SORTABLE_BAG_

template<class ItemType>
class SortableBag {
private:
static const int DEFAULT_CAPACITY = 100;// Default bag size
ItemType items[DEFAULT_CAPACITY]; // Array of bag items
int itemCount; // Current count of bag items
int maxItems; // Max capacity of the bag

// Returns either the index of the element in the array items that
// contains the given target or -1, if the array does not contain
// the target.
int getIndexOf(const ItemType& target) const;   

public:
SortableBag();
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
std::vector<ItemType> toVector() const;
};

// Default constructor implementation
template<class ItemType>
SortableBag<ItemType>::SortableBag(): itemCount(0), maxItems(DEFAULT_CAPACITY) {
// the default constructor initializes itemCount and maxItems above
}

// Return the number of items currently in the bag
template<class ItemType>
int SortableBag<ItemType>::getCurrentSize() const {
return itemCount;
}

// Return whether the bag is currently empty
template<class ItemType>
bool SortableBag<ItemType>::isEmpty() const {
return itemCount == 0;
}

// Adds a new item to the bag, returning whether there was space (false
// if the add failed)
template<class ItemType>
bool SortableBag<ItemType>::add(const ItemType& newEntry)
{
bool hasRoomToAdd = (itemCount < maxItems);
if (hasRoomToAdd) {
items[itemCount] = newEntry;
itemCount++;
}
  
return hasRoomToAdd;
}

// Removes an item, returning whether the item was successfully removed.
template<class ItemType>
bool SortableBag<ItemType>::remove(const ItemType& anEntry) {
int locatedIndex = getIndexOf(anEntry);
bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
if (canRemoveItem) {
itemCount--;
items[locatedIndex] = items[itemCount];
}
  
return canRemoveItem;
}

// Resets the number of items held in the bag. The data values are NOT
// cleared.
template<class ItemType>
void SortableBag<ItemType>::clear() {
itemCount = 0;
}

// Returns whether or not the bag holds a value.
template<class ItemType>
bool SortableBag<ItemType>::contains(const ItemType& anEntry) const {
return getIndexOf(anEntry) > -1;
}

// Returns a std::vector resulting from the conversion of the bag storage.
template<class ItemType>
std::vector<ItemType> SortableBag<ItemType>::toVector() const {
std::vector<ItemType> bagContents;
   for (int i = 0; i < itemCount; i++)
       bagContents.push_back(items[i]);
  
return bagContents;
}

// This is a private method for obtaining the index of an entry, or -1
// if it does not exist in the bag.
template<class ItemType>
int SortableBag<ItemType>::getIndexOf(const ItemType& target) const {
bool found = false;
int result = -1;
int searchIndex = 0;

// If the bag is empty, itemCount is zero, so loop is skipped
while (!found && (searchIndex < itemCount)) {
if (items[searchIndex] == target) {
found = true;
result = searchIndex;
} else {
searchIndex++;
}
}

return result;
}
#endif

Answer 1

Please find below the files:

1. SortableBag.h

#ifndef SORTABLE_BAG_
#define SORTABLE_BAG_

template < class ItemType >
  class SortableBag {
    private:
        static const int DEFAULT_CAPACITY = 100; // Default bag size
        ItemType items[DEFAULT_CAPACITY]; // Array of bag items
        int itemCount; // Current count of bag items
        int maxItems; // Max capacity of the bag
        // Returns either the index of the element in the array items that
        // contains the given target or -1, if the array does not contain
        // the target.
        int getIndexOf(const ItemType & target) const;

    public:
        SortableBag();
        int getCurrentSize() const;
        bool isEmpty() const;
        bool add(const ItemType & newEntry);
        bool remove(const ItemType & anEntry);
        void clear();
        void sort();
        bool contains(const ItemType & anEntry) const;
        std::vector < ItemType > toVector() const;
  };

// Default constructor implementation
template < class ItemType >
  SortableBag < ItemType > ::SortableBag(): itemCount(0), maxItems(DEFAULT_CAPACITY) {
    // the default constructor initializes itemCount and maxItems above
  }

// Return the number of items currently in the bag
template < class ItemType >
  int SortableBag < ItemType > ::getCurrentSize() const {
    return itemCount;
  }

// Return whether the bag is currently empty
template < class ItemType >
  bool SortableBag < ItemType > ::isEmpty() const {
    return itemCount == 0;
  }

// Adds a new item to the bag, returning whether there was space (false
// if the add failed)
template < class ItemType >
  bool SortableBag < ItemType > ::add(const ItemType & newEntry) {
    bool hasRoomToAdd = (itemCount < maxItems);
    if (hasRoomToAdd) {
      items[itemCount] = newEntry;
      itemCount++;
    }

    return hasRoomToAdd;
  }

// Removes an item, returning whether the item was successfully removed.
template < class ItemType >
  bool SortableBag < ItemType > ::remove(const ItemType & anEntry) {
    int locatedIndex = getIndexOf(anEntry);
    bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
    if (canRemoveItem) {
      itemCount--;
      items[locatedIndex] = items[itemCount];
    }

    return canRemoveItem;
  }

// Resets the number of items held in the bag. The data values are NOT
// cleared.
template < class ItemType >
  void SortableBag < ItemType > ::clear() {
    itemCount = 0;
  }

// Returns whether or not the bag holds a value.
template < class ItemType >
  bool SortableBag < ItemType > ::contains(const ItemType & anEntry) const {
    return getIndexOf(anEntry) > -1;
  }

// Returns a std::vector resulting from the conversion of the bag storage.
template < class ItemType >
    std::vector<ItemType> SortableBag < ItemType > ::toVector() const {
    std::vector < ItemType > bagContents;
    for (int i = 0; i < itemCount; i++)
      bagContents.push_back(items[i]);

    return bagContents;
  }

// This is a private method for obtaining the index of an entry, or -1
// if it does not exist in the bag.
template < class ItemType >
  int SortableBag < ItemType > ::getIndexOf(const ItemType & target) const {
    bool found = false;
    int result = -1;
    int searchIndex = 0;

    // If the bag is empty, itemCount is zero, so loop is skipped
    while (!found && (searchIndex < itemCount)) {
      if (items[searchIndex] == target) {
        found = true;
        result = searchIndex;
      } else {
        searchIndex++;
      }
    }

    return result;
  }
  
//public method to sort the current bag
template < class ItemType >
  void SortableBag < ItemType > ::sort() {
    std::vector<ItemType> bagContents = toVector();
    ItemType temp;
    int size = bagContents.size();
    
    //bubble sort
    for(int i=0;i<size-1 ;i++) {
        for(int j=0;j<size-i-1;j++) {
            if(bagContents[j]>bagContents[j+1]) {
                temp = bagContents[j];
                bagContents[j] = bagContents[j+1];
                bagContents[j+1] = temp;
            }
        }
    }

    //clear current bag
    clear();
    //add sorted elements to bag
    for(int i=0; i<size ;i++) {
        add(bagContents[i]);
    }
  }
#endif

2. Test.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;


//initialize bag -> sort -> convert to vector -> check if vector is sorted
string testSort() {
    SortableBag<int> sortableBag;
    int a=0;
    srand(time(0));
    
    cout<<"Requesting sort..."<<endl<<"The bag contains 100 items:"<<endl;
    
    //initialize bag contents
    for(int i=0; i<100; i++) {
        a=rand()%100 + 1; // generating random number between 0-99 and adding 1 to it
        sortableBag.add(a);
        cout<<a<<" "; //print initial elements
    }
    
    //sort
    sortableBag.sort();
    
    //converting to vector
    vector<int> sortableVector = sortableBag.toVector();
    cout<<"Here's the new bag"<<endl<<"The bag contains 100 items:"<<endl;
    
    //print elements and check if vector is sorted
    for(int i=0; i<100; i++) {
        cout<<sortableVector[i]<<" "; //print final elements
        if(i!=99 && sortableVector[i]>sortableVector[i+1]){ //if condition is true for any element, the vector is not sorted
            return "fail";
        }
    }
    
    return "pass";
}

int main(){
    string testResult = testSort();
    cout<<endl<<"Test result for the sorting: "<<testResult;
}

• Comments have been added wherever found necessary. Please increase/remove as required.
• Same output format is followed as described in your question.
• Bubble sort is used for sorting.

Thanks