470,841 Members | 930 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,841 developers. It's quick & easy.

Quicksort: I don't understand what is going on!

Hi, I want to sort an array of pointers, each position of this array
point to a position in an integer array.
There is a strange behavior when the 'pivot' is '0'. I am using Visual
C++, and when executing a segment violation error occur . When there is
no zeros in the integer
array, or when the pivot is never zero, this doesn't happen.
The pivot is always the last element. Try to change the last element in

the array for a non zero value and you will see it works.
Tell me something please. Thanks.
Also feel free to tell me any improvements you would do.

#include <iostream>
using namespace std;

void quicksort(int **vector, int inf, int sup)
{
int *temp;
int i = inf-1;
int j = sup;
int cont = 1;

if(inf>=sup) return;
int pivot = *vector[sup];
cout << "pivot " << pivot << endl;
while(cont)
{
while(*vector[++i] < pivot);
while(*vector[--j] > pivot);
if(i < j)
{
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
}
else cont = 0;
}
temp = vector[i];
vector[i] = vector[sup];
vector[sup] = temp;

quicksort(vector, inf, i-1);
quicksort(vector, i+1, sup);
}

int main()
{
int *buffer[10];
int array[10] = {4,1,14,9,2,3,6,11,8,0};

for(int i=0; i<10; i++)
buffer[i] = &array[i];
for(i=0; i<10; i++) cout << *buffer[i] << " ";
cout << endl;

quicksort(buffer, 0, 9);

cout << "Sorted array : " << endl;
for(i=0; i<10; i++) cout << *buffer[i] << " ";
cout << endl;

return 0;
}

Apr 25 '06 #1
2 1982

camotito escreveu:
Hi, I want to sort an array of pointers, each position of this array
point to a position in an integer array.
There is a strange behavior when the 'pivot' is '0'. I am using Visual
C++, and when executing a segment violation error occur . When there is
no zeros in the integer
array, or when the pivot is never zero, this doesn't happen.
The pivot is always the last element. Try to change the last element in

the array for a non zero value and you will see it works.
Tell me something please. Thanks.
Also feel free to tell me any improvements you would do.

#include <iostream>
using namespace std;

void quicksort(int **vector, int inf, int sup)
{
int *temp;
int i = inf-1;
int j = sup;
int cont = 1;

if(inf>=sup) return;
int pivot = *vector[sup];
cout << "pivot " << pivot << endl;
while(cont)
{
while(*vector[++i] < pivot);
while(*vector[--j] > pivot);
I didn't test your code, but I realized that if pivot is the smallest
value in the sequence (as is the case in your example) you keep
decreasing j beyond the start of the array. You have to stop decreasing
j when you hit the 0 value. Try
while(*vector[--j] > pivot)
if (j == 0)
break;
if(i < j)
{
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
}
else cont = 0;
}
temp = vector[i];
vector[i] = vector[sup];
vector[sup] = temp;

quicksort(vector, inf, i-1);
quicksort(vector, i+1, sup);
}

int main()
{
int *buffer[10];
int array[10] = {4,1,14,9,2,3,6,11,8,0};

for(int i=0; i<10; i++)
buffer[i] = &array[i];
for(i=0; i<10; i++) cout << *buffer[i] << " ";
cout << endl;

quicksort(buffer, 0, 9);

cout << "Sorted array : " << endl;
for(i=0; i<10; i++) cout << *buffer[i] << " ";
cout << endl;

return 0;
}


Apr 25 '06 #2

camotito wrote:
using namespace std;

void quicksort(int **vector, int inf, int sup)


That doesn't seem like robust code....

-Brian

Apr 25 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by why | last post: by
3 posts views Thread by Lieven | last post: by
2 posts views Thread by nkharan | last post: by
2 posts views Thread by camotito | last post: by
6 posts views Thread by Baltazar007 | last post: by
2 posts views Thread by simo | last post: by
8 posts views Thread by aparnakakkar2003 | last post: by
12 posts views Thread by aparnakakkar2003 | last post: by
3 posts views Thread by jollyfolly | last post: by
reply views Thread by mihailmihai484 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.