Vectors and bubblesort, what to do?

void bubbleSort(int *array,int length)
{
  for(int i = 0; i < length; i++)
    for(int j = i+1; j < length; j++)
      if(array[i] > array[j])
      {
	int temp = array[i]; //swap 
	array[i] = array[j];
	array[j] = temp;
      }  
}

Ok, you cleaned it up a bit, but what does that do? Sorry to ask, I'm just trying to understand how this thing works. What part of it decides what goes where, and in what order? Also, would I be putting this in my print function as I thought? Thanks for the help by the way.

I've tried putting this thing in all over the place and I still can't get it to work UG! The teacher says he doesn't care where it ends up being stuck as long as it works, but I don't get how to get it to print out the last names in alphabetical order. Can someone possibly walk me though how this thing is supposed to work in layman's terms? I''ve looked it up and read a bunch of stuff on it, but I'm still not getting how it works so I can figure out how to get it into my program correctly.

He also said I could put it in the header if I wanted to, but I have no idea how that would work.

Can anyone show me how to use the bubble sort?

I would suggest you look again at whatever source you're using that specifies the bubble sort algorithm, because that isn't it.

http://en.wikipedia.org/wiki/Bubble_sort

I would suggest you look again at whatever source you're using that specifies the bubble sort algorithm, because that isn't it.

http://en.wikipedia.org/wiki/Bubble_sort

It's what the teacher gave us to use. I saw the wikipedia link yesterday, I thought it looked different, but if the teacher says bubblesort, who am I to question...

So for this:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

How in the world can it know its supposed to swap around the last names?

this is what i'm trying in my addressbook.cpp, am I even close?

void addressBook::bubbleSort(int *lName,int length)//Bubble sort function 
{
    int i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<i;j++)
        {
            if(lName[i]>lName[j])
            {
                int temp=lName[i]; //swap 
                lName[i]=lName[j];
                lName[j]=temp;
            }

        }

    }

}

void addressBook::printBook(int *lName,int length) //print array elements
{
    int i=0;
    for(i=0;i< people.size();i++)
        cout << people[i].lName << "\t" << people[i].fName << "\t" << people[i].Address << endl;
}

You are close, but not quite, the key in bubble sort is to compare one element with the element after it and the word bubble sort comes from the way the smaller elements sort of "bubble" to the top as the sort goes on.

The difference between yours and mine is line 6 in yours and line 7 in mine.

void addressBook::bubbleSort(int *lName,int length)//Bubble sort function 
{
    int i,j;
    int g = people.size();
    for(i=0;i<g;i++)
    {
        for(j=i+1;j<g;j++)
        {
            if(lName[i]>lName[j])
            {
                int temp=lName[i]; //swap 
                lName[i]=lName[j];
                lName[j]=temp;
            }

        }

    }

}

Question, are you storing the people's last name as integers? Or is this just an example you are giving here?

Smac89 wrote:
The difference between yours and mine is line 6 in yours and line 7 in mine.

But neither one is a bubble sort.

xanthian23 wrote:
How in the world can it know its supposed to swap around the last names?

void addressBook::bubbleSort(int *lName,int length)//Bubble sort function

How does lName, a pointer to int, represent last names?

But neither one is a bubble sort.

From wikipedia:

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

From wikipedia:

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

I didnt even notice that, it's supposed to be a char from my PERSON struct, thats where the names are stored, i think, here's my header file with the struct:

#ifndef _ADDRESSBOOK
#define _ADDRESSBOOK
#include <vector>
using namespace std;

const int MAXADDRESS =25;

struct PERSON
{
 char fName[25];
 char lName[25];
 char Address[100];
};

class addressBook
{
private:
	vector <PERSON> people;

 int head;
 int tail;

public:

 addressBook();

 addressBook(const PERSON &p);

 addressBook(const PERSON p[], int size);

 addressBook(char *fName, char *lName, char *address);

 bool addPerson(const PERSON &p);
 bool getPerson(PERSON &p);
 bool findPerson(char *lastName, PERSON &p);
 bool findPerson(char *lastName, char *firstName, PERSON &p);
 void bubbleSort(char *lName,int length);

 void printBook(char *lName,int length);

};
#endif

On our last assingment I had to store some names through the struct, and then in an string array, and also a string, thats why I had the idea to use *lName.

After I posted my code I went back and caught the int and changed it to this:

void addressBook::bubbleSort(char *lName,int length)//Bubble sort function 
{
    int i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<i;j++)
        {
            if(lName[i]>lName[j])
            {
                int temp=lName[i]; //swap, I think... 
                lName[i]=lName[j];
                lName[j]=temp;
            }

        }

    }

}

void addressBook::printBook(char *lName,int length) //print elements
{
    int i=0;
    for(i=0;i< people.size();i++)
        cout << people[i].lName << "\t" << people[i].fName << "\t" << people[i].Address << endl;

I have no idea how to put it into main to test if it works. The teacher doesn't care about the main.cpp, so we can do whatever we want in there, he doesn't grade us on that, which is why I have the string array setup to store the name, but it doesn't print out, because I couldn't figure out how to do that one either. I have a hard time getting how this thing is printing stuff out in main, which sucks because it makes it really hard for me to test anything I do.

Anyways, so your saying I should do this:

void addressBook::bubbleSort(char *lName,int length)//Bubble sort function 
{
    int i,j;
    for(i=0;i<10;i++)
    {
        for(j=i+1;j<people.size();j++)
        {
            if(lName[i]>lName[j])
            {
                int temp=lName[i]; //swap, I think... 
                lName[i]=lName[j];
                lName[j]=temp;
            }

        }

    }

}

void addressBook::printBook(char *lName,int length) //print elements
{
    int i=0;
    for(i=0;i< people.size();i++)
        cout << people[i].lName << "\t" << people[i].fName << "\t" << people[i].Address << endl;
}

i'm assuming I have to use people.size(): since I'm using a vector now (latest assignment)

Anyways, so your saying I should do this:

Not really.

If I were doing it, it would look something like the following:

// comparison function for PERSONs -- makes the sort implementation cleaner.
bool operator>(const PERSON& p1, const PERSON& p2)
{
    int result = std::strcmp(p1.lName, p2.lName) ;

    if ( result > 0 )
        return true ;
    if ( result < 0 )
        return false ;

    // last names are equal, use first names to determine order
    return std::strcmp(p1.fName, p2.fName) > 0 ;
}

// changed the name to sort, because it shouldn't matter to the caller what algorithm
// we're using.  Got rid of the parameters, because we can extract them from the 
// data that already resides in the object the function was invoked for.
void addressBook::sort() 
{
    // unoptimized bubble sort
    bool didSwap ;

    do
    {
        didSwap = false ;

        for ( unsigned i=1; i<people.size(); ++i )
            if ( people[i-1] > people[i] )
            {
                std::swap(people[i-1], people[i]) ;
                didSwap = true ;
            }

    } while ( didSwap ) ;
}

void addressBook::sort() 
{
    // unoptimized bubble sort
    bool didSwap ;

    do
    {
        didSwap = false ;

        for ( unsigned i=1; i<people.size(); ++i )
            if ( people[i-1] > people[i] )
            {
                std::swap(people[i-1], people[i]) ;
                didSwap = true ;
            }

    } while ( didSwap ) ;
}

I see, nice idea using the boolean.

Last edited on

Ok, I see the comparison thing, which makes a lot more sense to do then anything I've heard so far, but what is operator? I know you can have overloaded operators, so is that just a reference to one of my other operators?