quicksort program problem

ace55 (33)
the problem with my code is that trace toggle can only be turn on, not off and trace does not demarcate the (substring) in progress. how do i fix 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
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
 
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void displayOptions()
{
	cout << "n - New list" << endl;
	cout << "s - Quick Sort" << endl;
	cout << "t - TraceMode " << endl;
	cout << "d - Delimiter Char " << endl;
	cout << "q - Quit " << endl;
}

vector<char> getTokens(const string& line,char delm)
{
	int pos = 0;
	vector<char> tokens;
	while ( (pos = line.find_first_not_of(delm,pos)) != string::npos)
	{
		tokens.push_back(line[pos]);
		pos++;
	}
	return tokens;
}

void quickSort(vector<char>& data, int  left, int right, int trace)
{
	        int l_hold, r_hold;
                l_hold = left;
                r_hold = right;
                char pivot = data[left];
                while(left < right)
                {
                        while( ( data[right] > pivot) && (left < right))
                        {
                                right--;
                        }
                        if(left != right)
                        {
                                data[left] = data[right];
                                left++;
                        }
                        while((data[left] < pivot) && (left < right))
                        {
                                left++;
                        }
                        if(left != right)
                        {
                                data[right] = data[left];
                                right--;
                        }
                }

                data[left] = pivot;
                int pivotPos = left;
                left = l_hold;
                right = r_hold;
		if(trace)
		{
			for(vector<char>::iterator ite = data.begin() ; ite != data.end() ; ite++)
			{
				cout << *ite << " " ;
			}
			cout << "\n" ;
		}
                if(left < pivotPos)
                        quickSort(data, left, pivotPos-1,trace);
                if(right > pivotPos)
                        quickSort(data, pivotPos+1, right,trace);
}
int main()
{

	char delm = ' ';
	bool traceMode = false;
	string data;

	while(1)
	{
		displayOptions();
		cout << "Enter the option:";
		string line;
		getline(cin,line);
		char c = line[0];
		switch(c)
		{
			case 's':
				{
					vector<char> tokens = getTokens(data,delm);
					quickSort(tokens, 0, (tokens.size() -1) , traceMode);
					cout << "sorted list :" ;
					for(vector<char> ::iterator ite = tokens.begin() ; ite != tokens.end() ; ite++)
                        		{
		                                cout << *ite << " " ;
                		        }
		                        cout << "\n" ;
					break;
				}


			case 'n':
				{
					cout << "Enter the new list:";
					getline(cin,line);
					data = line;
					break;
				}
			case 'd':
				{
					cout << "Enter the delimiter:";
					getline(cin,line);
					delm = line[0];
					cout <<"delimiter="  << delm << endl;
					break;
				}
			case 't':
				{
					traceMode = true;
					cout << "trace mode is on" << endl;
					break;
				}
			case 'q':
				{
					cout << "Quiting the program \n" << endl;
					return 0;
				}
		}
	}
}
Last edited on
whitenite1 (1785)
@ace55

I added in the ability to turn tracemode off or on.
Program works very nicely. I liked seeing the differences if tracemode is on and off.

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
 
void displayOptions(bool m)
{
	string mode[2] = {"off","on"};
	cout << "n - New list" << endl;
	cout << "s - Quick Sort" << endl;
	cout << "t - TraceMode " << mode[m] << endl; // Shows if on or off
	cout << "d - Delimiter Char " << endl;
	cout << "q - Quit " << endl;
}


int main()
{

	char delm = ' ';
	bool traceMode = false;
	string data;
	string mode[2] = {"off","on"}; // Added to show if tracemode is off or on
	while(1)
	{
		displayOptions(traceMode); // To allow menu to show condition of tracemode
		cout << "Enter the option:";
		string line;
		getline(cin,line);
		char c = line[0];
		switch(c)
		{
			case 's':
				{
					vector<char> tokens = getTokens(data,delm);
					quickSort(tokens, 0, (tokens.size() -1) , traceMode);
					cout << "sorted list :" ;
					for(vector<char> ::iterator ite = tokens.begin() ; ite != tokens.end() ; ite++)
                        		{
		                                cout << *ite << " " ;
                		        }
		                        cout << "\n" ;
					break;
				}


			case 'n':
				{
					cout << "Enter the new list:";
					getline(cin,line);
					data = line;
					break;
				}
			case 'd':
				{
					cout << "Enter the delimiter:";
					getline(cin,line);
					delm = line[0];
					cout <<"delimiter="  << delm << endl;
					break;
				}
			case 't':
				{
					traceMode = !traceMode; // Turns off and on, tracemode, 
					//  depending on its value at the time
					cout << "trace mode is " << mode[traceMode] << endl; // Prints out tracemode condition
					break;
				}
			case 'q':
				{
					cout << "Quitting the program \n" << endl; // Quitting has two t's
					return 0;
				}
		}
	}
}
ace55 (33)
ah thank you for fixing that. however when i test the program by inputting a new list and then quicksorting it, the result has commas preceding it. how do i get rid of them?
whitenite1 (1785)
@ace55

I'm not quite sure if you mean that, even if you typed a comma in the new list, that you don't want it in the list later, or they are there, regardless if you typed it in the sentence for the list.
The comma have an ascii value of 44, a hyphen, 45 and a period, a 46. Capital A is a 65, up to a Z of 90. Lower case a, is 97, etc. So when you do a sort, that would be the order they are placed.
ace55 (33)
what i mean is when i test it this way: Enter the new list:2,4,3,s,d,f n - New list s - Quick Sort t - TraceMode d - Delimiter Char q - Quit Enter the option:s , , , , , 2 s 3 d 4 f , , , , , 2 s 3 d 4 f , , , , , 2 s 3 d 4 f , , , , , 2 s 3 d 4 f , , , , , 2 s 3 d 4 f , , , , , 2 s 3 d 4 f , , , , , 2 f 3 d 4 s , , , , , 2 4 3 d f s , , , , , 2 3 4 d f s , , , , , 2 3 4 d f s , , , , , 2 3 4 d f s sorted list :, , , , , 2 3 4 d f s


i need to get rid of the commas preceding the sorted list so it would just be
2 3 4 d f s instead of all those commas before the sorted list
whitenite1 (1785)
In your 
1
2
3
4
5
 
case 's':
for(vector<char> ::iterator ite = tokens.begin() ; ite != tokens.end() ; ite++)
     {
	   cout << *ite << " " ;
       }

Add if (*ite >= '\x30')
before the cout << *ite << " " ;
so it will only start printing out if the character is a zero or greater.
Last edited on
ace55 (33)
ah okay but when i do trace mode for the quick sort there are still commas that precede the list being sorted so it looks like
, , , , , , 2 s 4 d 3 f n
, , , , , , etc
whitenite1 (1785)
@ace55

Place the same line of code I showed previously, into..
1
2
3
4
 
for(vector<char>::iterator ite = data.begin() ; ite != data.end() ; ite++)
{
	cout << *ite << " " ;
}

so it looks the same as case 's':

1
2
3
4
5
 
for(vector<char>::iterator ite = data.begin() ; ite != data.end() ; ite++)
{
   if (*ite >= '\x30')	
      cout << *ite << " " ;
}
Last edited on
ace55 (33)
okay got it! thank you!
Topic archived. No new replies allowed.