Inserção Ordenada


next up previous contents
Next: Remoção Up: Algoritmos de Inserção Previous: Inserção no Fim

Inserção Ordenada

Neste algoritmo o valor é inserido de tal modo que a tabela continue ordenada. Isso é conseguido em três passos:

  1. É procurada a posição em que o valor deverá ficar (corresponde a procurar a primeira posição da tabela que tem um valor maior do que o que queremos colocar na tabela).
  2. Todos os valores, a partir deste, são avançados uma posição para permitir colocar o valor a inserir.
  3. O valor é colocado na posição encontrada em 1.

O algoritmo é:

 

Este algoritmo utiliza as seguintes funções auxiliares (supondo que a tabela está ordenada por Classificação: campo CLASS):

 

 

Note-se que na função procura_pos a condição:

(list.CARROS[i].CLASS<elem.CLASS)(ilist.TOTAL)
deixa o valor da variável i, passar para além do fim da tabela, o que poderia originar uma situação de erro: uma tentativa de aceder a uma posição inexistente da tabela. No entanto, como se trata do fim lógico da tabelagif e a função só é invocada se houver espaço para mais elementos (ver algoritmo 6.2), nunca acontecerá uma situação em que o valor da variável i seja um índice inválido de list.CARROS.


Jose Franscisco Creissac Campos
Wed Jan 31 22:03:31 MET 1996