QuickSort . I don't understand this behavior

C

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;
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()
{
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;
}
 
L

Lew Pitcher

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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

iD8DBQFETPWgagVFX4UWr64RAinNAKDJ6CTecHbTbcFKZEfh4in/ZtC1GwCgur1R
dUDzcfgJRmVQQdjO3xJ9jlM=
=wb/c
-----END PGP SIGNATURE-----
 
M

Michael Mair

camotito said:
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.

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;

while(cont)
{
while(*vector[++i] < pivot);
while(*vector[--j] > pivot);

while (i < j && *vector[++i] < pivot);
while (i said:
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);


quicksort(vector, inf, i > inf ? i-1 : inf);
quicksort(vector, i < sup ? i+1 : sup, sup);

<snip>

Cheers
Michael
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top