[C++] problema Segmentation fault

[carugo]

Ciao a tutti

Ho un problema con questo programmino che utilizza l 'algoritmo quicksort per ordinare un vettore di interi creati a random, in run-time mi va in crash dovuto a un segmentation fault non capisco perchè.....

#include <cstdlib>
#include <iostream>

using namespace std;

const int QUANTI=100;

int v[QUANTI];

void stampaVet (int v[], int num_ele)
{
for (int i=0; i<num_ele; i++)
cout<< v[i] << " ";
}

void quickSort( int arr[], int left, int right)
{
int i = left;
int j = right;
int y = 0;

int z = arr[(left + right)/2];

do
{
while(arr[i] < z) i++;
while(z < arr[j]) j--;

if (i<=j)
{
y= arr[i];
arr[i]= arr[j];
arr[j]= y;
i++;
j--;
}
} while (i<=j);

if (left < j)
quickSort(arr,left,j);

if (i < right);
quickSort(arr,i,right);
}

void preparaVettore (int v[] , int num_ele)
{
for (int i=0; i<num_ele; i++)
v[i]= rand();
}


int main(int argc, char *argv[])
{

preparaVettore(v,QUANTI);
stampaVet(v,QUANTI);
quickSort(v,0,QUANTI-1);
stampaVet(v,QUANTI);


system("PAUSE");
return EXIT_SUCCESS;
}


Qualche idea?

TNX a tutti

[wingman87]

Prova ad eseguire l'algoritmo con carta e penna (o anche mentalmente) con questo array:
1 2 3 4 5 1 1

C'è chiaramente qualcosa che non va... rivedi l'algoritmo del quicksort, hai dimenticato qualcosa.

[sottovento]

void quickSort( int arr[], int left, int right)
{
int i = left;
int j = right;
int y = 0;

int z = arr[(left + right)/2];

do
{
while(arr[i] < z) i++;
while(z < arr[j]) j--;

if (i<=j)
{
y= arr[i];
arr[i]= arr[j];
arr[j]= y;
i++;
j--;
}
} while (i<=j);

if (left < j)
quickSort(arr,left,j);

if (i < right);
quickSort(arr,i,right);
}

Zoomiamo ancora:

if (i < right);

Questa fa si che il tuo codice sia sempre e comunque ricorsivo, quindi 'sta routine continua a chiamare se stessa fino ad esplodere.

Togli il punto e virgola

[wingman87]

Quello non l'avevo visto, che occhio di falco! :)
Ma se non ho visto male, corretto quello potrebbero esserci altri problemi.

[gbhu]

Tutto bene con i due cicli while piazzati subito all'inizio del blocco do ?

[carugo]

Grazie a tutti raga :)

Stavo diventando pazzo grazie Sottovento ora tutto ok alla prossima

CIauzzzz

[sottovento]

Quello non l'avevo visto, che occhio di falco! :)

Si chiama fortuna :D