C++

Forum

 
RE-Creating Quick Sort algorithm for class

d1g1talarts (55)
I need to create a quick sort method for my class and i am having trouble finding an example with a single input parameter. The input for my method will have to be a vector filled with doubles and it will return a vector filled with doubles. I also have to implement bubble sort, insertion sort, and selection sort. I think that i am having the same problem in all my methods and if you could help get this one working i may be able to figure out the others. Here is what i have. 
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
 
vector<double> QuickSort(vector<double>& vec1){
        double i = 0;
	double j = vec1.size()-1;
	int size = vec1.size();
		double tmp;

		double pivot = vec1[(i+j) / 2];



		/* partition */

		while (i <= j) {
		while (vec1[i] < pivot)
				i++;
			while (vec1[j] > pivot)
				j--;
		if (i <= j) {
				tmp = vec1[i];
				vec1[i] = vec1[j];
				vec1[j] = tmp;
				i++;
			j--;
		}

		}
		/* recursion */

		if (i < j) {

			QuickSort(vec1);
		}
		if (i <j) {

			QuickSort(vec1);
		}
		return vec1;
	
}
	
}
Quick update, bubblesort, selectionsort, and insertionsort are all implemented and working. Just have to fix my problems with quicksort and ill have completed the assignment. I still have no clue how to fix my code.
Last edited on
coder777 (8444)
In your code i and j cannot be used as index. This would be idexes:
1
2
 
	int i = 0;
	int j = vec1.size() - 1;
dhayden (5798)
Don't double space your code.

Line 8 isn't right i+j / 2 is interpretted as i+(j/2). You want (i+j)/2
jonnin (11438)
I fail to see how your recursion is working?

quicksort should be breaking the vector down into smaller vectors and sorting each of those, all the way down to size (2) or size(1) (depends on how you implement the base case, and you can even use a large size and have the base case use another sort on a small list). It looks like your recursion uses vec1 every time and never changes its size and you don't seem to retain any sort of indices.

it seems to me that if this is single threaded, some of your indices should be static or parameters. Somehow it needs to know where to start and stop for each recursive call, and .begin() and .end() won't do that, they just return the full vector's start/end and i and j are getting the values reset to the extremes of vec1 each iteration.

Unless I am missing something critical here?!

also tmp is an int being used to swap a vector of doubles?


Last edited on
d1g1talarts (55)
Ive taken the suggestions you have made and it is progress.
But the numbers are still being sorted improperly, any idea why?

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
 
 vector<double> QuickSort(vector<double>& vec1){


	double i = 0;
	double j = vec1.size() - 1;
	int size = vec1.size();
	double tmp;
	double pivot = vec1[(i + j )/ 2];
		/* partition */
		while (i <= j) {
			while (vec1[i] < pivot)
				i++;
			while (vec1[j] > pivot)
				j--;
			if (i <= j) {
				tmp = vec1[i];
				vec1[i] = vec1[j];
				vec1[j] = tmp;
				i++;
				j--;
			}
		}
		/* recursion */
		if (i < j) {
			QuickSort(vec1);
		}
		if (i <j) {
			QuickSort(vec1);
		}
		return vec1;
	
}

dhayden (5798)
Think about the recursive calls in quicksort. Each one sorts a subset of the vector. That means you have to pass the beginning and ending points:
1
2
3
4
5
6
7
8
9
10
11
 
static void QuickSortHelper(vector<double>& vec, size_t from, size_t to)
{
   // Your algorithm goes here.
}

vector<double> QuickSort(const vector<double> &vec)
{
    vector<double> result(vec);
    QuickSortHelper(result, 0, result.size());
    return result;
}


For debugging, consider adding some temporary code to QuickSortHelper() to print the "from" and "to" values.
d1g1talarts (55)
I tried your suggestion 
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
 
 static void QuickSortHelper(vector<double>& vec1, size_t from, size_t to)
{
	double i = from;
	double j = to;
	int size = vec1.size();
	double tmp;
	double pivot = vec1[(i + j) / 2];
	while (i <= j) {

		while (vec1[i] < pivot)

			i++;

		while (vec1[j] > pivot)

			j--;

		if (i <= j) {

			tmp = vec1[i];

			vec1[i] = vec1[j];

			vec1[j] = tmp;

			i++;

			j--;

		}

	};
}
//TODO: implement quicksort here
//return a sorted vector of doubles
vector<double> QuickSort(vector<double>& vec1){
/* recursion */
	vector<double> result(vec1);
	QuickSortHelper(result, 0, result.size()-1);
	return result;
	
}
and it returns
QuickSort:
-----------------------------

Enter size for numbers: 8
Enter seed for rand: 123
Constructed in 6.70694e-05 seconds
The sorted vector using QuickSort: -1.60122 , -2.26888 , -7.63348 , -6.06347 , 4.02684 , 1.07565 , 6.60101 , 7.95651 ,
calculated in 1.63647e-05 seconds

and i dont get why the numbers just are not in any sort of order.
d1g1talarts (55)
and seeing as splitting them into two ended in the same result as having the recursive call in the method, lets try to not split it and get this one working 

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
 
vector<double> QuickSort(vector<double>& vec1){

	double i = 0;
	double j = vec1.size()-1;
	int size = vec1.size();
		double tmp;

		double pivot = vec1[(i+j) / 2];



		/* partition */

		while (i <= j) {
		while (vec1[i] < pivot)
				i++;
			while (vec1[j] > pivot)
				j--;
			if (i <= j) {
//im pretty sure this is not doing what i want it to, but i am unsure of how to make it work
//most changes ive made have broken the program either by entering an infinite loop or 
//going beyond the bounds of the vector
				tmp = vec1[i];
				vec1[i] = vec1[j];
				vec1[j] = tmp;
				i++;
				j--;
			}
		};
		/* recursion */
		if (i < j) {
			QuickSort(vec1);
		}
		if (i <j) {
			QuickSort(vec1);
		}
		return vec1;
	
}
Last edited on
dhayden (5798)
QuickSortHelper looks like a good start, but you don't have the recursive calls. Between lines 32 and 33 you need to make some recursive calls. Also, you need to return in the base case (where you're sorting 0 or 1 items).
d1g1talarts (55)
wont compile now.
a number generator generates all input for my problem so input errors are not my biggest concern. 
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
 
static void QuickSortHelper(vector<double>& vec1, size_t from, size_t to)
{
	double i = from;
	double j = to;
	int size = vec1.size();
	double tmp;	double pivot = vec1[(i + j) / 2];
	//if (size == 1 || size == 0) {
	//	return vec1;
	//}
	while (i <= j) {
		while (vec1[i] < pivot)
			i++;
		while (vec1[j] > pivot)
			j--;
		if (i <= j) {
			tmp = vec1[i];
			vec1[i] = vec1[j];
			vec1[j] = tmp;
			i++;
			j--;
		}
	};
	if (vec1[0] < vec1[1]) {
		QuickSort(vec1);
	}
  }
//TODO: implement quicksort here
//return a sorted vector of doubles
vector<double> QuickSort(vector<double>& vec1) {
	/* recursion */
	vector<double> result(vec1);
	if (sizeof(vec1)<1) {
		return vec1;
	}
	else {
		QuickSortHelper(result, 0, result.size() - 1);
	}
	return result;

}
Last edited on
lastchance (6980)
@d1g1talarts, you are not attempting to follow @dhayden's suggestions.

Working from your last code above, the key errors are:
(1) You have no "base case" to stop a recursion. Put
if ( to <= from ) return;
as the first line of QuickSortHelper()

(2) You should be recursively sorting the two sides of the partition. Replace
1
2
3
 
	if (vec1[0] < vec1[1]) {
		QuickSort(vec1);
	}

by
1
2
 
        QuickSortHelper( vec1, from, j );
        QuickSortHelper( vec1, j+1, to );


(3) Wrong types:
1
2
 
	double i = from;
	double j = to;

should be
1
2
 
        size_t i = from;
        size_t j = to;


(4) Slightly wrong loop logic. Replace BOTH (i<=j) in lines 10 and 15 by ( i < j )

(5) LIne 32 can be amended to use <= rather than <
if (vec1.size()<=1) {

(6) Remove the unnecessary comment lines and any mention of size (line 5) in QuickSortHelper.


(7) FROM THE POINT OF VIEW OF GETTING ANSWERS ON THE FORUM, PLEASE PROVIDE A COMPILEABLE CODE, SO THAT WE CAN TEST YOUR CODE IN C++ SHELL WITHOUT HAVING TO WRITE OUR OWN DRIVERS.

You do not need the whole of your other code - just a simple main() program to throw some numbers in to test. Here is what I used to test your routines:
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
 
#include <iostream>
#include <vector>
using namespace std;

// ..... Your routines (after amendment) here

void write( const vector<double> &V )
{
   for ( double e : V ) cout << e << "  ";
   cout << '\n';
}

//======================================================================

int main()
{
   vector<double> A = { 1, 2, 3, 4, 5 };
   vector<double> B = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
   vector<double> C = { 1, 5, 6, 4, 9, 2, -3, 7 };
   vector<double> D = { 5, 5, 5, 5, 5, 5, 5 };

   A = QuickSort( A );   write( A );
   B = QuickSort( B );   write( B );
   C = QuickSort( C );   write( C );
   D = QuickSort( D );   write( D );
}


You will get more answers if you make it possible for people to test your code directly.
Last edited on
d1g1talarts (55)
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
 
#include<vector>
#include<algorithm>
#include<iostream>
vector<double> getNums(size_t listSize, double minNum, double maxNum)
{
	vector<double> theList;
	for (size_t i = 0; i < listSize; ++i)
	{
		theList.push_back(randReal(minNum, maxNum));
	}
	return theList;
}
void swap(double* a, double* b)
{
	double t = *a;
	*a = *b;
	*b = t;
}


double partition(vector<double> vec1, double low, double high)
{
	double pivot = vec1[high];    // pivot
	double i = (low);  // Index of smaller element
	//vector<double>Watcher = vec1;
	for (double j = low; j <= high - 1; j++)
	{
		// If current element is smaller than or
		// equal to pivot
		if (vec1[j] <= pivot||pivot>=vec1[j])
		{
			i++;    // increment index of smaller element
			swap(&vec1[i], &vec1[j]);
			vector<double>Watcher = vec1;
		}
	}
	swap(&vec1[i + 1], &vec1[high]);
	return (i+1);
}


void quickSort(vector<double> vec1, double low, double high)
{
	
	if (low < high)
	{

		double pi = partition(vec1, low, high);

		// Separately sort elements before
		// partition and after partition
		quickSort(vec1, low, pi-1);
		quickSort(vec1, pi+1 , high);
	}
}
int main(){
cout <<endl<< "QuickSort: " << endl

		<< "-----------------------------" << endl << endl;

	while (true)

	{

		cout << "Enter size for numbers: ";

		int n = 0;

		cin >> n;

		if (n <= 0)

			break;

		cout << "Enter seed for rand: ";

		unsigned int seed;

		cin >> seed;

		srand(seed);



		// Construct a sorted list of numbers

		//Timer get;

		//get.start();

		vector<double> numbers = getNums(n, -n, n);

		//get.stop();

		cout << "Constructed in " << get() << " seconds"

			<< endl;

		//Timer time;
		double in1=numbers.size()-1;
		//double in2 = 0;
		//time.start();

		 quickSort(numbers,0,in1);

		//time.stop();
		//int size = Quick.size();
		cout << "The sorted vector using QuickSort: ";
		for (int i = 0; i < in1+1; i++) {
			cout << numbers[i] << " , ";
		}
		cout << endl << "calculated in " << time() << " seconds"<< endl << endl;
	}

This is what im using now. ive tried your suggestions i really have and i am really just trying to get this to work properly at this point. its the last piece i need for the assignment and i just cannot figure out why the numbers won't sort.
i have a timer written that is working so we can ignore that. i just need the sorting to actually sort. My values always come out ,out of order
Last edited on
d1g1talarts (55)
This is what did it guys 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
template<class FwdIt, class Compare = std::less<>>
    void QuickSortImpl(FwdIt first, FwdIt last, Compare cmp = Compare{})
    {
        auto const N = std::distance(first, last);
        if (N <= 1) return;
        auto const pivot = *std::next(first, N / 2);
        auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
            return cmp(elem, pivot); 
        });
        auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
            return !cmp(pivot, elem);
        });
        QuickSortImpl(first, middle1, cmp);
        QuickSortImpl(middle2, last, cmp);
    }   


void QuickSort(vector<double>& vec1)
{
    QuickSortImpl(vec1.begin(), vec1.end());
}

https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c/24650627#24650627

https://stackoverflow.com/questions/49550327/quicksort-method-using-only-a-single-vector-as-input-parameter-in-c

if anyone else runs into a similar problem
dhayden (5798)
It looks like you copy and pasted the answer from stackoverflow. Be careful, you'll probably be caught for plagiarizing someone else's work. Most schools take that sort of thing very seriously.

Also, it's important to realize that programming is like football: to get good at it, you have to practice. You wouldn't send someone else to practice and then expect to be able to play well in a game. If you're planning to do this for a living, you'll need to know how to do this stuff yourself.
jonnin (11438)
if you just want to sort something, use the built in sort.
if you want to learn something, try to write it yourself until you figure it out.
There isnt a lot of middle ground there for whatever your purpose is in using others' code.

lastchance (6980)
@digitalarts - what a waste. Your OWN code in an earlier post wasn't a million miles away, and all you had to do was follow carefully-numbered instructions on how to fix it. Could you really not have done that? (I note from the following post that you didn't even try. Most of the problems in that later post are due to the fact that you used void functions but not reference arguments, so nothing would return changed to the calling routine.)

I'm sure that the stackoverflow code is a good use of the standard library, but it manifestly isn't YOUR code, nor do I find it particularly educational. Could you teach the QuickSort method from it? I doubt it. If you are going to use std::partition rather than write your own then you might as well have called std::qsort in the first place.

I don't want to waste the effort I spent looking on your original code, so here's what you would have got. Obviously it could be improved, it's nothing like as slick as the stackoverflow version, I tried to change yours as little as possible, and if there are bad errors then somebody please tell me. Note, in particular, the two things that @dhayden and @jonnin drew to your attention right at the beginning and that are marked KEY here:
- you need to deal with the base case to end the recursion (one line);
- you need to recursively sort the two sides of the pivot (two lines).

Note that the routines are set to return a sorted vector as the return value of the function - because that's what you had in your code - rather than the (admittedly more obvious) void function changing a reference argument as done in the stackoverflow code.

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
 
#include <iostream>
#include <vector>
using namespace std;

// ===== YOUR CODE - WITH INSTRUCTED AMENDMENTS - FROM AN EARLIER POST

static void QuickSortHelper(vector<double>& vec1, size_t from, size_t to)
{
        if ( to <= from ) return;                            // <===== KEY: BASE CASE TO END RECURSION

        size_t i = from;                                     // <===== get the type correct
        size_t j = to;                                       // <===== get the type correct
                                                             // <===== remove size
        double tmp;     double pivot = vec1[(i + j) / 2];

        while (i < j) {                                      // <===== less than, not <=
                while (vec1[i] < pivot)
                        i++;
                while (vec1[j] > pivot)
                        j--;
                if (i < j) {
                        tmp = vec1[i];
                        vec1[i] = vec1[j];
                        vec1[j] = tmp;
                        i++;
                        j--;
                }
        };

        QuickSortHelper( vec1, from, j );                   // <===== KEY: REPLACE WITH RECURSIVE SORT
        QuickSortHelper( vec1, j+1, to );                   //        OF ADJACENT PARTITIONS
}


vector<double> QuickSort(vector<double>& vec1) {
        vector<double> result(vec1);
        if (vec1.size()<=1) {                               // <===== minor amendment
                return vec1;
        }
        else {
                QuickSortHelper(result, 0, result.size() - 1);
        }
        return result;

}



// ===== END OF YOUR CODE (AMENDED) ===============================================


// === Added for testing ...

void write( const vector<double> &V )
{
   for ( double e : V ) cout << e << "  ";
   cout << '\n';
}

//======================================================================

int main()
{
   vector<double> A = { 1, 2, 3, 4, 5 };
   vector<double> B = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
   vector<double> C = { 1, 5, 6, 4, 9, 2, -3, 7 };
   vector<double> D = { 5, 5, 5, 5, 5, 5, 5 };

   A = QuickSort( A );   write( A );
   B = QuickSort( B );   write( B );
   C = QuickSort( C );   write( C );
   D = QuickSort( D );   write( D );
}

1  2  3  4  5  
1  2  3  4  5  6  7  8  9  10  
-3  1  2  4  5  6  7  9  
5  5  5  5  5  5  5

Last edited on
Topic archived. No new replies allowed.