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

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

 

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?

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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):

 

quick2.png

 

 

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

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
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

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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):

 

quick2.png

 

 

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 !

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

×