• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

NetWarrior

Merge java

10 mensagens neste tópico

:-[ psl tou um bocado ... Isto tudo fala de uma classe que ordena um vector de inteiros pelo metodo merge(classe a ser desenvolvida com base nas referencias abaixo). É o seguinte:

A is an array and p, q, and r are indices numbering elements of the array such that p ≤ q

< r. The procedure assumes that the subarrays A[p q] and A[q + 1 r] are in sorted order.

It merges them to form a single sorted subarray that replaces the current subarray A[p r].

MERGE(A, p, q, r)
1   n1 ← q - p + 1
2   n2 ← r - q
3   create arrays L[1  n1 + 1] and R[1  n2 + 1]
4   for i ← 1 to n1
5       do L[i] ← A[p + i - 1]
6           for j ← 1 to n2
7             do R[j] ← A[q + j]
8               L[n1 + 1] ← ∞
9               R[n2 + 1] ← ∞
10             i ← 1
11             j ← 1
12             for k ← p to r
13             do if L[i] ≤ R[j]
14                  then A[k] ← L[i]
15                      i ← i + 1
16                     else A[k] ← R[j]
17                      j ← j + 1

acima é o fluxograma e algum texto tirado do livro: Introduction to Algorithms, Thomas H. Cormen

Ja estive a tentar programar em JAva mas estou com alguns problemas....  como podem ver no fluxograma temos esses dois infinitos que nao percebo bem como os representar o texto fala deles e diz:

The following pseudocode implements the above idea, but with an additional twist that avoids

having to check whether either pile is empty in each basic step. The idea is to put on the

bottom of each pile a sentinel card, which contains a special value that we use to simplify our

code. Here, we use ∞ as the sentinel value, so that whenever a card with ∞ is exposed, it

cannot be the smaller card unless both piles have their sentinel cards exposed. But once that

happens, all the nonsentinel cards have already been placed onto the output pile. Since we

know in advance that exactly r - p + 1 cards will be placed onto the output pile, we can stop

once we have performed that many basic steps.

O que me aconteçe é que a classe que criei nao esta a fazer o que devia .... pois mostra um valor repetido n vezes. onde n = ao numero de elementos a ordar.

aqui fica o code:

public class Merge {

private int a[];
private int p,q,r;

public Merge(int[] a)
{
	this.a = a;
}

public void show()
{
	for(int i =0; i < a.length-1; i++ )
			System.out.print(a[i] + " ");
			System.out.println("\n");
}

public void sort()
{	
	p = 0;
	r = a.length-1;
	q = (int)(a.length / 2);

	int n1 = q ;
	int n2 = r - q ;
	int i,j,k;

	int[] r = new int[n1+1];
	int[] l = new int[n2+1];

	for(i=0; i < n1; i++)
	{ l[i] = a[i]; }

	for(j=0; j < n2; j++)
	{ r[j] = a[q+j]; }
	////////////////////////////////////
	l[n1] = java.lang.Integer.MAX_VALUE;
	r[n2] = java.lang.Integer.MAX_VALUE;
	i=0;
	j=0;

	for(k=0; k < a.length;k++)
	{ 
		if(l[i] <= r[j])
		{
			a[k]=l[i];
			i = i++;
		}
		else
		{
			a[k] = r[j];
			j = j++;
		}
	}
}
public static void main(String[] args) 
{
	int a[] = {2,5,4,1,7,8,10};

	Merge ins = new Merge(a);

	ins.show();
	ins.sort();
	ins.show();

}
}

em relação ao fluxograma o código nao m pareçe estar mal de todo ... nao consigo encontrar muito bem o problema. Se alguem tiver a vontade neste tipo de programação tendo por base fluxogramas que me de uma ajudinha. Desde já o meu obrigado a quem teve a paciencia para ler todo este texto :D  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem-vindo ao fórum, NetWarrior.

Para a próxima usa uma ferramenta chamada GeSHi que se encontra nas ferramentas de edição do tópico, de forma a facilitar a leitura do código. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

OBrigado... lamento .. vou tentar editar. Ainda procurei aqui para cima um butãozinho que tivesse aquele icone Code como já vi em outros foruns mas nao encontrei.. obrigado pela explicação. :D

Edit: Já está ;) era o cardinal :D hehe e que inteligente até detecta a linguagem java.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

OBrigado... lamento .. vou tentar editar. Ainda procurei aqui para cima um butãozinho que tivesse aquele icone Code como já vi em outros foruns mas nao encontrei.. obrigado pela explicação. :D

Edit: Já está ;) era o cardinal :D hehe e que inteligente até detecta a linguagem java.

Eu já tinha modificado o teu post, mas já agora, deixo aqui como fazer:

geshild5.png

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não acredito que ninguem me da uma ajudinha.... vá lá pessoal... alguem me pode dizer o que estou a fazer de errado no meu código comparando com o fluxograma.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

obrigado Knitter!

eu tambem ando a rever o código ..... a ver se percebo o que se passa. :wallbash:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

continuo sem chegar lá....grrrr  :wallbash:

será que estou a fazer mal o raciocinio para determinar o p, q e r ????? :thumbdown:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

já resolvi o problema... e hje codifiquei o quickSort ....

agora tou a ter é problemas a comparar eles..... nao esta a bater certo.... o InsertSort esta a ser o mais eficiente.

:cheesygrin:

(estou a falar de algoritmos de ordenação)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desc mas estive bastante ocupado e acabei por me esquecer, sorry :D

Como é que estás a medir a performance dos algoritmos?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora