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

}

[atlos]

oi,não sei como fazer isso no DEV,mas provavelmente o tamanho da pilha que ele reserva pro programa nao ta sendo grande o suficiente pra fazer toda essa recursão

[paul0liveira]

Então o que deve ser feito pra min consertar?

[atlos]

ve como seleciona um novo tamanho default pra pilha do programa pro compilador que voce ta usando

[Matheus Maldi]

O problema está nesta implementação com Partition

#include <stdio.h>#include <stdlib.h>#define MAX 1000 * 1000 * 100void quickSort(int vet[], int esq, int dir){	int ce = esq;	int cd = dir;	int meio = (ce + cd) / 2;	while (ce < cd){		while (vet[ce] < vet[meio]){			ce++;		}		while (vet[cd] > vet[meio]){			cd--;		}		if (ce <= cd){			int temp = vet[ce];			vet[ce] = vet[cd];			vet[cd] = temp;			ce++;			cd--;		}	}	if (cd > esq)		quickSort(vet, esq, cd);	if (ce < dir)		quickSort(vet, ce, dir);}void main(){	printf("Criando e inicializando o vetor...\n");	int i;	int *vetor = (int*)malloc(MAX * sizeof(int));	for (i = 0; i<MAX; i++){		vetor[i] = MAX - i;	}		printf("Ordenando o vetor...\n");	quickSort(vetor, 0, MAX - 1);	printf("\n10 primeiros elementos:\n");	for (i = 0; i < 10; i++){		printf("[%d] ", vetor[i]);	}	printf("\n10 Ultimos elementos:\n");	for (i = MAX - 10; i<MAX; i++){		printf("[%d] ", vetor[i]);	}	system("PAUSE");}

[paul0liveira]

 

O problema está nesta implementação com Partition

#include <stdio.h>#include <stdlib.h>#define MAX 1000 * 1000 * 100void quickSort(int vet[], int esq, int dir){	int ce = esq;	int cd = dir;	int meio = (ce + cd) / 2;	while (ce < cd){		while (vet[ce] < vet[meio]){			ce++;		}		while (vet[cd] > vet[meio]){			cd--;		}		if (ce <= cd){			int temp = vet[ce];			vet[ce] = vet[cd];			vet[cd] = temp;			ce++;			cd--;		}	}	if (cd > esq)		quickSort(vet, esq, cd);	if (ce < dir)		quickSort(vet, ce, dir);}void main(){	printf("Criando e inicializando o vetor...\n");	int i;	int *vetor = (int*)malloc(MAX * sizeof(int));	for (i = 0; i<MAX; i++){		vetor[i] = MAX - i;	}		printf("Ordenando o vetor...\n");	quickSort(vetor, 0, MAX - 1);	printf("\n10 primeiros elementos:\n");	for (i = 0; i < 10; i++){		printf("[%d] ", vetor[i]);	}	printf("\n10 Ultimos elementos:\n");	for (i = MAX - 10; i<MAX; i++){		printf("[%d] ", vetor[i]);	}	system("PAUSE");}

Este seu algoritmo está lega. Mas como eu citei, QuickSort com pivô no meio funciona, mas QuickSort com pivô no fim não, porque com pivô no meio ele é com laço de repetição, e com pivô no fim com recursividade entende... O problema eu descobri! é na recursividade, meu Dev não suporta esta quantidade de recursividade, terei que fazer o Quick com pivô no fim com laços de repetição... É bem mais complicado... Alguma dica?

ve como seleciona um novo tamanho default pra pilha do programa pro compilador que voce ta usando

Sou meio leigo no assunto, me disseram que tenho que usar outro compilador que suporte toda essa recursão... Essa seria a solução que você fala?

[LNW]

@paul0liveira

 

O programa funciona bem.. o problema realmente é o número elevado de chamadas recursivas que é feita. O seu programa acaba estourando a pilha, que é a porção de memória reservada pelo seu programa e usada durante essas chamadas. Nos executáveis produzidos pelo gcc/Windows, o tamanho padrão é de 2 MB. O amigo @atlos havia comentado e essa dúvida eventualmente aparece por aqui.

 

 

No Windows (apenas), basta passar a opção para o gcc (setando para 8 MB):

-Wl,--stack,8388608

No Linux, nem precisa fazer nada, basta compilar e rodar (tamanho padrão da pilha de 8 MB):

 

 

 

Esse Dev-C++ é uma IDE que utiliza o GCC, certo? Basta ir em alguma opção que permita adicionar opções ao Linker e usar a opção acima.

 

 

 

LNW

[atlos]

Sou meio leigo no assunto, me disseram que tenho que usar outro compilador que suporte toda essa recursão... Essa seria a solução que você fala?

 

nao com certeza,o que eu queria dizer foi o que o LNW disse,porém se um dia voce vier para o VS,um simples 

#pragma comment(linker,"/STACK:tamanhodapilha")

no topo do arquivo resolveria

[paul0liveira]

@paul0liveira

 

O programa funciona bem.. o problema realmente é o número elevado de chamadas recursivas que é feita. O seu programa acaba estourando a pilha, que é a porção de memória reservada pelo seu programa e usada durante essas chamadas. Nos executáveis produzidos pelo gcc/Windows, o tamanho padrão é de 2 MB. O amigo @atlos havia comentado e essa dúvida eventualmente aparece por aqui.

 

 

No Windows (apenas), basta passar a opção para o gcc (setando para 8 MB):

-Wl,--stack,8388608

No Linux, nem precisa fazer nada, basta compilar e rodar (tamanho padrão da pilha de 8 MB):

 

 

 

Esse Dev-C++ é uma IDE que utiliza o GCC, certo? Basta ir em alguma opção que permita adicionar opções ao Linker e usar a opção acima.

 

 

 

LNW

 

 

nao com certeza,o que eu queria dizer foi o que o LNW disse,porém se um dia voce vier para o VS,um simples 

#pragma comment(linker,"/STACK:tamanhodapilha")

no topo do arquivo resolveria

Entendi! Consegui! É Só ir em 'Ferramentas'->Opções do compilador->(Aqui vai ter um local escrito assim 'Adicionar esses comandos a linha de comando Linker' é só colocar esse parâmetro que voce me passou -Wl,--stack,8388608 e pronto ! Obrigado á todos que responderam ! Realmente me ajudou !