Quicksort function to work with my class array

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 Quicksort(int info[],int left,int right){
int pivot = left + (right - left)/2;//it is the middle (will change sometimes but will end up in the middle
int temp;

while(left<=right){
	while(info[left] < pivot){
	left++;
	}
	while(info[right] < pivot){
	right--;
	}
	//swap feature
	if(left<=right){
	temp =	info[left];
	info[left]=info[right];
	info[right] = temp;

	left ++;
	right --;
	}


}

}



this is my quicksort function


I have tried a lot of things but I am trying to get it to work to sort all the details I have stored in an array by there age.

This is how I have entered the data.

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
void DataEntry(Details info[],int size){
int x;
int i;
i=0;
		
cout << "How Many Entries Would You Like to add";
cin >> x;
for(int j=0;j<x;j++){
	if ( info[i].Age == 0){
		cout << "First Name: ";
		getline(cin, info[i].FirstName);
		cin.ignore(256,'\n'); 
		cout << "Last Name: ";
		getline(cin,info[i].LastName);
		cout << "Age(Please Enter an Integer(Number)): ";
		cin >>  info[i].Age;
		cin.ignore(256,'\n'); 
		cout << "Email: ";
		getline(cin,  info[i].Email);
		cout << "Door Number(Please Enter an Integer(Number)): ";		
		cin >>  info[i].DoorNumber;	
		cin.ignore(256,'\n'); 
		cout << "Road Name: ";
		getline(cin,info[i].RoadName);
		cout << "Post Code(NOTE:Please use Lower Case): ";
		getline(cin,info[i].PostCode);				
		}		
	else{
		i++;
		j--;
			}
}	
}


I am stuck on what to do with it
bump
Please post all of the code and tell me the question you get, so i know how to help you.
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
	#include <iostream> 
	#include <string>
	#include <math.h> 
	#include <fstream>
	#include <sstream>
	using namespace std;

class Details
{
public:
    Details();
	string FirstName;
    string LastName;
    int Age ;
    string Email;
    int DoorNumber;
    string RoadName;
    string PostCode;
	void SearchByAge(int);
	
};

	 Details::Details() : Age(0), DoorNumber(0) {}
void DataEntry(Details info[],int size){
int x;
int i;
i=0;
		
cout << "How Many Entries Would You Like to add";
cin >> x;
for(int j=0;j<x;j++){
	if ( info[i].Age == 0){
		cout << "First Name: ";
		getline(cin, info[i].FirstName);
		cin.ignore(256,'\n'); 
		cout << "Last Name: ";
		getline(cin,info[i].LastName);
		cout << "Age(Please Enter an Integer(Number)): ";
		cin >>  info[i].Age;
		cin.ignore(256,'\n'); 
		cout << "Email: ";
		getline(cin,  info[i].Email);
		cout << "Door Number(Please Enter an Integer(Number)): ";		
		cin >>  info[i].DoorNumber;	
		cin.ignore(256,'\n'); 
		cout << "Road Name: ";
		getline(cin,info[i].RoadName);
		cout << "Post Code(NOTE:Please use Lower Case): ";
		getline(cin,info[i].PostCode);				
		}		
	else{
		i++;
		j--;
		cout << "FULL Moving on to Next Array";
	}
}	
}
void GetData(Details &member){
	cout << "\nFirst Name: "<< member.FirstName;
	cout << "\nLast Name: " << member.LastName;
	cout << "\nAge: " << member.Age;
	cout << "\nEmail: " << member.Email;
	cout << "\nDoor Number: " <<  member.DoorNumber;
	cout << "\nRoad Name: " << member.RoadName;
	cout << "\nPost Code: " <<  member.PostCode<<"\n";
}
void Age_Search(Details info[], int size){
    int AgeSearch = 0;
	cin >> AgeSearch;
	for(int i=0; i < size; i++){
		if( info[i].Age == AgeSearch ){
		cout << info[i].FirstName << " "  << info[i].LastName << " is" << info[i].Age << " years old.\nHere are his/her Details:";
		GetData(info[i]);
		}
	}
}




void LastName_Search(Details info[],int size){
	string LastNameSearch;
	cin >> LastNameSearch;
	for(int i=0; i < size; i++){
		if( info[i].LastName == LastNameSearch ){
		cout << "Here are Details of People who have the Surname "<< LastNameSearch<<":";
		GetData(info[i]);
		}
	}

}
void PostCode_Search(Details info[],int size){
	string PostCodeSearch;
	cin >> PostCodeSearch;
	for(int i=0; i < size; ++i){
		if( info[i].PostCode == PostCodeSearch ){
		cout << "Here are Details of People Who Live in the '"<< PostCodeSearch<<"' Postal Area:";
		GetData(info[i]);
		}
	}
}
void Email_Search(Details info[],int size){
	string EmailSearch;
	cin >> EmailSearch;
	for(int i=0; i < 10; ++i){
		if( info[i].Email == EmailSearch ){
		cout << "This Person Has the email address '"<< EmailSearch<<"':";
		GetData(info[i]);
		}
	}
}
// define operator >> for a Details object

   istream& operator>>( istream& is, Details& detail ){
    string line;
    string word;
    char delim = '\t';
    getline(is, line);

    istringstream iss(line);

    getline(iss, word, delim);
    detail.FirstName = word;

    getline(iss, word, delim);
    detail.LastName = word;

    getline(iss, word, delim);
    detail.Age = atoi(word.c_str());          // convert string to integer

    getline(iss, word, delim);
    detail.Email = word;

    getline(iss, word, delim);
    detail.DoorNumber = atoi(word.c_str());   // convert string to integer

    getline(iss, word, delim);
    detail.RoadName = word;

    getline(iss, word, delim);
    detail.PostCode = word;

    return is;
}
//      istream& operator<<( istream& is, Details& detail ){
//    string line;
//    string word;
//    char delim = '\t';
//    getline(is, line);
//
//    istringstream iss(line);
//
//    getline(iss, word, delim);
//    detail.FirstName = word;
//
//    getline(iss, word, delim);
//    detail.LastName = word;
//
//    getline(iss, word, delim);
//    detail.Age = atoi(word.c_str());          // convert string to integer
//
//    getline(iss, word, delim);
//    detail.Email = word;
//
//    getline(iss, word, delim);
//    detail.DoorNumber = atoi(word.c_str());   // convert string to integer
//
//    getline(iss, word, delim);
//    detail.RoadName = word;
//
//    getline(iss, word, delim);
//    detail.PostCode = word;
//
//    return is;
//}
void LoadData(Details info[], int size){
    ifstream File_in("test.txt");// attempt to open file for reading
    if( File_in.is_open() )
    {
        for(int i=0; i<size;i++)
            File_in >> info[i];
	        File_in.close();// details!
    }
    return;
}
//void SaveData(Details Data[], int size){
//	ofstream DataSave("test.txt");
//    if( DataSave.is_open() )
//    {
//        for(int i=0; i<size;i++){
//           DataSave << Data[i];
//		}
//	  DataSave.close();      // details!
//    }
//
//    return;
//}

void SaveData(Details info[],int size){
	ofstream DataSave("test.txt");
	
			for(int i=0;i<size;i++){
				DataSave <<  info[i].FirstName<<"\t";	
				DataSave <<  info[i].LastName<<"\t";
				DataSave <<  info[i].Age<<"\t";
				DataSave <<  info[i].Email<<"\t";
				DataSave <<  info[i].DoorNumber<<"\t";
				DataSave <<  info[i].RoadName<<"\t";
				DataSave <<  info[i].PostCode<<"\t";
				DataSave <<"\n";
			}
				DataSave.close();

}

void Quicksort(int info[],int left,int right){
int pivot = left + (right - left)/2;//it is the middle (will change sometimes but will end up in the middle
int temp;

while(left<=right){
	while(info[left] < pivot){
	left++;
	}
	while(info[right] < pivot){
	right--;
	}
	//swap feature
	if(left<=right){
	temp =	info[left];
	info[left]=info[right];
	info[right] = temp;

	left ++;
	right --;
	}


}

}


int main(){	
	
	int a=0;
	int b=0;
	int i = 0;
	string temp;
	Details	Data[100];
	LoadData(Data,10);
	
	
	do{	
		cout << "\n1) Input \n2) ViewByAge \n3) Search\n4) Delete\n5)Exit \n" ;
		cin >> a;
		switch(a){
			case 1:	
				//Input;
			DataEntry(Data,100);
			break;
			case 2: 
				//View;
				
				
			break;
			case 3: 
				//Search
				system("CLS");
				cout << "1) Input \n2) View";
				cout << "\n3Search\n   3.1)Search Using Age\n   3.2)Search Using Last Name\n   3.3)Search Using Post Code\n   3.4)Search Using Email";
				cout <<"\n4) Delete\nExit \n" ;
				cin >> b;
				switch(b){
				case 1:
					//Search With Age
					cout << "Enter the age of the person you are looking for: ";Age_Search(Data,10);break;
				case 2:
					//Search Using Last Name
					cout << "Enter the Last Name or Surname of the person you are looking for: ";LastName_Search(Data,10);break;
				case 3:
					//Search Using Post Code
					cout << "Enter the Post Code of the person/people you are searching for: ";PostCode_Search(Data,10);break;
				case 4:
					//Search Using Email Adress
					cout << "Enter the Email Address of the person you are searching for: ";Email_Search(Data,10);break;default:break;
				system("pause");					
				}//end of switch b(search)
			break;
			case 4: 
				//Delete
			break;
			case 5:
				//Exit
				
			break;default: break;       
		   }//end of switch a(main menu)
	}//end of do while loop if exit is chosen.
	while(a!=5);
	SaveData(Data,100);



return 0;}


I am trying to sort all the members info using quicksort by their age.
Last edited on
bump again :D
anyone?
Does your Quicksort function work for an integer array?
If so, then it can be adapted to work with Details objects (you're still working on this problem?)

I suspect your Quicksort function may be broken:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Quicksort(int info[],int left,int right){
int pivot = left + (right - left)/2;//it is the middle (will change sometimes but will end up in the middle
int temp;

while(left<=right){
	while(info[left] < pivot){
	left++;
	}
	while(info[right] < pivot){
	right--;
	}
	//swap feature
	if(left<=right){
	temp =	info[left];
	info[left]=info[right];
	info[right] = temp;

	left ++;
	right --;
	}
}
}

Lines 6 and 9 don't look right. An index value (pivot) is being compared to a stored value there.
Maybe while(info[left] < info[pivot]) is correct.
I don't want to troubleshoot the Quicksort function. Make sure it works on an integer array.
Here's how I would adapt it for use on Details objects where the sorting is based on age:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Quicksort(Details info[],int left,int right){
int pivot = left + (right - left)/2;//it is the middle (will change sometimes but will end up in the middle
Details temp;// working with Details, not ints

while(left<=right){
	while( info[left].age < info[pivot].age ){// if my "correction" is correct
	left++;
	}
	while( info[right].age < info[pivot].age ){// if my "correction" is correct
	right--;
	}
	//swap feature
	if(left<=right){
	temp =	info[left];
	info[left]=info[right];
	info[right] = temp;

	left ++;
	right --;
	}
}
}
yes Im still working on this I had to stop working on it as I had exams and such Im pretty much where you left it except i need to add some features to this.

such as a priority list etc



anyway will try your soloution


however is there anyway i could do this without adapting the function for the specific task? as i want to be able to use this same function for the door numbers and other integer informations
also is right 99? not 100 right ?
as left is 0;
1
2
3
4
5
1
1>  attemp2.cpp
1>c:\users\faieq\documents\visual studio 2010\projects\attempt 2 challange 1\attempt 2 challange 1\attemp2.cpp(223): error C2228: left of '.Age' must have class/struct/union
1>          type is 'int'
1>c:\users\faieq\documents\visual studio 2010\projects\attempt 2 challange 1\attempt 2 challange 1\attemp2.cpp(223): fatal error C1903: unable to recover from previous error(s); stopping compilation
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========



i have the following problem now
any ideas?
dump

however is there anyway i could do this without adapting the function for the specific task? as i want to be able to use this same function for the door numbers and other integer informations

Yes. There are several ways I can think of.
I will recommend a simple method, which others will probably disagree with.
Add a method to your details class which returns a bool result of comparing the desired members.
If you identify the members by number, then you could write something like:

1
2
3
4
5
6
7
8
9
10
bool less(const Details& D, int searchParam)
{
    switch( searchParam )
    {
        case 1: return FirstName < D.FirstName;// sorting by FirstName
        case 2: return LastName < D.LastName;// sorting by LastName
        case 3: return Age < D.Age;// sorting by Age
        // and so on
    }
}

Then he Quicksort function can work like this. A parameter has been added for giving which member to sort by
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Quicksort(Details info[],int left,int right, int searchParam){
int pivot = left + (right - left)/2;//it is the middle (will change sometimes but will end up in the middle
Details temp;// working with Details, not ints

while(left<=right){
	while( info[left].less(searchParam) < info[pivot].less(searchParam) ){// if my "correction" is correct
	left++;
	}
	while( info[right]..less(searchParam) < info[pivot].less(searchParam) ){// if my "correction" is correct
	right--;
	}
	//swap feature
	if(left<=right){
	temp =	info[left];
	info[left]=info[right];
	info[right] = temp;

	left ++;
	right --;
	}
}
}

The error means it doesn't know what a Details is. This error was encountered in previous threads, so please research how to fix it yourself.
Last edited on
I see you have problems with the Quicksort function, so I change my recommendation to overloading operator< for Details, then just call std::sort(). Forget writing the sort function.

Can you do that? Or, must you write your own sort function?

EDIT: Here's a simplified example I just made up to verify that I knew how to make it work right (and it does):
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
#include <iostream>
#include<algorithm>
#include <string>
using namespace std;

class A
{
    public:
    static int sortParam;// applies to all Details
    int age;
    string name;
    int zip;
    A(int Age, string Name, int Zip ): age(Age), name(Name), zip(Zip) {}
    bool operator<(const A& ra )const;
    void print(void) { cout << "age: " << age << " name: " << name << " zip: " << zip << endl; }
};

bool A::operator<(const A& ra )const
{
    switch( sortParam )
    {
        case 1: return ( age < ra.age );
        case 2: return ( name < ra.name );
        case 3: return ( zip < ra.zip );
    }
    return false;
}

int A::sortParam = 1;// sort by age

int main()
{
    A arr[] = { A( 25, "Job", 23471 ), A( 5, "Norm", 11654 ), A( 17, "Angel", 87638 ), A( 46, "Grant", 77153 ) };
    int i = 0;

    // unsorted
    for(i=0; i<4; ++i) arr[i].print();

    A::sortParam = 1;// sort by age
    sort(arr, arr+4);
    cout << endl;
    for(i=0; i<4; ++i) arr[i].print();

    A::sortParam = 2;// sort by name
    sort(arr, arr+4);
    cout << endl;
    for(i=0; i<4; ++i) arr[i].print();

    A::sortParam = 3;// sort by zip
    sort(arr, arr+4);
    cout << endl;
    for(i=0; i<4; ++i) arr[i].print();

    cout << endl;
    return 0;
}

Output:

age: 25 name: Job zip: 23471
age: 5 name: Norm zip: 11654
age: 17 name: Angel zip: 87638
age: 46 name: Grant zip: 77153

age: 5 name: Norm zip: 11654
age: 17 name: Angel zip: 87638
age: 25 name: Job zip: 23471
age: 46 name: Grant zip: 77153

age: 17 name: Angel zip: 87638
age: 46 name: Grant zip: 77153
age: 25 name: Job zip: 23471
age: 5 name: Norm zip: 11654

age: 5 name: Norm zip: 11654
age: 25 name: Job zip: 23471
age: 46 name: Grant zip: 77153
age: 17 name: Angel zip: 87638
Last edited on
I need to use my own sort . I can use a simpler sort but my quicksort is only not working because I haven't called It again.


Also how can I clear a string array I know I can clear the integers by setting them to -1

as currently its sorting all the empty slots.
Last edited on
Do you have any working sort function, perhaps from a previous homework?

I was not offering to help with quicksort because it's one of the few sort methods that I have heard of, but not yet worked out myself.
I am deferring this for when I get to more formal study of algorithms.

When it comes to subtle algorithms, and especially when recursion becomes involved, I'm simply not going to be able to see how it works by examining the code. I would have to research how to make that recursive call correctly myself.

I could help you with an iterative (not recursive) version of selection sort, if you don't already have any other working method.

Also how can I clear a string array I know I can clear the integers by setting them to -1

There is a clear() function for strings.
I recall from the previous thread that the user can enter Details and remove Details, so the array ends up with a mixture of "valid" and "invalid" Details in it. Is this right?
A clean approach may be to rely on one chosen data member (eg Age=-1) to tell if a Details is invalid. This way it doesn't even matter what the values of any of the other data members are.
To illustrate, suppose Age==-1 means an element is not to be displayed when the array is printed out. If I rewrite the print function like this:
1
2
3
4
5
void print(void) 
{
    if( age == -1 ) return;// print nothing
    cout << "age: " << age << " name: " << name << " zip: " << zip << endl; 
}

You could print the whole array and only the valid entries would appear.
Do you need to control where the "invalid" elements wind up in the sorted array? If you want them all to be at one end, this is easy. Modify the operator< I wrote so it always returns false if age==-1. This would result in all invalid elements at the end (I think).
1
2
3
4
5
6
7
8
9
10
11
12
13
void GetData(Details &member){
	
	cout << "\nFirst Name: "<< member.FirstName;
	cout << "\nLast Name: " << member.LastName;
	cout << "\nAge: " << member.Age;
	cout << "\nEmail: " << member.Email;
	cout << "\nDoor Number: " <<  member.DoorNumber;
	cout << "\nRoad Name: " << member.RoadName;
	cout << "\nPost Code: " <<  member.PostCode<<"\n";
	if (member.Age == -1){
		return ;}
	
}



it still prints the empty ones with -1 which is bad for my eyesight lol


Yeah. The return is at the wrong end of the function.
You want to return before printing everything out, not after.

Perhaps more sensibly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void GetData(Details &member){
	
    if( member.Age != -1 )
    {
	cout << "\nFirst Name: "<< member.FirstName;
	cout << "\nLast Name: " << member.LastName;
	cout << "\nAge: " << member.Age;
	cout << "\nEmail: " << member.Email;
	cout << "\nDoor Number: " <<  member.DoorNumber;
	cout << "\nRoad Name: " << member.RoadName;
	cout << "\nPost Code: " <<  member.PostCode<<"\n";
    }
    return ;	
}
Last edited on
thanks fixed a lot
Topic archived. No new replies allowed.