Ir ao conteúdo
  • Cadastre-se
paul0liveira

Erro com ordenação de uma quantidade alta de elementos com o QuickSort em C

Recommended Posts

Olá galera, venho aqui pedir ajuda de vocês quanto a um erro que está ocorrendo com meu QuickSort com pivô no último elemento.

Bom, estou fazendo um artigo cientifico e preciso coletar dados da velocidade de ordenação do QuickSort com diferentes números de elementos.

Bom, meu Quick está ordenando até mais ou menos 40mil e alguma coisa números. Quando coloco a partir de 50mil por exemplo, o Quick simplesmente não ordena, e meu Dev dá erro e para! E eu preciso de dados do Quick ordenando de 10mil 20mil,30mil... até 100mil elementos!

Minha IDE é Dev C++, e minha máquina é um notebook na HP i5 4gb de memória RAM. Eu passei este algoritmo para alguns amigos (que usam Dev tb) e continuou dando erro... Não sei o que causa este erro.. 

De princípio achei que era o Dev, mas um colega meu me passou um outro QuickSort, com pivô no meio, e meu Dev ordenou 100mil elementos tranquilo! Isso me deixou ainda mais confuso! Sem falar que no artigo preciso coletar dados do SelectionSort também, e o selection ordena 100mil elementos tranquilo também...Bom eu posso estar enganado mas não creio que seja a IDE.

O erro não deve ser no algoritmo porque 40mil ele ordena! Quando passa disso ele dá erro!

Aparece uma janela falando que o 'QuickSort.exe' parou de funcionar, e na tela do Dev C++ aparece: 'return value 3221225725'

Quem quiser dá uma olhada no código (Em C) aí está: A quem se disponibilizar de me ajudar, eu agradeço desde já!

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int Quick(int vetor[],int ini,int fim){
if (fim< ini)
return;
int meio = partition (vetor,ini,fim);
Quick(vetor,ini,meio-1);
Quick(vetor,meio+1,fim);
}
 
int partition (int vetor[],int ini,int fim){
int temp,i,atual,pivo = vetor[fim];
int menores = ini-1;
for (atual=ini;atual<fim;atual++){
if(vetor[atual]<pivo){
menores++;
temp=vetor[menores];
vetor[menores]=vetor[atual];
vetor[atual]=temp;
}
}
temp = vetor[menores+1];
vetor[menores+1]=vetor[fim];
vetor[fim]=temp;
return menores+1;
}
 
void main(){
int i,vetor[MAX];
for(i=0;i<MAX;i++){
vetor=MAX-i;
}
printf(" [%d] ",vetor);
 
Quick(vetor,0,MAX-1);
 
for(i=0;i<MAX;i++){
printf("[%d] ",vetor);
}
system("PAUSE");
}

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá. Parece que você tá quebrando a stack devido a muitas chamadas recursivas (muitas delas desnecessárias). Alem do mais, parece que o teu algoritmo quick sort tá confuso. Afinal a tua variavel pivo deveria ser colocada na posição final apos a troca sendo que isso forma 2 sublistas desordenadas que então são ordenadas (pode ser recursivamente). Segue exemplo e aconselho que dê uma olhada mais profundamente nos passos do algoritmo para que possa implementá-lo de maneira correta:

#include <stdio.h>#include <stdlib.h>#define MAX 100000void quickSort(int valor[], int esquerda, int direita){int i, j, x, y;i = esquerda;j = direita;x = valor[(esquerda + direita) / 2];while(i <= j){while(valor[i] < x && i < direita){i++;}while(valor[j] > x && j > esquerda){j--;}if(i <= j){y = valor[i];valor[i] = valor[j];valor[j] = y;i++;j--;}}if(j > esquerda){quickSort(valor, esquerda, j);}if(i < direita){quickSort(valor, i, direita);}}int main(){    int i, vetor[MAX];    for(i=0;i<MAX;i++){        vetor[i]=MAX-i;    }    printf("***** [%d] \n",vetor[i]);        quickSort(vetor,0,MAX-1);        for(i=0;i<MAX;i++){        printf("[%d] ",vetor[i]);    }    system("PAUSE");    return 0;} 

Espero ter ajudado.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×