[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]

Originariamente inviato da wingman87

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

Si chiama fortuna