Dúvida Ordenação Inserção

mendesjao · 2 de outubro de 2013

Boa Noite Galera, estou com um problema nesse código em Delphi Console, pelo que li desse método Inserção, está certo mais o primeiro valor do Vetor não está sendo ordenado. Gostaria de saber se alguém poderia me ajudar.

Desde já Agradeço a todos que ajudarem.

Var
i,j,eleito,aux,achou,posi : integer;
Vetor : array [0..7] of integer;

begin
for i := 0 to 7 do
begin
Writeln('Insira o Valor ', i, ':');
Readln(Vetor[i]);
end;

for i := 1 to 7 do
begin
eleito := vetor[i];
j := 1;
achou := 0;

while (j < i) and (achou = 0) do
begin
if vetor[j] > eleito then
begin
achou := 1;
posi := j;
end
else
begin
j := j + 1;
end;
end;
if achou = 1 then
begin
for j := i downto posi do
begin
vetor[j] := vetor[j - 1];
end;
vetor[posi] := eleito;
end;
end;

Writeln('-------------------------------------------------');
Writeln('Vetor Ordenado por Metodo Inserção:');
for i:= 0 to 7 do
begin
Writeln('Indíce [',i+1,'] = ' + INTTOSTR(vetor[i]));
end;
Writeln('-------------------------------------------------');
Readln ;
end.

Diron Donadel · 2 de outubro de 2013

Boa Noite Galera, estou com um problema nesse código em Delphi Console, pelo que li desse método Inserção, está certo mais o primeiro valor do Vetor não está sendo ordenado. Gostaria de saber se alguém poderia me ajudar.

Desde já Agradeço a todos que ajudarem.

i,j,eleito,aux,achou,posi : integer;
Vetor : array [0..7] of integer;

begin
for i := 0 to 7 do
begin
Writeln('Insira o Valor ', i, ':');
Readln(Vetor[i]);
end;

for i := 1 to 7 do
begin
eleito := vetor[i];
j := 1;
achou := 0;

while (j < i) and (achou = 0) do
begin
if vetor[j] > eleito then
begin
achou := 1;
posi := j;
end
else
begin
j := j + 1;
end;
end;
if achou = 1 then
begin
for j := i downto posi do
begin
vetor[j] := vetor[j - 1];
end;
vetor[posi] := eleito;
end;
end;

Writeln('-------------------------------------------------');
Writeln('Vetor Ordenado por Metodo Inserção:');
for i:= 0 to 7 do
begin
Writeln('Indíce [',i+1,'] = ' + INTTOSTR(vetor[i]));
end;
Writeln('-------------------------------------------------');
Readln ;
end.
Var

cara não é de certeza, mais se não me engano, o vetor começa da posição 1 não da posição 0

teste assim acredito que irá funcionar

LNW · 2 de outubro de 2013

Olá,

Boa Noite Galera, estou com um problema nesse código em Delphi Console, pelo que li desse método Inserção, está certo mais o primeiro valor do Vetor não está sendo ordenado. Gostaria de saber se alguém poderia me ajudar.
Desde já Agradeço a todos que ajudarem.
(...)
begin
for i := 0 to 7 do
begin
Writeln('Insira o Valor ', i, ':');
Readln(Vetor[i]);
end;

for i := 1 to 7 do
begin
eleito := vetor[i];
j := 1;
achou := 0;
(...)[/quote]

Logo no início daquele segundo FOR, atribua [B]0[/B] (zero) a [B]j[/B]:

[code]j := 0;
Teste aí..

[]'s

LNW

mendesjao · 2 de outubro de 2013

Olá,
Logo no início daquele segundo FOR, atribua 0 (zero) a j:
j := 0;
Teste aí..

[]'s

LNW

valeu cara, deu certo aqui.

Muito Obrigado.

Simon Viegas · 2 de outubro de 2013

Olá a todos...

cara não é de certeza, mais se não me engano, o vetor começa da posição 1 não da posição 0
teste assim acredito que irá funcionar

Creio que seja o contrário, geralmente, quando não é definido, os vetores começam da posição 0... mas no caso, como essa declaração no Delphi/Pascal usa as duas coordenadas, o início e fim ficam estipulados pelo programador. No caso ele estipulou de 0 a 7 (8 posições).

PS: Poderia ser também por exemplo de 11 a 18, de 'b' a 'j' etc... ou seja, a faixa é "simbólica" e "flexível".

valeu cara, deu certo aqui.
Muito Obrigado.

Então beleza..

Obs.: Onde você conseguiu esse código? Você que fez baseado em alguma definição ou se baseou em outro código?

O interessante é que esse código NÃO ESTÁ DE ACORDO COM O ALGORITMO PADRÃO (veja os vídeos do YouTube por exemplo), ou seja, pelo que eu consegui encontrar na internet, o processo do Insert Sort é feito DESLOCANDO O VALOR ATÉ A SUA POSIÇÃO, mas neste, o valor está SENDO INSERIDO NA POSIÇÃO. São coisas diferentes..

No padrão = Vai deslocando o valor para esquerda até ser maior;

No seu = Deslocar todo os necessários para direita e insere o valor no lugar certo

Na minha opinião esse código está mais certo do que os outros... já que o nome é INSERT e não "MOVE". Gostaria de debater sobre isso se possível

Como me interessei, tentei entender o processo usado e fiz algumas modificações e comentários baseados no seu código..

Veja:

uses
  SysUtils; //precisou para rodar no FreePascal (carrega
var
  i,j,
  eleito,
  aux,
  posi  :integer;
  achou :boolean;
  vetor :array [0..7] of integer;
BEGIN
//LEITURA DOS DADOS
for i:=0 to 7 do
  begin
  writeln('Insira o Valor ',i,':');
  readln(Vetor[i]);
  end;


//ORDENAÇÃO MÉTODO "Insertion sort"
for i:=1 to 7 do //da segunda até a última posição
  begin
  eleito:=vetor[i]; //valor a ser inserida na coluna já ordenada
  achou:=false; //marca como não precisando deslocar
  j:=0; //primeria posição - auxiliar que vai percorrer a coluna ordenada

  //Verificar se precisa deslocar a coluna já ordenada para "encaixar" o eleito
  while (j<i) and (not achou) do //enquanto estive na coluna ordenada e ainda não encontrado
    begin
    if vetor[j]<=eleito then //se ainda não precisa deslocar
      j:=j+1  //vai para o próximo
    else
      begin
      achou:=true; //marca que precisa deslocar (vai interromper o loop)
      posi:=j; //marcar até onde precisa deslocar
      end
    end;

  if achou then //se precisa deslocar
    begin
    //abre caminho para o novo dado
    for j:=i downto posi do //da última posição da coluna ordenada até a posição que precisa ordenar
      vetor[j]:=vetor[j-1]; //desloca da esquerda para direita

    vetor[posi]:=eleito; //a posição passa a ter o valor "eleito" (inserindo na posição certa)
    end;
  end;

//exibe o resultado
writeln('-------------------------------------------------');
writeln('Vetor Ordenado por Metodo Inserção:');
for i:= 0 to 7 do
  writeln('Indíce [',i+1,'] = '+IntToStr(vetor[i]));
writeln('-------------------------------------------------');
readln;
END.

Acho que seria mais ou menos isso...

Comentários?

Obs: Fiz um código ainda mais simples (que mesclo a verificação com as trocas em um loop só - mas prefiro inicialmente nos atentar a esse código por enquanto).

No aguardo...

mendesjao · 3 de outubro de 2013

Fala Simon, esse códiigo eu começei fazer e pedi umas dicas pro meu Prof. que me da aula de Lab. Programação II, faço 2º Período SI.

Ele me deu umas dicas e pelo que entendi eu passei para o código, só está dando errado no trecho ali que j := 1, mas era 0.

Sim, pelo que você fez os comentários do Código seria isso mesmo. Esse método de ordenação foi um dos mais chatinhos que achei, pois muitos falam várias coisas. Mas teu código fico muito bom.

Simon Viegas · 3 de outubro de 2013

Fala Simon, esse códiigo eu começei fazer e pedi umas dicas pro meu Prof. que me da aula de Lab. Programação II, faço 2º Período SI.
Ele me deu umas dicas e pelo que entendi eu passei para o código, só está dando errado no trecho ali que j := 1, mas era 0.

Sim, pelo que você fez os comentários do Código seria isso mesmo. Esse método de ordenação foi um dos mais chatinhos que achei, pois muitos falam várias coisas. Mas teu código fico muito bom.

Então, pelo que eu entendi, seu algoritmo está seguindo como o exemplo desta imagem:

Font:Wikipedia

Obs.: O processo não é literalmente igual o da imagem, já que em nível de computação o conceito de "mover" é um pouco diferente do mundo real, ou seja, quando se quer passar de uma "casa" para "outra", na verdade o que ocorre é uma "cópia do valor da posição antiga, em cima da posição nova", e daí "apaga a posição antiga". O mesmo ocorre com o eleito, ele não é deslocado, apenas terá uma cópia do valor em outro lugar...

Obs2: No seu código, como é fácil observar, ele não apaga a antiga ao deslocar, simplesmente vai copiando da atual para direita (quase sempre vai existir o mesmo valor em duas casas ), até que a posição atual (que não vai mais ser descolada) seja a posição que vai ser "inserida o eleito". Tá dando para entender?

Mas no próprio Wikipedia, tem esse pseudocódigo:

FUNCAO INSERTION_SORT (A[], tamanho)

        VARIAVEIS
        var i, j, elemento;


        PARA j <- 1 ATÉ tamanho - 1 FAÇA
                elemento <- A[j];
                i <- j – 1;

                ENQUANTO ((i >= 0) E (A[i] > elemento)) FAÇA
          [COLOR="Red"]posição atual do elemento-->[/COLOR]  A[i+1] <- A[i]
                        A[i] <- elemento    [COLOR="Red"]<--salvo na nova posição[/COLOR]
                        i <- i–1
                FIM_ENQUANTO

        FIM_PARA

FIM

Que não está de acordo com a imagem!!!

Nestes código, a cada loop do ENQUANTO o elemento (análogo ao eleito do seu código) está sendo trocado com o vizinho, ou seja, ele está funcionando como uma "bolha", conceito usado do Bubble Sort.

Veja por exemplo alguns vídeos do YouTube... A maioria (senão todos), esta utilizando como o pseudocódigo.

RESUMIDAMENTE

Estaria você certo (eu me incluo nesta vertente) e resto do mundo errado????

PS: acharia interessante se puder trazer mais ou menos a opinião do seu professor e até quem sabe dos seus colegas...

No aguardo.

LNW · 4 de outubro de 2013

Salve,

Que não está de acordo com a imagem!!!
Nestes código, a cada loop do ENQUANTO o elemento (análogo ao eleito do seu código) está sendo trocado com o vizinho, ou seja, ele está funcionando como uma "bolha", conceito usado do Bubble Sort.

Confesso que de início não havia entendido essa dúvida levantada, mas acho que agora começo a imaginar o porquê dela...

O que ocorre no código do mendesjao é que ele desmembrou a parte responsável pelo deslocamento dos elementos do vetor da parte que testa pela maioridade do elemento. Observe que há um laço principal (o FOR), e dentro desse laço existem 2 laços: um para testar e marcar posição e o outro para deslocamento.

Quando ele marca a posição (do elemento que é maior):

posi := j;

corresponderia à condição de parada:

(A[i] > elemento)

do pseudocódigo. A diferença é que no pseudocódigo o deslocamento necessário já vai acontecendo. No caso dele, ele ainda precisa lançar mão de um laço exclusivo para essa tarefa.

Ambos os algoritmos deslocam os elementos.

Fiz uma implementação rápida para demonstrar que o pseudocódigo gera aquela sequência da imagem (ele imprime o vetor etapa por etapa da ordenação):

program foo;
Uses CRT;
type
   TArr = Array [0..7] of Integer;

procedure impr_vetor(arr :TArr);
var
  i :Integer;
begin
  For i := 0 to 7 do
    write(arr[i], ' ');
end;

procedure Insertion_sort(var arr :TArr);
var
  i, j, elem : Integer;
begin
  For j := 1 To 8 - 1 Do
    begin
      elem := arr[j];
      i := j - 1;

      while ((i >= 0) and (arr[i] > elem)) do
        begin
          arr[i+1] := arr[i];
          arr[i] := elem;
          i := i - 1;
        end;
      impr_vetor(arr);
      writeln;
    end;
end;

var
  arr : TArr;

begin
  ClrScr;
  arr[0] := 6;
  arr[1] := 5;
  arr[2] := 3;
  arr[3] := 1;
  arr[4] := 8;
  arr[5] := 7;
  arr[6] := 2;
  arr[7] := 4;

  write('Vetor original: ');
  impr_vetor(arr);
  writeln;
  writeln;
  writeln;
  Insertion_sort(arr);

end.

Bom, não sei se consegui explicar direito...

[]'s

LNW

Simon Viegas · 4 de outubro de 2013

A diferença é que no pseudocódigo o deslocamento necessário já vai acontecendo. No caso dele, ele ainda precisa lançar mão de um laço exclusivo para essa tarefa.

Sim, existe essa diferença de separação entre os dois códigos, mas a diferença que me refiro é sobre o deslocamento em si. (são duas coisas distintas)

PS: eu inclusive comentei sobre isso em uma das postagens:

Obs: Fiz um código ainda mais simples (que mesclo a verificação com as trocas em um loop só - mas prefiro inicialmente nos atentar a esse código por enquanto).

Observe a animação... Nela o objeto é "inserido na posição certa" (daí que imagino que vem o nome do método INSERTION), sendo que antes "os valores são deslocados para direita", já que o array não tem o recurso de "intercalar" (o que teríamos por exemplo se fosse com ponteiros, correto?), logo é necessário abrir um buraco manualmente.

Já no pseudocódigo é diferente, lá ele "pega o novo valor e vai deslocando para esquerda até chegar no seu lugar". Isso eu não acho coerente... Aqui, o valor novo é que está se deslocando para chegar até o lugar certo (como uma "bolha")... e não o array que abre caminho para "inserir" no lugar certo.

O pseudo código da animação seria mais ou menos assim:

FUNÇÃO INSERTION_SORT (A[], tamanho)
        VARIÁVEIS      
                i, ,j
                eleito
        PARA I <- 1 ATÉ tamanho-1 FAÇA
                eleito <- A[i];
                j <- i-1;
                ENQUANTO ((eleito < A[j]) E (j>=0)) FAÇA
                        [B]  A[j+1]:=v[j];
                          j:=j-1;[/B]
                FIM_ENQUANTO
                [B]A[j+1] <- eleito;    [/B]            
        FIM_PARA
FIM

Ambos os algoritmos deslocam os elementos.

Isso, mas um desloca os valores já ordenados para direita, e o outro desloca o valor novo dentro dos valores ordenados...

Fiz uma implementação rápida para demonstrar que o pseudocódigo gera aquela sequência da imagem (ele imprime o vetor etapa por etapa da ordenação):

program foo;
Uses CRT;
type
   TArr = Array [0..7] of Integer;

procedure impr_vetor(arr :TArr);
var
  i :Integer;
begin
  For i := 0 to 7 do
    write(arr[i], ' ');
end;

procedure Insertion_sort(var arr :TArr);
var
  i, j, elem : Integer;
begin
  For j := 1 To 8 - 1 Do
    begin
      elem := arr[j];
      i := j - 1;

      while ((i >= 0) and (arr[i] > elem)) do
        begin
          arr[i+1] := arr[i];
          arr[i] := elem;
          i := i - 1;
        end;
      impr_vetor(arr);
      writeln;
    end;
end;

var
  arr : TArr;

begin
  ClrScr;
  arr[0] := 6;
  arr[1] := 5;
  arr[2] := 3;
  arr[3] := 1;
  arr[4] := 8;
  arr[5] := 7;
  arr[6] := 2;
  arr[7] := 4;

  write('Vetor original: ');
  impr_vetor(arr);
  writeln;
  writeln;
  writeln;
  Insertion_sort(arr);

end.

Bom, não sei se consegui explicar direito...

Se você observar, no exemplo está imprimindo após as trocas de cada valor novo, ou seja, está imprimindo após o que está sendo analisado... O que nos interessa no momento é justamente o processo de trocas... Teria que imprimir dentro do while. (verá que por exemplo, o 1 irá trocar com 6, depois trocar com 5, depois trocar com 3. Em vez de jogar o 6 no 1, jogar o 5 no 6 e o 3 no 5, daí o lugar do 3 seria ocupado pelo 1 depois.)

Os vídeos do YT seguem esse princípio do pseudocódigo, e que no meu ponto de vista está errado, e não o da imagem.

PS: pela tarde vou tentar um código demonstrando a diferença entre um e outra.

No aguardo

LNW · 4 de outubro de 2013

Olá,

Sim, agora entendi o que quis passar.

Mas só uma dúvida: de onde você tirou aquele primeiro pseudocódigo?

--EDIT--

Agora que vi, você editou o artigo na Wiki...

[]'s

LNW

Simon Viegas · 4 de outubro de 2013

Olá,
Sim, agora entendi o que quis passar.

Mas só uma dúvida: de onde você tirou aquele primeiro pseudocódigo que deixa A[i+1] <- A dentro do ENQUANTO?

[]'s

LNW

Vou tentar já deixar explicar a ideia geral...

                ENQUANTO ((eleito < A[i]) E (i>=0)) FAÇA
                          A[i+1]:=v[i];
                          i:=i-1;
                FIM_ENQUANTO
                A[i+1] <- eleito;

Neste caso, a cada loop, o i estará armazenando um valor que é correspondente a suposta posição de onde o eleito vai ser armazenado. Daí ele faz o deslocamento da posição i para i+1 lá em

A[i+1] <- A[i]

. Ao atualizar com i-1, o i vai apontar para a posição anterior, logo, se a posição for maior que o elemento, então efetuará mais uma troca etc... (análogo ao que ocorre na animação). Quando o valor for maior ou igual (ou terminar a lista) ele INSERE na posição certa. Mas por que fica i+1 lá em baixo? Porque após achar o anterior, foi feito mais uma atualização (já pensando em um anterior)., logo precisa compensar...

O mesmo vale se não houver troca nenhuma, pois o i já é inicializado uma posição atrás antes do ENQUANTO.

PS: Um vetor[j]:=vetor[j-1]; terá o mesmo efeito de um vetor[j+1]:=vetor[j];, já que esse último seria o resultado de vetor[j+1]:=vetor[j-1+1];... claro que toda a estrutura terá que ser ajustada para essa diferença de "+1".

Abaixo ajustei o código de LNW para tentar demonstrar que esse código não segue o da imagem.

Código:

PROGRAM foo;
uses CRT;
type
   TArr = array [0..7] of integer;

procedure impr_vetor(arr :TArr; trocado:byte);
  var
    i :byte;
  begin
  for i := 0 to 7 do
    begin
    if (i=trocado-1) then TextColor(Yellow) //eleito
    else if (i=trocado) then TextColor(Red) //trocado
      else TextColor(White);
    write(arr[i],' ')
    end;
  end;

procedure Insertion_sort(var arr :TArr);
  var
    i, j, elem : Integer;
  begin
  For j := 1 To 8 - 1 Do
    begin
    writeln('LOOP ',j);
    elem := arr[j];
    i := j - 1;
    while ((i >= 0) and (arr[i] > elem)) do
      begin
      arr[i+1] := arr[i];
      arr[i] := elem;
      impr_vetor(arr,i+1);
      i := i - 1;
      writeln;        
      end;
    end;
  end;

var
  arr : TArr;

BEGIN
TextColor(White);
ClrScr;
arr[0] := 6;
arr[1] := 5;
arr[2] := 3;
arr[3] := 1;
arr[4] := 8;
arr[5] := 7;
arr[6] := 2;
arr[7] := 4;

write('Vetor original: ');
impr_vetor(arr,999);
TextColor(Yellow);
write('AMARELO');
TextColor(White);
write('=ELEITO');
TextColor(Red);
write('   VERMELHO');
TextColor(White);
writeln('=TROCADO');

Insertion_sort(arr);
readln;
END.

Imagem:

Ou seja, os fins são iguais (está ordenado a cada loop), mas os meios são diferente.

Se estivesse em GIF, o eleito ia "percorrendo/trocando", em vez de "caindo/inserido".

PS: dá para fazer a animação como do GIF no Pascal também, basta um pouco de paciência...

PS2: Desculpem-me todos, pois não sei se meus textos estão claros, pois eu vou tentando criar o raciocínio a medida que vou ganhando um tempinho no trabalho.

No aguardo.

LNW · 4 de outubro de 2013

Olá,

Ou seja, os fins são iguais (está ordenado a cada loop), mas os meios são diferente.
Se estivesse em GIF, o eleito ia "percorrendo/trocando", em vez de "caindo/inserido".

Ficou claro sim, Viegas. Naquele seu post anterior já havia entendido o seu ponto. A dúvida ficou sendo apenas com o pseudocódigo postado anteriormente, que depois conferi no site e já estava diferente; depois que fui ver que você havia editado o artigo..

Realmente, estava considerando o conteúdo do vetor a cada iteração do laço; pensei que estava se referindo que a ordem dos elementos dentro do vetor a cada iteração não batia com aquela sequência da imagem...

Mas sim, realmente, há uma instrução desnecessária e até dispendiosa, já que trata-se de uma operação de escrita em memória. E, claro, por definição, fica em desacordo com o algoritmo Insertion sort.

Normalmente, eu costumo acessar a versão EN dos artigos da wikipedia; Na versão inglesa (que costuma ser mais apurada), esse algoritmo encontra-se como deve ser e até bem comentado.

[]'s

LNW