Merge java

[NetWarrior]

? 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 😄   😉

[Triton]

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. 😉

[NetWarrior]

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. 😄

Edit: Já está 😉 era o cardinal 😄 hehe e que inteligente até detecta a linguagem java.

[Triton]

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. 😄

Edit: Já está 😉 era o cardinal 😄 hehe e que inteligente até detecta a linguagem java.

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

http://img395.imageshack.us/img395/1007/geshild5.png

[NetWarrior]

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.

[Knitter]

Vou ver isso entretanto....

[NetWarrior]

obrigado Knitter!

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

[NetWarrior]

continuo sem chegar lá....grrrr 

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

[NetWarrior]

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.

😁

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

[Knitter]

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

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