QuickSort . I don't understand this behavior

[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 the OS tell me "quicksort.exe has encountered
a problem and needs to close". When there is no zeros in the integer
array, 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 se it works.
Tell me something please. Thanks

#include <iostream>
using namespace std;

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

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

if(inf>=sup) return;
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()
{
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;
}

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

camotito wrote:

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++,
Sorry, but C++ is off topic in comp.lang.c

You might want to try comp.lang.c++
and when executing the OS tell me "quicksort.exe has encountered
a problem and needs to close". When there is no zeros in the integer
array, 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 se it works.
Tell me something please. Thanks

#include <iostream>

[snip]

Yup. Definitely not C

- --

Lew Pitcher, IT Specialist, Corporate Technology Solutions,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFETPWgagVFX4UWr64RAinNAKDJ6CTecHbTbcFKZEfh4i n/ZtC1GwCgur1R
dUDzcfgJRmVQQdjO3xJ9jlM=
=wb/c
-----END PGP SIGNATURE-----

[Michael Mair]

camotito schrieb:

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 the OS tell me "quicksort.exe has encountered
a problem and needs to close". When there is no zeros in the integer
array, 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 se it works.
Tell me something please. Thanks
I will ignore the C++ specific stuff; read the comp.lang.c++
FAQ or post your code for code review to comp.lang.c++ -- your code
leaves much room for improvement.

Your problem is that you do not control the indices. Print the
indices within the corrected loops and at the beginning of
quicksort to see what is going wrong.

<snip>
void quicksort(int **vector, int inf, int sup)
{
int *temp;
int pivot = *vector[sup];
You are accessing vector[sup] without having checked whether
sup >= inf.
int i = inf-1;
int j = sup;
int cont = 1;

if(inf>=sup) return;
<snip>
while(cont)
{
while(*vector[++i] < pivot);
while(*vector[--j] > pivot);
while (i < j && *vector[++i] < pivot);
while (i < j && *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);
quicksort(vector, inf, i > inf ? i-1 : inf);
quicksort(vector, i < sup ? i+1 : sup, sup);
}

<snip>

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.