Inserindo elementos em uma sequência ordenada

Neste post, vamos descrever indutivamente um algoritmo para inserir um elemento em uma sequência ordenada. Utilizaremos a linguagem Haskell, e em posts posteriores apresentaremos implementações em Python e Scala.

Descrição indutiva:

• Caso Base: Inserir um elemento em uma sequência vazia é trivial.
• Hipótese de Indução: Vamos assumir que sabemos como inserir um elemento em uma sequência com n-1 elementos.
• Caso Geral: Simples, basta verificar se o elemento que desejamos inserir é maior ou menor que o primeiro elemento da lista, caso seja maior, entregamos o elemento e o restante da lista para a hipótese de indução, caso seja menor que o primeiro elemento, basta colocá-lo no início da lista ordenada.

A implementação em Haskell segue exatamente a descrição indutiva apresentada acima.

• Implementação em Haskell

insert :: [Int] -> Int -> [Int]
insert [] a = [a]
insert (x:xs) a 
  | (a < x)   = a:(x:xs)
  | otherwise = x:(insert xs a)

Como podemos perceber, utilizar uma linguagem funcional ajuda no processo de abstração e resolução dos problemas. Inductioncode disponibilizará em breve um editorial que fará um comparativo entre os paradigmas funcional e imperativo.