stack overflow

22/10/2007

1

Opa , galera queria saber como corrigir o stack Overflow no meu quicksort

Chamada na main
quickSort(case1Ordenation, 0, tam-1);


Função:
//Partition

void partition(int vet[], int primeiro, int ultimo, int *j) {
           
int up, down, temp, a;
     a =  vet[primeiro];
    up = ultimo;
    down = primeiro;
troc = 0, comp = 0;
               
while(down < up){
comp++;
while(vet[down] <= a && down < ultimo){
comp = comp +2;
            down++;
}
while(vet[up] > a){
comp++;
                up--;
}
                if(down < up) {
comp ++;
temp = vet[down];
                    vet[down] = vet[up];
                vet[up] = temp;
                }
    }

vet[primeiro] = vet[up];
    vet[up] = a;
    *j = up;

}

//  Quicksort

void quickSort(int vet[], int primeiro, int ultimo){

int j;

if(primeiro >= ultimo)
return;
           
partition(vet,primeiro,ultimo,&j);
quickSort(vet,primeiro,j-1);
quickSort(vet,j+1,ultimo); 
troc++;
}


a segunda chamada recursiva do quickSort (quickSort(vet,j+1,ultimo);) pelo que percebi que esta fazendo dar stack overflow, mais nao consigo pensar um jeito de corrigir , pois com um vetor menos que 5000 funciona nomalmente, porem com 5000 ou mais stack overflow.


Responder

Posts

22/10/2007

Autilio

a quem interessar , a solucao foi implemtar outro quicksort

void swap(int *a, int *b) {
  int t=*a; *a=*b; *b=t;
}

void quickSort(int vet[], int primeiro, int ultimo) {
  
int pivo, a, up, comp = 0, troc = 0;
if (ultimo > primeiro + 1) {
comp++;
pivo = vet[primeiro];
a = primeiro + 1;
up = ultimo;
    while (a < up) {
comp++;
if (vet[a] <= pivo){
a++;
comp++;
}
else{
swap(&vet[a], &vet[--up]);
}
}
    
swap(&vet[--a], &vet[primeiro]);
    quickSort(vet, primeiro, a);
    quickSort(vet, up, ultimo);
troc++;
}
}



Responder