Ordenar os elementos de
uma lista é um problema que surge em muitos contextos, por exemplo, para
produzir uma lista telefônica é necessário colocar em ordem alfabética os
nomes.
Suponha que temos uma
lista de elementos de um conjunto, além disso, suponha que temos uma maneira de
ordenar os elementos do conjunto. Ordenar é colocar esses elementos em uma
lista na qual eles aparecem em ordem crescente, por exemplo, ordenar a lista 7,
2, 1, 4, 5, 9; produz a lista 1, 2, 4, 5, 7, 9. Ordenar a lista d, h, e, a, f;
produz a lista a, e, d, f, h.
A seguir vamos introduzir
os algoritmos de ordenação bubblesorte o insertionsort.
O bubblesort (ordenação
por flutuação) é um dos algoritmos de ordenação mais simples, mas não um dos
mais eficientes. Ele coloca uma lista em ordem crescente para comparação de
elementos adjacentes, mudando-os se eles estiverem na ordem errada, para isso,
trocamos um elemento maior por um menos se estiverem em sequência, começando no
início da lista e passando por toda ela. Continuamos esse processo até que
esteja completa.
Exemplo
3:
Ordenar
3, 2, 4, 1, 5
Como 3 > 2 troque o 3
pelo 2, reproduzindo a lista 2, 3, 4, 1, 5;
como 3 < 4, continue a comparação dos próximos elementos 4 e 1. Como
4 > 1, troque 1 pelo 4, reproduzindo a lista 2, 3, 1, 4, 5. Como 4 < 5, o
primeiro passo está completo.
O segundo passo começa
pela comparação entre 2 e 3. Como esses dois estão na ordem correta, 3 e 1 são
comparados, como 3 > 1, eles são trocados. Como 3 < 4 eles estão na ordem
certa.
Terceiro passo começa na
comparação entre 2 e 1. Como 2 > 1, produzindo 1, 2, 3, 4, 5.
Quarto passo consiste na
comparação entre todos os números para verificar se estão corretos.
Ou melhor, exemplificando
passo a passo na ordem a seguir:
Primeiro passo:3 2 4 1 5
2 3 4 1 5
2 3 4 1 5
2 3 1 4 5
2 3 1 4 5
Segundo passo:2 3 1 4 5
2 3 1 4 5
2 1 3 4 5
2 1 3 4 5
Terceiro passo:2 1 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
O insertionsort (ordenação
por inserção) é um algoritmo de ordenação simples, mas, geralmente não é mais o
eficiente. Para ordenar uma lista com n elementos, o insertionsort começa com o
segundo elemento. Ele compara o segundo com o primeiro elemento e o coloca
antes do primeiro elemento se ele não exceder o primeiro elemento, depois, do
primeiro elemento se ele o exceder. Neste ponto, os dois primeiros elementos
estão na ordem correta. O terceiro elemento é comparado com o primeiro, e se
for maior que o primeiro é comparado com o segundo, ele é colocado na posição
correta, entre os primeiros três elementos.
Exemplo
4:
Use o insertionsort para
colocar os elementos da lista 3, 2, 4, 1, 5 em ordem crescente.
Comparar 3 com 2. Como 3
> 2, coloca 2 na primeira posição, reproduzindo a lista 2, 3, 4, 1, 5.
Depois compara 4 > 3. Como 4 > 3, 4 é colocado na terceira posição, a
lista fica 2, 3, 4, 1, 5. Depois encontramos o lugar certo para o quarto
elemento 1, entre os elementos já ordenados 2, 3, 4. Como 1 < 2, obtemos a
lista 1, 2, 3, 4, 5. Como 5 > 4, 5 é posto no final da lista.
Algoritmo de Ordenação