How do I implement bubblesort using a vector

Question

I'm having some serious trouble getting this program to work. I know my question isn't exactly specific but I don't know where else to go. This is what I have so far. Insert, size, erase, find, and empty all work fine. The overloaded output operator and the sort function are both broken. The program must be set up this way because that is what was assigned.

main testing program:

#include <iostream>
#include "UList.h"
#include "sortBS.h"
#include <vector>

using namespace std;

int main(){
    UList<size_t> list1(20), list2;

    cout<<list1.size()<<endl;
    cout<<list2.size()<<endl;
    list1.insert(3);
    list1.insert(5);
    list1.insert(4);
    list1.erase(4);
    cout<<list1.find(3)<<endl;
    cout<<list1.find(4)<<endl;
    cout<<list1.empty()<<endl;
    cout<<list2.empty()<<endl;
    sort(list1);
    cout<<list1<<endl;
    //sort
    //<<

}

UList.h

#ifndef UList__H
#define UList__H
#include <iostream>
#include <vector>
#include "sortBS.h"
template <class T>
class UList{
public:
    UList(size_t=10);
    void insert(const T&);
    bool erase(const T&);
    bool find(const T&);
    size_t size() const;
    bool empty() const;
    friend void sort (UList<T>&);
    friend std::ostream& operator << (std::ostream&, const UList<T>&);

protected:
    std::vector<T> items;
};

template <class T>
UList<T>::UList(size_t size){
    items.resize(size);
}

template <class T>
void UList<T>::insert(const T& element){
    items.insert(items.begin(), element);
}

template <class T>
bool UList<T>::erase(const T& element){
    for(size_t index=0; index<items.size(); index++){
        if(element==items.at(index))
            items.erase(items.begin()+index);
            return true;
    }
    return false;
}

template <class T>
bool UList<T>::find(const T& element){
    bool found=false;
    size_t index=0;
    while(index<items.size()){
        if(items.at(index)==element)
            found=true;
        index++;
    }
    return found;
}

template <class T>
size_t UList<T>::size() const{
    return items.size();
}

template <class T>
bool UList<T>::empty() const{
    return items.empty();
}

template<class T>
std::ostream& operator << (std::ostream& out, const UList<T>& List){
    if(List.items.empty())
        out<<"list is empty."<<std::endl;
    else{
        for(size_t index=0;index<List.items.size();index++){
            out<<List.items.at(index);
            if(index<List.items.size()-1)
                out<<" ";
        }
    }
    return out;
}

template<class T>
void sort(UList<T>& List){
    sortBS(List);
}

#endif

sortBS.h

#ifndef sortBS__H
#define sortBS__H
#include <iostream>
#include <vector>
#include "UList.h"

template <class T>
void sortBS(UList<T> List){
    for(size_t iteration=1;iteration<items.size();iteration++){
        for(size_t index=0;index<items.size()-iteration;index++){
            if(items.at(index)>items.at(index+1)){
                T temp = items.at(index);
                items.at(index) = items.at(index+1);
                items.at(index+1) = temp;
            }
        }
    }    
}

#endif // sortBS__H

errors

  ||=== Build: Debug in Program04 (compiler: GNU GCC Compiler) ===|
  G:\Program04\sortBS.h|8|error: variable or field 'sortBS' declared void|
  G:\Program04\sortBS.h|8|error: 'UList' was not declared in this scope|
  G:\Program04\sortBS.h|8|error: expected primary-expression before '>' token|
  G:\Program04\sortBS.h|8|error: 'List' was not declared in this scope|
  G:\Program04\UList.h|15|warning: friend declaration 'void sort(UList<T>&)' declares a                 non-template function [-Wnon-template-friend]|
  G:\Program04\UList.h|15|note: (if this is not what you intended, make sure the    function     template has already been declared and add <> after the function name here) |
  G:\Program04\UList.h|16|warning: friend declaration 'std::ostream&    operator<<(std::ostream&, const UList<T>&)' declares a non-template function [-Wnon-    template-friend]|
 ||=== Build failed: 4 error(s), 2 warning(s) (0 minute(s), 0 second(s)) ===|

here is the specs for creating the program( this teacher is very vague and not helpful in the slightest so i cant ask him for help(ive tried multiple times))

For this assignment you will create a stand-alone function, sort, that takes an UList parameter and sorts it using the Bubble Sort algorithm. This sort function is to placed in a file named sortBS.h and UList should be in a file named UList.h. The UML diagram for UList is given below:

UList<T>
#items: vector<T>
+UList(size_t=10)
+insert(const T&): void
+erase(const T&): bool
+find(const T&) const: bool
+size() const: size_t
+empty() const: bool
+friend operator << (ostream&, const UList<T>&): ostream&
+friend sort (UList<T>&): void
Submit sortBS.h and UList.h prior to the due date/time using the following form (I will        be using my own driver file for grading purposes):

Your variable name is "List" at the start of sortBS, but inside it you refer to "items". Rename one of those two to match each other. — BonzaiThePenguin, Apr 21 '14 at 07:03
You have a circular dependency between your header files. Fix it and a lot of your problems will go away. — Mankarse, Apr 21 '14 at 07:11
how should i go about explaining to my instructor that its not the best idea to use size and set it to 10 by default instead of using a capacity? — user3555573, Apr 21 '14 at 10:44

score 0 · Answer 1 · answered Apr 21 '14 at 07:13

0

Here are the problems I can find:

Don't include sortBS.h from within UList.h. UList does not require sortBS to exist (it'd work fine without it), so it shouldn't be included as such. Plus since that file is being included before you define what UList actually is, you get errors saying sortBS doesn't know what UList is.
sortBS declares a variable named List then doesn't use it, and tries using a variable named "items" which does not exist. Rename one of those to match the other one.
The last part of sortBS can be simplified to this:

if (items[index] > items[index+1]) std::swap(items[index], items[index+1]);

answered Apr 21 '14 at 07:13

BonzaiThePenguin

1,413
13
19

Also, the sort function does not need to be a `friend`, since it uses only the public interface of `UList`. (And as it is, this is causing problems, because the friend declaration has not been correctly written (see [this](http://stackoverflow.com/questions/19753609/how-to-use-friend-operators-in-a-template-class?lq=1))). – Mankarse Apr 21 '14 at 07:15
@Mankarse `+friend sort (UList&): void` - The UML from the instructor says it is to be friended, likely because it is *supposed* to hit up the private member vector directly when performing the actual sort. – WhozCraig Apr 21 '14 at 07:22
I took out the inclusion of sortBS.h from UList.h and it did fix a few problems, thank you! – user3555573 Apr 21 '14 at 10:41

BlackMamba · Answer 2 · 2014-04-21T07:53:15.793

First there is no need for sortBS(), because you just declare sort() as the friend of class UList.

In you class UList, please use these codes:

template< typename C >
friend void sort (UList<C>&);
template< typename C>
friend std::ostream& operator << (std::ostream&, const UList<C>&);

But in the function of sort, there is bug: you can't access items directly, please do vector<T> items(List.items);

template< typename T>
void sort(UList<T>& List){
    vector<T> items(List.items);
    for(size_t iteration=1;iteration<items.size();iteration++){
        for(size_t index=0;index<items.size()-iteration;index++){
            if(items.at(index)>items.at(index+1)){
                T temp = items.at(index);
                items.at(index) = items.at(index+1);
                items.at(index+1) = temp;
            }
        }
    } 
}

if you just want use friend void sort (UList<T>&);, you should put the define code of function sort inside class UList, just like this:

template <class T>
class UList{
public:
    UList(size_t=10);
    void insert(const T&);
    bool erase(const T&);
    bool find(const T&);
    size_t size() const;
    bool empty() const;
    friend void sort (UList<T>& List)
    {
        vector<T> items(List.items);
        for(size_t iteration=1;iteration<items.size();iteration++){
            for(size_t index=0;index<items.size()-iteration;index++){
                if(items.at(index)>items.at(index+1)){
                    T temp = items.at(index);
                    items.at(index) = items.at(index+1);
                    items.at(index+1) = temp;
                }
            }
        } 
    }
    template< typename C>
    friend std::ostream& operator << (std::ostream&, const UList<C>&);

protected:
    std::vector<T> items;
};

thanks for your time and help man i do greatly appreciate it but i have to keep the sortBS function seperate from my UList.h header file because thats the way my instructor wants it, i was thinking the same thing but i have no choice unfortunatly. — user3555573, Apr 21 '14 at 10:23
It should be noted that if the `vector items(List.items)` won't work either if you don't have access to `List.items` in the first place. And even if you did, all this does is sort a local copy of said-container. the actual `List.items` would remain unsorted. — WhozCraig, Apr 21 '14 at 19:43

How do I implement bubblesort using a vector

2 Answers2