Modificação de listas

#Modificação-de-listas

Quando se implementa algoritmos que produzem estruturas de tipos mutáveis deve-se começar por decidir se se pretende:

  • construir novas estruturas em cada passo (i.e. de forma imutável como em programação funcional); ou
  • alterar incrementalmente uma mesma estrutura, tomando partido da mutabilidade, como é típico da programação imperativa

Vamos ilustrar ambas as abordagens com uma função de inserção numa lista ordenada. A primeira versão, funcional, constroi recursivamente uma nova lista. A segunda versão altera "in place" a lista recebida (será necessário adicionar-lhe explicitamente um elemento para criar espaço para o novo elemento a inserir).

Algoritmos de ordenação - implementação imperativa (com mutabilidade)

#Algoritmos-de-ordenação---implementação-imperativa-(com-mutabilidade)

Insertion Sort

#Insertion-Sort

Vemos o array como tendo uma parte já ordenada, no início, seguindo-se elementos ainda não ordenados. Em cada passo do algoritmo insere-se mais um elemento na parte já ordenada.

40, 20, 10, 30, 60, 0, 80

20, 40, 10, 30, 60, 0, 80

10, 20, 40, 30, 60, 0, 80

10, 20, 30, 40, 60, 0, 80

10, 20, 30, 40, 60, 0, 80

0, 10, 20, 30, 40, 60, 80

0, 10, 20, 30, 40, 60, 80

Mergesort

#Mergesort

Comece por escrever uma função de fusão de listas/arrays ordenados. Deve receber um array comportar-se da seguinte forma:

u = 0, 10, 20, 30, 40, 60, 80, 5, 8, 31, 100

A chamada merge (u, 0, 6, len(u)-1)

Deve produzir como resultado:

0, 5, 8, 10, 20, 30, 31, 40, 60, 80, 100

Em seguida implemente o algoritmo mergesort, na sua versão inplace, alterando directamente o array recebido.

A ideia é partir a sequência em dois segmentos de igual comprimento, e em seguida ordenar recursivamente cada um. É por isso aquilo a que se chama um algoritmo baseado na estratégia de divisão e conquista.

Não se esqueça dos casos de paragem, e de considerar que o comprimento do array pode ser ímpar.