Vectors and bubblesort, what to do?

OK, so my latest assignment has me replacing an array with a vector, and adding in a sorter to print out addressbook names in some order. I think I've managed to work out the vector problem, mostly because I put in the code, and everything still runs as it should. So if anyone could look it over for me and let me know if I've goofed I'd really appreciate it since I'm new to vectors.

My big problem right now is figuring out how to use the bubblesort. This one has me confused. I'm relatively sure I need to fit it into my printout function, but I don't know how to do that, or what the format should look like. I have the basic coded that is needed for the function, provided from my teacher, and I have tried a few different things to get it to work, but so far no go. I'll post my code, and hopefully someone can point me in the right direction, or at least explain how the sorter is supposed to work. Oh, and the code I have seems to be based on working with an array, and I was wondering if it can or should be utilizing the vector I just integrated.

Here is my header file:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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(int *array,int length);
 void printBook();

};
#endif 


And here is my addressbook.cpp file:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include "addressBook.h"
using namespace std;

addressBook::addressBook()
: head(0), tail(-1)
{
 
}

addressBook::addressBook(const PERSON &p)
: head(0), tail(-1)
{
 addPerson(p);
}

addressBook::addressBook(const PERSON p[], int size)
: head(0), tail(-1)
{
 for(int i = 0; i < size; i++)
 addPerson(p[i]);

}

addressBook::addressBook(char *fName, char *lName, char *address)
: head(0), tail(-1)
{
 PERSON tmp;
 strcpy(tmp.fName, fName);
 strcpy(tmp.lName,lName);
 strcpy(tmp.Address, address);
 addPerson(tmp);
}

bool addressBook::addPerson(const PERSON &p)
{
 
 
 people.push_back(p);

 if(tail == -1)
 tail++;
 return true;
 
}
bool addressBook::getPerson(PERSON &p)
{
 if(tail >=0)
 {
 if(tail >= people.size())
 tail = 0;
 p = people[tail];
 tail++;
 return true;
 }
 return false;
}
bool addressBook::findPerson(char *lastName, PERSON &p)
{
 for(int i = 0; i < people.size(); i++)
 {
 if(!stricmp(people[i].lName, lastName))
 {
 p = people[i];
 return true;
 }
 }
 return false;
}
bool addressBook::findPerson(char *lastName, char *firstName, PERSON &p)
{
 for(int i = 0; i < people.size(); i++)
 {
 if(!stricmp(people[i].lName, lastName) && !stricmp(people[i].fName, firstName))
 {
 p = people[i];
 return true;
 }
 }
 return false;
}


void addressBook::printBook()
{
 for(int i = 0; i < people.size(); i++)
 {

 cout << people[i].fName << "\t" << people[i].lName << "\t" << people[i].Address << endl;
 }
}


And here is my main.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdlib>
#include <conio.h>
#include "addressBook.h"


using namespace std;
int printMenu();
void waitKey();

const int ADDPERSON = 1;
const int GETPERSON = 2;
const int FINDLAST = 3;
const int FINDBOTH = 4;
const int PRINT = 5;
const int EXIT = 0;
int main()
{
	PERSON p;
	addressBook ad;
	addressBook myBook;
	addressBook newBook;
	addressBook newerbook;

	PERSON me = {"Johnny", "Rocket", "123 go"};


	myBook.addPerson(me);


	addressBook newbook("TEST", "TEST2", "1234");

	
	
	
	
	

int selection;



bool status;
char lName[50];
char fName[50];
		

		selection = printMenu();
		while(selection != EXIT )
		{
		switch(selection)
			{
			case ADDPERSON :
				cout << "Enter First Name " << endl;
				cin >> p.fName;
				cout << "Enter last Name " << endl;
				cin >> p.lName;
				cout << "Enter Address " << endl;
				cin >> p.Address;
				status = ad.addPerson(p);
				if(status == false)
					cout << "Sorry There is no more room in the address book " << endl;
				else
					cout << "Thanks for your Entry " << endl;

				waitKey();	
				break;
			case GETPERSON :
				status = ad.getPerson(p);
				if(status)
					cout << p.fName << "\t" << p.lName << " " << p.Address << endl;
				else
					cout << "Sorry The address book is empty " << endl;

				waitKey();

				break;
			case FINDLAST :
				cout << "Enter a last name " << endl;
				cin >> lName;
				status = ad.findPerson(lName,p);
				if(status)
						cout << p.fName << "\t" << p.lName << " " << p.Address << endl;
				else
					cout << "Sorry, Name not found " << endl;

				waitKey();
				break;

			case FINDBOTH :
				cout << "Enter last name " << endl;
				cin >> lName;
				cout << "Enter first name " << endl;
				cin >> fName;
				status = ad.findPerson(lName, fName,p);
				if(status)
					cout << p.fName << "\t" << p.lName << " " << p.Address << endl;
				else
					cout << "Sorry, Name not found " << endl;

				waitKey();
				break;
				
			case PRINT :
				newerbook.printBook();
				newbook.printBook();
				ad.printBook();
				myBook.printBook();
				waitKey();
				break;
			case EXIT :
				cout << "Thanks for using the address book " << endl;
				exit(0);
		}
			selection = printMenu();
		}
};

int printMenu()
{
	

int selection;

	system("CLS");
	cout << "1. Add A Person" << endl;
	cout << "2. Get A Person " << endl;
	cout << "3. Find A person By Last Name " << endl;
	cout << "4. Find A person By First and Last Name " << endl;
	cout << "5. Print the address book" << endl;
	cout << "0. Exit this program " << endl;
	cin >> selection;

	return selection;

};

void waitKey()
{

	cout << "Press a key to continue " << endl;
	while(!kbhit())
		;

	getch();
	fflush(stdin);

};


And finally, here is the code I have to the bubbleSort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void bubbleSort(int *array,int length)
{
    int i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<i;j++)
        {
            if(array[i]>array[j])
            {
                int temp=array[i]; //swap 
                array[i]=array[j];
                array[j]=temp;
            }

        }

    }

}


Hopefully someone can help me with this, and thanks in advance.

Almost forgot, this is my assignment:

For this lab, add the following functionality to your address book.

Remove the array of PERSON structures and replace it with a vector
Add a sort function that will sort your addressBook by last name.
There are several different sorting algorithms that you can use. You might want to investigate using a bubble sort. Examples can be found online but if you have problems finding one let me know and I will supply one for you.
Last edited on
1
2
3
4
5
6
7
8
9
10
11
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 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 ) ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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?
bool operator>(const PERSON& p1, const PERSON& p2)

is operator> overloaded to work with objects of type PERSON.

If you aren't comfortable with the overloaded operator, you could make it a function:

1
2
3
4
5
6
7
8
9
10
11
12
bool greaterThan(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 ;
}


And the sort would then be:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void addressBook::sort() 
{
    // unoptimized bubble sort
    bool didSwap ;

    do
    {
        didSwap = false ;

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

    } while ( didSwap ) ;
}
Topic archived. No new replies allowed.