Comparar e ordenar vetores - Lógica

6 de novembro de 2009 13 respostas

thiagoponte 6 de novembro de 2009

Na aula passada o professor mostrou como se ordena vetores, do modo mais demorado possível, onde ele testa todas as possibilidades, e usando o tal do “bubblesort”.
Ele passou um exercício, e um colega disse que era algo como pegar 2 baralhos já ordenados, comparar as cartas, e juntar as cartas em um novo monte de cartas.
Não quero a resposta com código java, até porque a prova é em portugol, só preciso de ajuda com a lógica. Depois que eu entender que vou fazer em java.

Exercício:
Ler um vetor a de n valores já ordenados. Ler um vetor b de m valores já ordenados. Transferir para um vetor c todos estes valores, mantendo a cada transferência o 3º vetor ordenado. A ordenação dos 3 vetores é crescente.

Considerações:
Eu sei que vou ter que percorrer os 2 vetores, mas se fosse para utilizar o comando for, qual seria o número de vezes a percorrer? Talvez um while ou do while seria melhor?
O terceiro vetor tem o tamanho n+m?
As comparações dos valores dentro dos vetores, tem que ocorrer dentro da estrutura de repetição.

13 Respostas

entanglement 6 de nov. de 2009

Se você aceitar valores repetidos, então o vetor resultado tem tamanho m + n.
Você precisa ter três índices (isso não quer dizer “três laços”, mas apenas 1, conforme você vai ver.)
Um para indicar o elemento corrente no primeiro vetor.
Um para indicar o elemento corrente no segundo vetor.
Um para indicar o elemento corrente no vetor resultado.
Basicamente, como você disse, você pega o elemento corrente do primeiro e o elemento corrente do segundo vetores, e os compara.
Então você pega o menor elemento deles e o põe no vetor resultado. O “for” necessário é só porque há m + n elementos no destino.

rmendes08 6 de nov. de 2009

O índice do vetor resultado incrementa incondicionalmente, enquanto que os outros dois incrementam dependendo de qual vetor foi escolhido o elemento …

ccefetpb 6 de nov. de 2009

Existem um algoritmo cujo objetivo e justamente esse unir dois vetores ordenados enfim conselho , busque no google algortimo de ordenação por intercalação .È algo mais ou menos assim : os vetores não ja estao ordenados existem dois valores i e j que marcam a posicao do tamanho do vetor ( o laço consiste em pos < vet3.size ) ambos começando de zero.Entao vc compara qual é o menor( ou maior ) vet1[i] ou vet2[j] .Caso seja vet1[i] vc salva o valor no vet3[ pos ] , incrementa o i e o pos . E na proxima iteração vai acontecer a mesma coisa so que o valor do vet1 que vai ser comparado é posicao seguinte.Outra coisa tem que ficar testando tambem se a posicao que o i e o j tão apontando esta nos limites do vetor caso um deles não esteja da um break e insere os elementos do outro vetor em sequencia.
bem é isso desculpe se pela pressa eu falei alguma coisa errada .
vlw

blaine 6 de nov. de 2009

O número de iterações do loop será exatamente igual ao tamanho do terceiro vetor.

Agora o tamanho do terceiro vetor depende se você permite valor repetido ou não.
Se sim, tamanho do terceiro vetor será igual m+n, como o pessoal já falou.
Se não, aí depende da quantidade de valores repeditos você terá. Seria isso m+n - q, onde ‘q’ seria a quantidade de valores repetidos.

thiagoponte 6 de nov. de 2009

Seria algo assim?

import java.util.Scanner;

public class QuestaoMatriz {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("DIGITE O TAMANHO DO PRIMEIRO VETOR: ");
		int m = s.nextInt();
		System.out.println("DIGITE O TAMANHO DO SEGUNDO VETOR: ");
		int n = s.nextInt();
		int a[] = new int[m];
		int b[] = new int[n];
		int c[] = new int[m + n];
		for (int i = 0; i < a.length; i++) {
			System.out.println("valores de a: ");
			a[i] = s.nextInt();
		}
		for (int i = 0; i < b.length; i++) {
			System.out.println("valores de b: ");
			b[i] = s.nextInt();
		}
		for (int i = 0; i < c.length; i++) {
			int x = a.length;
			int y = b.length;
			int z = c.length;
		}
	}
}

blaine 9 de nov. de 2009

Para que você utiliza esse último ‘for’?

Não entendi sua utilidade.

ccefetpb 9 de nov. de 2009

public class testeArray {
	public static void main(String[] args) {
		int[] v1 = {1,2,3};
		int[] v2 = {2,5,7};
		
		int[] v3 = new int[6];

		int i = 0 ;
		int j = 0;
		int k = 0;

		for ( int cont = 0 ; cont < v1.length ; cont++ ) {
			System.out.println( v1[cont] + " ");
		}
		
		for ( int cont = 0 ; cont < v2.length ; cont++ ) {
			System.out.println( v2[cont] + " ");
		}
		
		while ( k != v3.length ) {
			
			if ( i == v1.length ) {
				for ( ; j < v2.length ; j++)
					v3[k++] = v2[j];
				break;
			}
			
			if ( j == v2.length ) {
				for ( ; i < v1.length ; i++)
					v3[k++] = v1[i];
				break;
			}
			
			if ( v1[i] < v2[j] ) {
				v3[k++] = v1[i++];
			}else
				v3[k++] = v2[j++];


		}
		
		for ( int cont = 0 ; cont < v3.length ; cont++ ) {
			System.out.println( v3[cont] + " ");
		}

		
		
	}

}

ccefetpb 9 de nov. de 2009

Desculpe a demora na resposta estou sem internet em casa e so posso acessar do trabalho , bem eu testei a logica acima e funcionou . Qualquer erro relata ai que eu NAO dou uma olhada .

hehe.
vlw !

ccefetpb 9 de nov. de 2009

Bem desculpe a demora na resposta é que to sem internet em casa.Bem o codigo acima acabei de fazer estestei parece que funcionou sem erro , a logica e como eu ja tinha explicado , note que os vetores ja foram inicializados ordenados .As variaveis i marca a posição do primeiro vetor , j do segundo e k do terceiro .Os testes dentro do while são pra evitar o exceção pelo estouro do indice , como eu tambem ja expliquei .Bem qualquer duvida posta ai que eu NAO dou uma olhada .hehe , brincadeira.

vlw.

blaine 9 de nov. de 2009

Eu fiz assim:

import java.util.Arrays;

public class lab8 {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 58, 12, 34, 75};
        int[] b = {3, 5, 7, 9, 11, 5, 7, 9, 84, 6};
        int[] c = new int[a.length + b.length];

        Arrays.sort(a);
        Arrays.sort(b);

        for (int i = 0, j = 0, it = 0; i < a.length || j < b.length; it++) {
            if (i >= a.length) {
                c[it] = b[j];
                j++;
            } else if (j >= b.length) {
                c[it] = a[i];
                i++;
            } else {
                if (a[i] <= b[j]) {
                    c[it] = a[i];
                    i++;
                } else {
                    c[it] = b[j];
                    j++;
                }        
            }
        }

        for (int jt = 0; jt < c.length; jt++) {
            System.out.println(c[jt]);
        }
    }
}

ccefetpb 10 de nov. de 2009

Sem duvida que o seu codigo é mais eficiente que o meu , muito inteligente colocar os elses dentro do for , foi mal … mas ambos fazem a mesma coisa .Parabns mesmo.hehe.
:lol:

blaine 10 de nov. de 2009

Seu código funciona, é isso que importa.

Não há muita diferença entre o me código e o seu.

Eu só postei o meu porque eu evito usa o ‘break’.
Pra te falar a verdade nem eu mesmo sei o porque, acho que foi o meu professor da facul que odiava o 'break. Acho que acabei pegando a mania dele. ¬¬

A única coisa que eu mudaria no seu código é a instanciação do terceiro vetor.
Deixando ele dinâmico, mas eu acho que você sabe disso e só fez estático porque era um teste. =P

Mas valeu…

ccefetpb 10 de nov. de 2009

Interessante né , o break é uma daquelas polemicas tipo ofor infinito , quando eu aprendi a programar achava isso (o break , for infinito , o goto) seboseiras , falava mal de quem usava e tudo , ai eu fui aprender c e depois java e agora eu não consigo mais programar sem usar o break , sei que é um mal habito .
ps : o goto pra mim ainda é uma seboseira e o for infinito é usavel mas pouco confiavel .

Criado 6 de novembro de 2009

Ultima resposta 10 de nov. de 2009

Respostas 13

Participantes 5

13 Respostas

Topicos relacionados