QuickSort - StackOverFlowError

6 de novembro de 2011 2 respostas

bacp 6 de novembro de 2011

Boa tarde,

Sou nova aqui no fórum e preciso de uma ajuda de vocês.
Estou fazendo um projeto de Estrutura de dados, para implementar 5 metodos de ordenação e particioná-los. O tamanho do vetor a ser ordenado é de 120mil valores.
Estou com o seguinte problema no QuickSort, até 40mil número ele ordena que é uma belezinha. Mas quando coloco os 120mil números, dá um erro de OverFlow.
O código é esse:

public void QuickSort(int vet[], int ini, int fimVet) {
      int meio;
                 if(ini < fimVet){
                        meio = partition(vet,ini,fimVet);
                        QuickSort(vet, ini, meio);
                        QuickSort(vet, meio+1,fimVet);
                }
        }
 
        public static int partition(int []v, int ini, int fim){
                int pivo, topo,i;
                pivo = v[ini];
                topo = ini;
 
                for(i=ini+1;i<fim;i++){
                        if(v[i]<pivo){
                                v[topo]=v[i];
                                v[i]=v[topo+1];
                                topo++;        
                        }
                }
                v[topo]=pivo;
                return topo;
        }

Vocês poderiam me ajudar, não sei o que posso fazer para que nao dê esse erro :(
Obrigada :P

2 Respostas

rxca 6 de nov. de 2011

bacp,

posso estar falando asneira, mas uma coisa chamou a minha atenção.
como seu vetor é grande (120.000 elementos) você vai precisar particioná-lo bastante. você está criando 3 variáveis - pivo, topo e i - a cada vez que você chama esse método. e como você vai chamá-lo várias vezes e, caso o menor elemento do conjunto seja o primeiro, seu algoritmo vai rodar em O(n^2).
E além de rodar em tempo quadrático, ele vai particionar o vetor de um jeito bem pior do que se fosse bem balanceado.

consigo pensar em duas sugestões: a primeira seria randomizar seu pivô; assim você minimiza as chances de cair um caso ruim. a outra ideia seria você colocar essas variáveis - pivo, topo e i - fora do método.
Vê se isso resolve, e avisa a gente!

[]'s

bacp 6 de nov. de 2011

Obrigada pela resposta, rxca

Então, esse trabalho tem que ser implementado no pior caso.
Vou verificar com essas dicas, e respondo se deu certo ou não.

E muito obrigada!!

Criado 6 de novembro de 2011

Ultima resposta 6 de nov. de 2011

Respostas 2

Participantes 2

2 Respostas

Topicos relacionados