Jump to content

Merge java


NetWarrior
 Share

Recommended Posts

? 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 😄   ;)

Link to comment
Share on other 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. ;)

<3 life

Link to comment
Share on other 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. 😄

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

Link to comment
Share on other 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. 😄

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:

geshild5.png

<3 life

Link to comment
Share on other 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.

😁

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

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.