C++

Forum

 
Question about quicksort

Pages: 12
BananaCode (51)
Hello,

So my next algorithm is QuickSort which I'm trying to implement.
Here is the 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
 
#include <iostream>
#include <time.h>

using namespace std;

void quicksort (int* a, int left, int right);

int main()	
{
	int size,l=0,r;
	int* a;
	srand((unsigned int)time(0));
	cin >> size;
	r = size-1;
	a = new int [size];
	for (int i=0;i<size;i++)
	{
		cin >> a[i];
	}
	quicksort (a,l,r);
	quicksort (a,l,r);
	for (int x=0;x<size;x++)
	{
		cout << a[x] << " ";
	}
	delete [] a;
	system("pause");
	return 0;
	
}


void quicksort (int* a, int l, int r)
{
	int temp, left=l, right=r;
	if (r-l<1)
	{
		return;
	}
	int pivot =  rand() % right+1;
	pivot = a[pivot];
	while (left<right && !(a[left] == a[right]))
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	quicksort(a,l,left-1);
	quicksort(a,left+1,r);

}

Newest problem: It doesn't sort it completely out. Aren't I recursively calling quicksort enough times?

Regards,
Last edited on
BananaCode (51)
Problem still persists.
coder777 (8444)
quicksort isn't about splitting the array 'physically'. So your approch doesn't help.

You need an index within your array and swap fields when they're less/greater (depends on whether you're left or right).
BananaCode (51)
Well...that explains a lot. Thanks mate.
BananaCode (51)
Updated the original post with the code, need some help with it.
BananaCode (51)
Help...please?
ne555 (10692)
BananaCode (51)
I don't see what you are trying to show, unless it's the changing of the pivot element to the last place, for which I get an error similar to the previous one.
BananaCode (51)
This Algorithm is really slowly starting to get on my nerves:

The error I'm getting:

Zugriffsverletzung beim Lesen an Position 0xaf1cfafc.
Translation: "Access violation reading location 0xaf1cfafc."

The 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
 
#include <iostream>
#include <time.h>

using namespace std;

void quicksort (int* a, int left, int right);

int main()	
{
	int size,l=0,r;
	int* a;
	srand((unsigned int)time(0));
	cin >> size;
	r = size-1;
	a = new int [size];
	for (int i=0;i<size;i++)
	{
		cin >> a[i];
	}
	quicksort (a,l,r);
	for (int x=0;x<size;x++)
	{
		cout << a[x] << " ";
	}
	delete [] a;
	system("pause");
	return 0;
	
}


void quicksort (int* a, int l, int r)
{
	int temp, left=l, right=r;
	if (r<=1)
	{
		return;
	}
	int pivot =  rand() % right+1;
	pivot = a[pivot];
	temp = a[r];
	a[r] = a[pivot];
	a[pivot] = temp;
	for (;;)
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		if (left>=right || a[left]==a[right])
		{
			break;
		}
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	quicksort(a,l,left-1);
	quicksort(a,left+1,r);

}


What the hell am I doing wrong? Can someone point it out to me? No links, no other algorithm, just a simple answer to what I'm doing wrong, please!

Thank you.
Last edited on
ne555 (10692)
Considerer an input array like: 42 54 13 
1
2
3
4
5
 
	int pivot =  rand() % right+1;
	pivot = a[pivot]; //<---
	temp = a[r];
	a[r] = a[pivot]; //<----
	a[pivot] = temp; //<---


Also the conditions in the loop are wrong.
Last edited on
BananaCode (51)
Updated the code 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
26
 
void quicksort (int* a, int l, int r)
{
	int temp, left=l, right=r;
	if (r-l<=1)
	{
		return;
	}
	int pivot =  rand() % right+1;
	pivot = a[pivot];
	while (left<right)
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	quicksort(a,l,left-1);
	quicksort(a,left+1,r);

}

It almost works, can anyone spot the mistake?

Following array gives out a wrong answer for example: {1 8 11 6 7 2 10 9 3 5 4}
Following leads to an infinite loop: {1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 3}
Following is correct: {6 3 2 5 4 8}
Last edited on
BananaCode (51)
Updated the code, I'm almost there!
hackthisred (15)
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
 

#include <iostream>
using namespace std;


double array[5];
double temp;
double high;
double low;
double running_sum;
void print_array();


int main (int argc, char * const argv[]) {
cout << "Please enter in five values you wish to store in the array\n";



for (int i = 0; i < 5; i++) {
cin >> array[i];
}



/* first solution finds the low to high sort of the array */
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
/* swap instruction if one number is less then the */
/* one it is next to swap them */
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}//end if
}//end for
}//end for
low = array[0];
cout << "Your array sorted 'low' to 'high' is : ";
print_array();// function call



/* second solution finds the high to low sort of the array */
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
/* swap instruction if one number is more then the */
/* one it is next to swap them */
if (array[i] < array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}//end if
}//end for
}//end for
high = array[0];
cout << "Your array sorted 'high' to 'low' is : ";
print_array();// function call



/* find the difference of the  high and low value */
cout << "The difference of the 'highest' value "<< high<<" and the 'lowest' value "<<low<<" is : ";
cout << high -  low << endl;



/* find the average of the array */
    for (int i = 0; i < 5; i++) {
running_sum += array[i];
}
cout << "The average of the values of the array is : " << running_sum/5.0 << endl;



    return 0;
}


/* a void function, it returns nothing, simply used to output the array to the screen */
void print_array(){



for (int i = 0; i < 5; i++) {
cout <<array[i]<<" ";
}
cout << endl;
}


This is a simple bubble sort see if this helps you...
you can deffinately mod this to work for your problem... without me giving you the answer directly.
closed account (D80DSL3A)
One idea for troubleshooting your code.
Does your function partition the array as intended? Remove the recursive calls (lines 23 and 24) to see what the function does in the 1st iteration only.
This may help you to see what is wrong.
Restore the recursion when the function is performing as expected.

@hackthisred: He's not trying to write a bubble sort. He's trying for quick sort.
Last edited on
BananaCode (51)
fun2code, I did that before implementing the recursion, it function as expected. There is some mistake with the recursion which I'm trying to figure out since the beginning of this thread. Can you help me?
BananaCode (51)
An additional observation I made is that when I call quicksort twice in the main function, it sorts the array correctly, for bigger array it needs to be called even more.

Am I recursively calling it in the quicksort function one to little?
ne555 (10692)
Try this sequence {1,2,3,3,2,1}
1
2
3
4
5
6
7
8
9
10
11
 
	while (left<right)
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--) //¿what if you find the pivot?
		{
		}
		swap(a[left], a[right]); //¿what if left > right here?
	}
closed account (D80DSL3A)
Sorry, I can't figure out how to correct your code either.
Some flaws which seem evident:
1) int pivot = rand() % right+1; pivot must be between left and right not 1 and right
2) A working version modifies the value of pivot then calls:
1
2
 
quickSort(A,left,newPivot-1);
quickSort(A,newPivot+1,right);

3) Your code appears to get stuck in the while loop on the 2nd iteration.
I added this code after line 22 (just outside of the while loop):
 
 
cout << "pivot=" << pivot << " l=" << l << " r=" << r << " left=" << left << " right=" << right  << endl;

When tested on arr[] = 3 7 8 5 2 1 9 5 4 it gives as output:

3 7 8 5 2 1 9 5 4
pivot=8 l=0 r=8 left=7 right=7
3 7 4 5 2 1 5 8 9

Does that seem right?
This output appears only once, which is why I think it is stuck in the while loop.
It appears to be the 1st call to quicksort() on line 23 causing the problem. Commenting out line 23 only will stop the infinite loop problem. ie: line 24 doesn't cause it.

Are you sure you don't want to see code for a working in-place quick sort? I found Wikipedias pseudocode easy to adapt from. Perhaps you could compare logic.
BananaCode (51)
ne555, I don't seem to figure out what you are trying to say.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
while (left<right && !(a[left] == a[right]))
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}


During swapping, it is desired for a[left] > a[right]. Unless you mean the pointer values, in which case the entire loops cancels.
And if you find the pivot...it get's switched? I thought that's the point of quicksort, so it leads to the proper position of the pivot element.


fun2code, what is the command to get a random element between two numbers?
How come you change the "left" to "newPivot" ? I don't seem to understand.

I have a working code of the algorithm, here: http://xoax.net/comp/sci/algorithms/Lesson4.php (scroll further down)

It's very similar to my code, yet symbols they use to recursively call the quicksort function seems odd to me, in other words I don't understand what it means, let alone why it's in that form. Maybe you can help me?
Last edited on
ne555 (10692)
And if you find the pivot...it get's switched? I thought that's the point of quicksort, so it leads to the proper position of the pivot element.

The array should end [ Lesser | Pivot | Greater ] (it could be relaxed to [ <= | Pivot | >= ] )
Suppose this sequence 1 5 2 3 4, pivot is 3.
It will end 1 3 2 5 4. Note that there is an smaller value to the right of the pivot, that is incorrect.

A way to handle it is to send the pivot "outside" the array, and when you finish the partition put it in the right position
1 5 2 3 4 -> 1 5 2 4 (3) (the array now it's just 1 5 2 4)
1 5 2 4 (3)
1 2 5 4 (3)
And now swap it to the right position 1 2 (3) 4 5

Unless you mean the pointer values, in which case the entire loops cancels.
Yes, I mean the positions. Nope, it cancels one step too late
Suppose this sequence ... 1 3 42 54 ... (left points to 1, right points to 54, pivot is 13)*
left advances till it tops with 42.
right advances till it tops with 3.
Now the partition should end, however:
You swap the values -> ... 1 42 3 54 ... Then you break


*As you can see the pivot is not in the extract of the sequence. That could happen because you swapped before, or you send "outside" the array
Last edited on
Pages: 12