Duvida Merge! :D

CH11 · Março 31, 2011, 2:10am


/*
 * 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]);
        }
    }

}

[quote]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[/quote]

___<

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!

suelengc · Março 31, 2011, 8:31am

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 · Março 31, 2011, 8:35am

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 · Março 31, 2011, 8:36am

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 · Março 31, 2011, 11:18am

[code]/*

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

}
[/code]

[code]/*

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++];
            }
    }

}
}
[/code]

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:

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

Outra coisa que demorei mas acho que entendi:

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?

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

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)

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

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

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 · Março 31, 2011, 12:20pm

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

Abs.,

CH11 · Abril 1, 2011, 10:51am

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!

system · Dezembro 24, 2015, 10:02am

Duvida Merge! :D

Cursos de Mobile

Cursos de Programação

Cursos de Front-end

Cursos de DevOps

Cursos de Design & UX

Cursos de Business

Cursos de Data & BI