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

[camotito]

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;
vector = vector[j];
vector[j] = temp;
}
else cont = 0;
}
temp = vector;
vector = 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 = &array;
for(i=0; i<10; i++) cout << *buffer << " ";
cout << endl;

quicksort(buffer, 0, 9);

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

return 0;
}

 

[Marcelo Pinto]

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;
vector = vector[j];
vector[j] = temp;
}
else cont = 0;
}
temp = vector;
vector = 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 = &array;
for(i=0; i<10; i++) cout << *buffer << " ";
cout << endl;

quicksort(buffer, 0, 9);

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

return 0;
}

 

[BigBrian]

using namespace std;

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

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

-Brian