Continuando a nossa série sobre algoritmos de ordenação, apresentamos neste artigo o funcionamento do insertsort e um exemplo de implementação em Python.
O insertsort
Um dos métodos mais naturais que uma pessoa pode pensar para ordenar esse vetor é o insertsort. Geralmente fazemos insertsort mesmo sem perceber no dia-a-dia, quase que instintivamente. :)
Imagine que você tivesse um bolo de cartas na sua mão e quisesse ordená-las. Você provavelmente vai pensar em ir procurando a menor carta desse bolo desordenado de cartas e ir separando em um outro bolo ordenado de cartas, até que o bolo desordenado esvaziasse.
O insertsort funciona exatamente assim, mas, para uma melhor performance, ele coloca o bolo de cartas ordenado na frente do bolo de cartas desordenado, assim ele aproveita o mesmo bolo (no caso, o vetor).
Uma parte do vetor, que começa no início dele, vai ficando ordenada conforme você executa o algoritmo, e o tamanho dessa parte do vetor cresce cada vez mais, enquanto a parte desordenada diminui, até acabar.
Para facilitar a implementação, usaremos uma variante do insertsort que funciona da seguinte maneira: procuramos o menor elemento da parte desordenada do vetor e o trocamos com o primeiro elemento dessa parte desordenada. Após esse procedimento, esse elemento passará a integrar a parte ordenada.
Tomemos novamente o nosso vetor de exemplo: [4,5,2,1,3,7,5].
ordenado desordenado
_____|_____ _____|_____
/ \ / \
[ 4,5,2,1,3,7,5]
[1, 5,2,4,3,7,5]
[1,2, 5,4,3,7,5]
[1,2,3, 4,5,7,5]
[1,2,3,4, 5,7,5]
[1,2,3,4,5, 7,5]
[1,2,3,4,5,5, 7]
[1,2,3,4,5,5,5,7 ]
No exemplo a seguir, i indica o índice da primeira posição da parte desordenada do vetor, e j é um índice auxiliar para achar o menor elemento da parte desordenada.
def isort(a):
for i in range(len(a)):
min = a[i]
k = i
for j in range(i + 1, len(a)):
if min > a[j]:
min = a[j]
k = j
t = a[k]
a[k] = a[i]
a[i] = t
a = [4,5,2,1,3,7,5]
print repr(a)
isort(a)
print repr(a)
Não perca na segunda-feira o próximo artigo da série, sobre o mergesort!
