Ajuda com MergeSort

[Ander3PJ]

Ae pessoal…na boa?

to eu dnv aki atucando com esse problema hehehe…

é o seguinte

tenho que implementar o mergeSort… implementei mas ele tah dando IndexOfBoundsException… eu vi onde é, mas me parece que o código esta certo… não sei o que mudar pra solucionar isso…

abaixo esta o código do merge q implementei,…tem um System.out no meio para imprimir o “esq e o dir” que pelo que vi é ali que esta dando erro…

obrigado pela ajuda pessoal

abraços

[code]import java.util.*;

public class MergeSort {

public void mergeSort(ArrayList<Integer> vetor, int esq, int dir){
	System.out.println("Esq: "+esq+" Dir: "+dir);
	if(esq==dir) return;
	if(dir-1==1){
		if(vetor.get(esq)>vetor.get(dir)){
			int aux = vetor.get(esq);
			vetor.set(esq, vetor.get(dir));
			vetor.set(dir, aux);				
		}
		return;
	}
	int meio = (dir+esq)/2;
	mergeSort(vetor, esq, meio);
	mergeSort(vetor, meio+1, dir);
	uniao(vetor, esq, meio, dir);
}

public void uniao(ArrayList<Integer> vetor, int i, int m, int f){
	
	ArrayList<Integer> vetor1 = new ArrayList<Integer>(m-i+1);
	ArrayList<Integer> vetor2 = new ArrayList<Integer>(f-m+1);
	int aux, indVetor1 = 0, indVetor2 = 0;
	
	for(aux = i; aux < m + 1; aux++){
		vetor1.set(indVetor1, vetor.get(aux));
		indVetor1++;
	}
	for(aux = m; aux < f; aux++){
		vetor2.set(indVetor2, vetor.get(aux));
		indVetor2++;
	}
	
	int i1 = 0, i2 = 0;
	
	while(i1 < indVetor1 && i2 < indVetor2){
		if(vetor1.get(i1) < vetor2.get(i2)){
			vetor.set(i, vetor1.get(i1));
			i1++;
		}
		else{
			vetor.set(i, vetor2.get(i2));
			i2++;
		}
		i++;
	}		
	while(i1 < indVetor1){
		vetor.set(i, vetor1.get(i1));
		i1++;
		i++;
	}
	while(i2 < indVetor2){
		vetor.set(i, vetor2.get(i2));
		i2++;
		i++;
	}
	
}	

}[/code]

[luBSPJ]

Não entrando nos méritos da implementação que eu não sei se esta certo ok?

mas quando você faz

      for(aux = i; aux < m + 1; aux++){
         vetor1.set(indVetor1, vetor.get(aux));
         indVetor1++;
      }
      for(aux = m; aux < f; aux++){
         vetor2.set(indVetor2, vetor.get(aux));
         indVetor2++;
      } 

O set o arrayList vai pre-supor que a lista ja esteja populada naquela posicao, ou seja contenha um elemento naquela posicao, mas ali sua lista esta vazia ( não tem elemento ainda)

Olha o código do set do arrayList:

    public E set(int index, E element) {
	RangeCheck(index);

	E oldValue = elementData[index];
	elementData[index] = element;
	return oldValue;
    }

e o código de RangeCheck

    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }

como seu index eh 0 (sua posicao) e é igual a size (que é o número de elementos que a lista contém), ele da o erro.

Tenta usar ao invés de set

         vetor1.set(indVetor1, vetor.get(aux));
         vetor2.set(indVetor2, vetor.get(aux));

o método add

         vetor1.add(indVetor1, vetor.get(aux));
         vetor2.add(indVetor2, vetor.get(aux));

Eu não olhei seu código para saber se vai ordenar algo, mas caso vc ainda tenha duvidas quanto ao algoritmo, tem uma implementação em java aqui

Merge sort

ps1: quando vc for chamar seu método pela primeira vez, o index inicial eh 0 e o index final eh o tamanho da lista -1, pois são esses os valores que ele vai usar de base para pegar os index do array, se vc passar tamanho da lista, ele vai pensar que uma lista de tamanho 4 tem o quinto que esta na posição 4, o certo eh passar de 0-3 (elemento 0, elem 1, elem 2 e elem 3).

ps2: eu falo para vc rever depois o algoritmo e que não sei se esta certo porque essa parte me pareceu meio que gambiarra no código

      if (dir - 1 == 1)
      {
         if (vetor.get(esq) > vetor.get(dir))
         {
            int aux = vetor.get(esq);
            vetor.set(esq, vetor.get(dir));
            vetor.set(dir, aux);
         }
         return;
      }

Mas… vai saber neh, faz tempoooo que estudei algoritmos de ordenação

boa sorte

[Ander3PJ]

luBS velho,…vlw mesmo, nem notei essa parada…era ai mesmo o erro…

vo t falar uma coisa, pra mim o código inteiro parece meio gambiarra, mas fazer o que… foi PROFA. da minha facul q passou isso… v c pode…

pior q agora funcionou,…capenga mas funcionou… ordena metade dos numeros soh e desaparece com outros… vou continuar procurando erros de implementação do algoritmo dela uhauhauhauha

vlw pela mão velho

abração

[Ander3PJ]

outra coisa pessoal,…

todos os algoritmos do Merge q catei na net, nenhum é com ArrayList, e transformei uns 4 jah, mas todos dão o erro de indexofbounds… e tenho QUASE certeza q to fazendo certo…pq primeiro estou adicionando os numeros em um novo vetor e dps eu modifico,…mas continua dando o mesmo erro :’(

vlws

[luBSPJ]

hehehe relaxa, olha, alterei aquele merge do wikipedia… acho que funcionou… testa ai…

ps: se funcionar quero uma cerva depois

package lubs;

import java.util.ArrayList;
import java.util.List;

public class Mer
{

   public static void main(String[] args)
   {
      List<Integer> x = new ArrayList<Integer>();
      x.add(3);
      x.add(5);
      x.add(7);
      x.add(2);
      x.add(9);
      x.add(1);
      x.add(4);

      mergeSort(x, 0, x.size() - 1);
      for (Integer s : x)
      {
         System.out.println(s);
      }
   }

   public static void mergeSort(List<Integer> x, int esq, int dir)
   {
      if (esq < dir)
      {
         int medio = (esq + dir) / 2;
         mergeSort(x, esq, medio);
         mergeSort(x, medio + 1, dir);
         mezclar(x, esq, medio + 1, dir);
      }
   }

   public static void mezclar(List<Integer> x, int posEsq, int posDir, int posFin)
   {
      int[] xAux2 = new int[x.size()];
      int finIzq = posDir - 1;
      int posAux = posEsq;
      int numElementos = posFin - posEsq + 1;
      // Busca principal
      while (posEsq <= finIzq && posDir <= posFin)
         if (x.get(posEsq) < x.get(posDir))
         {
            xAux2[posAux++] = x.get(posEsq++);
         }
         else
         {
            xAux2[posAux++] = x.get(posDir++);
         }
      // Copia primeira metade
      while (posEsq <= finIzq)
      {
         xAux2[posAux++] = x.get(posEsq++);
      }
      // Copia segunda metade
      while (posDir <= posFin)
      {
         xAux2[posAux++] = x.get(posDir++);
      }
      // Copia veteor temporário no principal
      for (int i = 0; i < numElementos; i++, posFin--)
      {
         x.set(posFin, xAux2[posFin]);
      }
   }

}

ps2: isso aqui eh xunxera, vc não vai precisar provavelmente de uma array sempre do mesmo tamanho que a ArrayList, mas eu não to com tempo de ficar vendo certinho que tamanho criar o array… ai isso acho eh algo que de vc melhorar caso use esse codigo.

int[] xAux2 = new int[x.size()];

[Ander3PJ]

Velho, t devo uma cerva mesmo…até 2 uhauhauhauha

kra brigadão mesmo pela mão…eu soh testei ali e funcionou direitinho…
dps eu vou ver o que eu tava fazendo de errado hehehe

vlws mesmo pela ajuda

abração