Duvida Merge! :D

6 respostas
CH11
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package mergesort;

/**
 *
 * @author CH
 */
public class Merge {

    public static void Merge(int vetor[], int inicio, int fim)
    {
        if ((fim-inicio+1)>1)
        {
            int mid = ((fim-inicio))/2;
            int[] subvet1 = new int[mid+1];
            preencher(vetor, subvet1, inicio, mid);
            int[] subvet2 = new int[fim-mid];
            preencher(vetor, subvet2, mid+1, fim);
            Merge(subvet1,inicio,mid);
            Merge(subvet2,mid+1,fim);
            finalorganize(subvet1,subvet2,vetor);
        }

     }
    public static void preencher(int vetor[], int subvet[], int inicio, int fim)
            {
        int sp=0;

        for(int x=inicio; x <= fim; x++)
        {
            subvet[sp]=vetor[x];
            sp++;
        }

    }
    public static void finalorganize(int subvet1[],int subvet2[], int vetor[])
    {
        int p1=0;
        int p2=0;
        int x=0;

        for( x=0; x<vetor.length; x++)
        {
            if(((p2>subvet2.length)&&(p1<subvet1.length))||(subvet1[p1]<subvet2[p2]))
            {
                vetor[x]=subvet1[p1];
                p1++;
            }
            else
            if(((p1>subvet1.length)&&(p2<subvet1.length))||(subvet2[p2]<subvet1[p1]))
            {
                vetor[x]=subvet2[p2];
                p2++;
            }
        }

    }

}
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package mergesort;

/**
 *
 * @author CH
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        int x[]= new int[8];
        x[0]=6;
        x[1]=7;
        x[2]=8;
        x[3]=3;
        x[4]=5;
        x[5]=4;
        x[6]=1;
        x[7]=2;

        Merge.Merge(x, 0, 7);
        for(int y=0; y<x.length; y++)
        {
            System.out.println(x[y]);
        }
    }

}
<blockquote>Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 1

at mergesort.Merge.finalorganize(Merge.java:48)

at mergesort.Merge.Merge(Merge.java:25)

at mergesort.Merge.Merge(Merge.java:23)

at mergesort.Merge.Merge(Merge.java:23)

at mergesort.Main.main(Main.java:30)

Java Result: 1</blockquote>

___<

Então galera, estou tentando desenvolver um merge sort pra entender melhor o funcionamento, o problema é que eu to encontrando um pouco de dificuldades e nao consguindo compilar o que seria minha ideia…

Um metodo recursivo responsavel por particionar o vetor, copiar os dados referentes originais nesses sub-vetores particionados e repetir, até que o vetor particionado se torne unitario. Quando isso ocorrer eu entre na função de reorganizar, comparando so 2 subvetores menores e organizando-os em forma crescente… Bom, é que eu estou estudando matematica computacional e essa coisa de ir quebrando em vetores menores nao parece ser tão facil hehe…

Bom, já agradeço de ante-mão ae galera! :smiley:

6 Respostas

suelengc

Olá CH,

Eu ia compilar seu código e ver o que estava errado… mas como estou no trabalho, é meio complicado rs… então entrei na wikipédia, tem lá o mergesort já em algumas linguagens, incluindo java.

Peguei o código do link acima, inseri numa classe, fiz uns ajustes (não de lógica pq a lógica deles está correta) e compilei e rodei, deu certo… segue code:

/* Vetor de entrada */
public class MergeSort {

  private static int[] vetor;


  public static void main (String[] args)
  {
         vetor = new int[7];

         for (int i = 0; i < 7; i++)
         {
             vetor[i] = (int)(Math.random()*100);
         }

         ImprimeVetor(vetor);

         merge(0, 6);

         ImprimeVetor(vetor);

  }

  public static void ImprimeVetor(int[] v){
    System.out.println("\nVetor:");
    for (int i = 0; i < v.length; i++)
         System.out.println("vetor[" + i + "] = " + v[i]);
  }

  /*
   * Método recursivo que divide o vetor em dois e depois os mescla e ordena
   */

  private static void merge(int inicio, int fim) {
   
          if (inicio < fim) {
                  int meio = (inicio + fim) / 2;
                  merge(inicio, meio);
                  merge(meio + 1, fim);
                  mesclar(inicio, meio, fim);
          }
   
  }
   
  /* 
   * Ordena dois trechos ordenados e adjacente de vetores e ordena-os
   * conjuntamente
   */
  private static void mesclar(int inicio, int meio, int fim) {
   
          int tamanho = fim - inicio + 1;
   
          /*
           * Inicialização de um vetor temporario para auxiliar na ordenação O
           * vetor temporário é uma cópia do trecho que será ordenado
           */
   
          int[] temp = new int[tamanho];
   
          System.arraycopy(vetor, inicio, temp, 0, tamanho);
   
          /*
           * Laço para ordenação do vetor, utilizando o vetor temporário, usando
           * índices i e j para cada trecho de vetor da mesclagem
           */
   
          int i = 0;
          int j = meio - inicio + 1;
   
          //A depender das condições, recebe um elemento de um trecho ou outro
          for (int posicao = 0; posicao < tamanho; posicao++) {
                  if (j <= tamanho - 1) {
                          if (i <= meio - inicio) {
                                  if (temp[i] < temp[j]) {
                                          vetor[inicio + posicao] = temp[i++];
                                  } else {
                                          vetor[inicio + posicao] = temp[j++];
                                  }
                          } else {
                                  vetor[inicio + posicao] = temp[j++];
                          }
                  } else {
                          vetor[inicio + posicao] = temp[i++];
                  }
          }
  }
}
suelengc

Ahhhh!!! Uma dica… se gostar de recursividade, análise de complexidade de algorítmos, e mais… no IME tem os famosos cursos de verão, que ocorrem todos os anos, no começo do ano (verão!!! rs)… no curso de Tópicos de Programação, você toma café, almoça e janta recursividade e análise de complexidade de algorítmos… o curso é excelente, barato, super legal e ainda é um plus para quem quer cursar mestrado lá…

Segue link:

http://www.ime.usp.br/~verao/index.php?secao=difusao&anoID=1&

Abs.,

suelengc

Ahhhh!!! Uma dica… se gostar de recursividade, análise de complexidade de algorítmos, e mais… no IME tem os famosos cursos de verão, que ocorrem todos os anos, no começo do ano (verão!!! rs)… no curso de Tópicos de Programação, você toma café, almoça e janta recursividade e análise de complexidade de algorítmos… o curso é excelente, barato, super legal e ainda é um plus para quem quer cursar mestrado lá…

Segue link:

http://www.ime.usp.br/~verao/index.php?secao=difusao&anoID=1&

Abs.,

CH11
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package mergesort;

import javax.swing.JOptionPane;

/**
 *
 * @author CH
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        int z = Integer.parseInt(JOptionPane.showInputDialog("Entre com o tamanho do vetor:"));

        int x[]= new int[z];

        for (int i = 0; i < z; i++)
         {
             x[i] = (int)(Math.random()*100);
         }

        Wikimerge.merge(0, (z-1), x);

        int pula=1;
        for(int y=0; y<x.length; y++)
        {
            System.out.print(x[y]);
            System.out.print("\t");
            pula++;
            if(pula>=5)
            {
                System.out.print("\n");
                pula=1;
            }
        }
    }

}
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package mergesort;

/**
 *
 * @author CH
 */
public class Wikimerge {

    public static void merge(int inicio, int fim, int vetor[]) {

        if (inicio < fim) {
                int meio = (inicio + fim) / 2;
                merge(inicio, meio, vetor);
                merge(meio + 1, fim, vetor);
                mesclar(inicio, meio, fim, vetor);
        }

}

    private static void mesclar(int inicio, int meio, int fim, int vetor[]) {

        int tamanho = fim - inicio + 1;

        /*
         * Inicialização de um vetor temporario para auxiliar na ordenação O
         * vetor temporário é uma cópia do trecho que será ordenado
         */

        int[] temp = new int[tamanho];

        System.arraycopy(vetor, inicio, temp, 0, tamanho);

        /*
         * Laço para ordenação do vetor, utilizando o vetor temporário, usando
         * índices i e j para cada trecho de vetor da mesclagem
         */

        int i = 0;
        int j = meio - inicio + 1;

        //A depender das condições, recebe um elemento de um trecho ou outro
        for (int posicao = 0; posicao < tamanho; posicao++) {
                if (j <= tamanho - 1) {
                        if (i <= meio - inicio) {
                                if (temp[i] < temp[j]) {
                                        vetor[inicio + posicao] = temp[i++];
                                } else {
                                        vetor[inicio + posicao] = temp[j++];
                                }
                        } else {
                                vetor[inicio + posicao] = temp[j++];
                        }
                } else {
                        vetor[inicio + posicao] = temp[i++];
                }
        }
}
}

Então galera, obrigado pela ajudar! É que é muito confuso e além disso um dos maiores pulos do gato que eu vi nesse codigo da suelengc é isso:

System.arraycopy(vetor, inicio, temp, 0, tamanho);

Eu nem sabia que isso existia, ajuda um montão!

Outra coisa que demorei mas acho que entendi:

vetor[inicio + posicao] = temp[i++];

Quando você usa i++ como indexador do vetor, você copia o valor de i e adiciona uma unidade a i posteriormente certo?

Seria o mesmo que isso?

vetor[inicio + posicao] = tempo[i]; i++;

Agora, também fiquei intrigado com o fato de ele já fazer a mudança no metodo mesclar direto no vetor principal, nos tutoriais, livros e coisas do genero, da a se entender que é criado um novo subvetor resultante da ordenação dos 2 subvetores iniciais que na verdade nesse codigo é apenas 1 com 2 ponteiros distintos (confuso né), ou seja até então ao me ver era para serem criados 3 novos subvetores no metodo mesclar, o interessante desse algoritmo aí é que ele já altera o vetor principal a partir dos subvetores sem a necessidade de mais custo adicional de memoria e processamento... Demorei para entender o funcionamento certinho, confesso que eu não vou conseguir guardar tão cedo, mas conseguir entender já foi um grande passo ... Enfim, complexo, porem nlog(n) :D

Valeu pela ajuda galera, fiz algumas alretaçõezinhas no codigo que pode tornar ele mais reutilizavel! :D

Agora é estudar bastante esse e passar para o quicksort e o heapsort! :D

OBS: Valeu pelas dicas de curso, eu moro em sp e realmente esse curso é praticamente essencial! Gostaria de cursa-lo mas nunca fui ao IME... Será que terá aulas de recursividade e análise de complexidade de algorítmos logo? Gostaria muito mesmo de fazer esse curso, apesar de eu ser burrinho até umas horas.... :[

suelengc

Olá CH,

Os cursos de verão no IME, incluindo o de Tópicos de Programação, se nada mudou, só ano que vem (no verão) terá nonvamente, as inscrições costumam abrir ao final do ano. As aulas costumam ser de janeiro a fevereiro/março (normalmente é possível “conciliar” o término do curso com o início das aulas nas faculdades).

A tempos atrás ouvi boatos de um projeto de cursos de inverno (similar aos de verão), mas não fiquei sabendo se esta idéia foi concretizada…

Mas de qualquer forma, acompanhe o link que passei, lá constam todas as informações inclusive quanto a datas dos cursos, inscrições, pagamento etc. Ai depois é só comparecer e ralar para conseguir ser aprovado :wink:

Abs.,

CH11

Olá, obrigado pela resposta pessoal… Referente a estes topicos de programação eu estou usando o livro do Cormen “Introduction to algorithms”, no entanto eu nao sou nenhum prodigio em matematica e por muitas vezes o livro me deixa na mão, para falar a verdade a grande parte dos exercicios eu não consigo fazer… Alguem teria alguma outra recomendação de livro, a maioria fala que o Cormen é a “Bíblia” mas no meu caso ele não está sendo muito didático… :oops:

Abraço! :smiley:

Criado 31 de março de 2011
Ultima resposta 1 de abr. de 2011
Respostas 6
Participantes 2