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

[paul0liveira]

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");

}

[clodoaldoPeres]

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.