Cormen - Pseudocodigo confuso

26 de outubro de 2010 11 respostas

aajjbb 26 de outubro de 2010

Estudando algoritimos com o livro do cormen… terceira edição, logo ja me confundi no segundo capitulo, com o seguinte pseudo codigo

for j ← 2 to length[A]
do key ← A[ j ]
✄ Insert A[ j ] into the sorted sequence A[1 … j − 1].
i ← j − 1
while i > 0and A[i ] > key
do A[i + 1] ← A[i ]
i ←i − 1
A[i + 1] ← key

como estou acostumado com o java, essas setas estao um pouco estranhas para mim, mesmo passando a convenção do pseudo codigo ainda estou confuso, se algume pudesse me ajudar

PS: nao achei necessario o uso de por se tratar de pseudocodigo.

11 Respostas

aajjbb 26 de out. de 2010

identação correta

for j ← 2 to length[A]
   do key ← A[ j ]
     ✄ Insert A[ j ] into the sorted sequence A[1 .. j − 1].
     i ← j − 1
     while i > 0and A[i ] > key
        do A[i + 1] ← A[i ]
           i ←i − 1
     A[i + 1] ← key

EDIT (Moderador) - Para inserir código ou texto com formatação, use as tags [ code ] … [ /code ]

entanglement 26 de out. de 2010

A seta é o sinal de atribuição, ou “=” no Java. Satisfeito?

(Em particular, quando comecei a aprender programação, achava que o operador de atribuição “=” é que era muito confuso, além de se confundir com o operador de igualdade “=” que é o mesmo em muitas linguagens. Eu estava acostumado com a seta mesmo, que é uma notação mais matemática.)

aajjbb 26 de out. de 2010

for j ← 2 to length[A]

em java seria o mesmo que

for(int j = 2; j < A.length; j++) {}

entanglement 26 de out. de 2010

Quase. Seria isto:

for(int j = 2; j <= A.length; j++)

Isso, é claro, se o array começar na posição 1. (Em Java ele começa no 0).

aajjbb 27 de out. de 2010

for j ← 2 to length[A]  
      do key ← A[ j ]  
        ✄ Insert A[ j ] into the sorted sequence A[1 .. j − 1].  
        i ← j − 1  
        while i > 0and A[i ] > key  
           do A[i + 1] ← A[i ]  
              i ←i − 1  
        A[i + 1] ← key

e o "do" seguido de "while" seria como um do-while como no java mesmo?

bezier_curve 27 de out. de 2010

for j ← 2 to length[A]    
    do key ← A[ j ]

for (int j = 2;  j <= A.length; ++j) {
    key ← A[ j ]  
}

while i > 0and A[i ] > key    
         do A[i + 1] ← A[i ]    
            i ←i − 1

while (i > 0 && A[i] > key) {
    A[i + 1] ← A[i ]

Aí não tem nenhum “do/while”. (Não tenho o livro do Cormen aqui comigo, mas acho que o equivalente do do/while do Java no livro do Cormen deve ser o “repeat…until”, não “do…while”.)

Rapaz, você não leu o livro desde o começo. Se tivesse lido, provavelmente entenderia melhor a notação.

aajjbb 27 de out. de 2010

estou tentando implementar ele em java, mas ainda nao deu certo…

public void InsertSort(int a, int b, int c, int d, int e) {
		int[] A;
		A = new int[5];
		A[0] = a;
		A[1] = b;
		A[2] = c;
		A[3] = d;
		A[4] = e;

		for (int j = 2; j <= A.length; ++j) {
			int key = A[j];
			int i = j - 1;
			while (i > 0 && A[i] > key) {

				A[i + 1] = A[i];
				i = i - 1;
				A[i + 1] = key;
			}
		}
	}

tomo a seguinte stack trace. mas ainda nao compreendi o erro.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5

at br.com.cormen.InsertSort.InsertSort(InsertSort.java:14)

at br.com.cormen.InsertSort.main(InsertSort.java:26)

entanglement 27 de out. de 2010

É que o array do livro do Cormen começa em 1 e vai até N. Em Java, um array começa em 0 e termina em N - 1. Então, você tem de acertar o programa para levar isso em conta. Não dá para simplesmente olhar o algoritmo e copiar sem ententer o que está acontecendo.

aajjbb 29 de out. de 2010

é… me indicaram esse como um otimo livro… mas para quem nao é muito experiente… ele é um verdadeiro desafio… estou analizando melhor o pseudocodigo e logo vou postar ele…

aajjbb 29 de out. de 2010

cheguei ao seguinte codigo, mas nao obtive exito, acho que agora, os problemas se diminuira, acho q o codigo ta bem parecido como o proposto pelo exercicio...

public void calculaSort(int a, int b, int c, int d, int e) {
		int[] A;
		A = new int[5];
		A[0] = a;
		A[1] = b;
		A[2] = c;
		A[3] = d;
		A[4] = e;

		for (int j = 0; j <= A.length; ++j) {
			int key = A[j];
			int i = j - 1;
			while (i > 0 && A[i] > key) {

				A[i] = A[i + 1];
				i = i - 1;
				key = A[i + 1];
			}
			System.out.println("" + key);
		}
	}

thiagomiranda3 29 de mai. de 2015

Também estou precisando de uma ajuda para entender a notação do pseudocódigo do livro de Algorítmos do Cormem. Veja esse exemplo de Rotação à Esquerda de uma árvore Rubro Negra.

LEFT-ROTATE(T,x)
    y <- direita[x]
    direita[x] <- esquerda[y]
    p[esquerda[y]] <- x
    p[y] <- p[x]
    if p[x] = nil[T]
        then raiz[T] <- y
        else if x = esquerda[p[x]]
            then esquerda[p[x]] <- y
            else direita[p[x]] <- y
        esquerda[y] <- x
        p[x] <- y

Pelo pouco que eu entendi, direita[x] seria como o x->direita em C ou x.direita em java. No entanto, p[esquerda[y]] ou esquerda[p[x]] não fazem sentido pra mim, assim como algumas outras partes onde ele faz essa salada com variáveis e colchetes.

Abraços

Criado 26 de outubro de 2010

Ultima resposta 29 de mai. de 2015

Respostas 11

Participantes 4

11 Respostas

Topicos relacionados