CENTRO UNIVERSITÁRIO DO PLANALTO
CENTRAL APARECIDO DOS SANTOS - UNICEPLAC
ESTRUTURA DE DADOS - ENGENHARIA DE SOFTWARE
3º PERÍODO - NOTURNO
Insertion Sort e Bubble Sort
Gama/DF
2024
CENTRO UNIVERSITÁRIO DO PLANALTO
CENTRAL APARECIDO DOS SANTOS - UNICEPLAC
ESTRUTURA DE DADOS - ENGENHARIA DE SOFTWARE
3º PERÍODO - NOTURNO
ALUNO: JOÃO PEDRO SANTOS OLIVEIRA SOUZA
Gama/DF
2024
INSERTION SORT
Existem muitos modos diferentes de ordenar. Conforme a ordenação por seleção é
executada, o subarray no começo do array é ordenado, mas o subarray no final não. A ordenação
por seleção (selection sort) escaneia o subarray não ordenado em busca do próximo elemento a
ser incluído nele.
Aqui está outro modo de pensar sobre ordenação. Imagine que você está jogando cartas.
Você está com as cartas na mão, e elas estão ordenadas. Você recebe exatamente uma nova
carta. Você deve colocá-la na posição correta, de forma que as cartas na sua mão continuem
ordenadas. Na ordenação por seleção, cada elemento que você adiciona ao subarray ordenado
não é menor que os elementos que já estão no subarray ordenado. Mas no nosso exemplo de
cartas, a nova carta pode ser menor que algumas das cartas que você já está segurando, e então
você as examina, comparando a nova carta com todas as cartas na sua mão, até encontrar a
posição para colocá-la. Você insere a nova carta na posição correta, e, novamente, sua mão é
composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo
procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.
Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array,
começando com o índice 1. Cada nova posição é como a nova carta que você recebeu, e você
precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição.
Em termos de arrays, imagine que o subarray do índice 0 até o índice já está ordenado, e
queremos inserir o elemento atualmente no índice 6 neste subarray ordenado, de forma que o
subarray do índice 0 até o índice 6 fique ordenado. É assim que começamos:
E é assim que o subarray deve se parecer quando tivermos terminado:
Para inserir o elemento da posição 6 no subarray à sua esquerda, o comparamos
repetidamente com os elementos à sua esquerda, indo da direita para a esquerda. Vamos chamar
o elemento na posição 6 de chave.
Sempre que descobrimos que a chave é menor que um elemento à sua esquerda,
deslocamos esse elemento uma posição para a direita, já que sabemos que a chave deverá ficar
à esquerda desse elemento.
Vamos precisar de duas coisas para fazer essa ideia funcionar: precisamos ter uma
operação de deslocamento que mova um elemento uma posição à direita, e precisamos salvar o
valor da chave em uma posição separada (de modo que ela não seja sobrescrita pelo elemento
imediatamente à sua esquerda). Em nosso exemplo, vamos colocar o elemento no índice 6 em
uma variável chamada key:
Agora, comparamos key com o elemento na posição 5. Descobrimos que key (5) é menor
que o elemento na posição 5 (13), então deslocamos esse elemento para a posição 6:
Note que a operação deslocamento simplesmente copia o elemento uma posição para a
direita. Agora, comparamos key com o elemento na posição 4. Descobrimos que key (5) é menor
que o elemento na posição 4 (10), e deslocamos esse elemento:
Depois, comparamos key com o elemento na posição 3 e deslocamos esse elemento:
O mesmo acontece com o elemento na posição 2:
Agora, chegamos ao elemento na posição 1, que tem um valor de 3. Este elemento é
menor do que key, então não precisamos deslocá-lo. Em vez disso, colocamos key na posição
imediatamente à direita desse elemento (ou seja, na posição 2), cujo elemento foi mais
recentemente deslocado para a direita. O resultado é que o subarray do índice 0 até o índice 6 foi
ordenado:
A ordenação por inserção insere um elemento no subarray ordenado à sua esquerda.
Inicialmente, podemos dizer que o subarray que contém apenas o índice 0 está ordenado, já que
ele contém apenas um elemento, e como pode um único elemento não estar ordenado em
relação a si mesmo? Ele deve estar ordenado. Vamos trabalhar em um exemplo. Aqui está nosso
array inicial:
Como o subarray que contém apenas o índice 0 é nosso subarray ordenado inicial, a
primeira chave está no índice 1. (Vamos mostrar o subarray ordenado em vermelho, a chave em
amarelo, e a parte do array com que ainda temos que lidar em azul). Inserimos a chave no
subarray ordenado à sua esquerda:
Agora, o subarray ordenado vai do índice 0 até o índice 1, e a nova chave está no índice 2.
O inserimos então no subarray ordenado à sua esquerda:
Continuamos com esse processo, considerando cada elemento do array, um por vez, como
a chave e o inserimos no subarray ordenado à sua esquerda:
Depois que inserimos o elemento mais à direita no array, teremos ordenado todo o array:
Algumas situações que surgem em nosso exemplo merecem ser estudadas um pouco
mais: quando a chave sendo inserida for menor do que todos os elementos à sua esquerda
(como quando inserimos as chaves 2 e 3), e quando é maior ou igual a todos os elementos à sua
esquerda (como quando inserimos a chave 13). No primeiro caso, todos os elementos no
subarray à esquerda da chave se deslocam uma posição para a direita, e devemos parar quando
chegarmos à extremidade esquerda do array. No último caso, na primeira vez que comparamos a
chave com um elemento à sua esquerda, descobrimos que a chave já está na sua posição
correta em relação a todos os elementos à sua esquerda. Nenhum elemento é deslocado e a
chave retorna à posição em que começou.
Inserir um valor em um subarray ordenado
A parte principal da ordenação por inserção é abrir espaço em um array para colocar o
valor atual, que é armazenado na variável key. Como vimos antes, percorremos o subarray à
esquerda da posição inicial de key, da direita para a esquerda, deslocando cada elemento que
seja maior do que key uma posição para a direita. Quando encontramos um elemento que seja
menor do que key, ou igual a key, paramos de deslocar e copiamos key para a posição vaga
imediatamente à direita deste elemento. (É claro, a posição não está realmente vazia, seu
elemento foi deslocado para a direita). Este diagrama mostra a ideia:
BUBBLE SORT
A classificação por bolha, ou Bubble Sort, é um algoritmo básico para organizar uma
sequência de números ou outros elementos na ordem correta. O método funciona examinando
cada conjunto de elementos adjacentes na string, da esquerda para a direita, trocando suas
posições se estiverem fora de ordem. O algoritmo então repete esse processo até que possa
percorrer toda a string e não encontrar dois elementos que precisem ser trocados.
Bubble Sort é um algoritmo de classificação comumente usado em ciência da computação.
O Bubble Sort baseia-se na ideia de comparar repetidamente pares de elementos adjacentes e,
em seguida, trocar as suas posições se existirem na ordem errada.
Algoritmo de Classificação de bolhas:
1. Em uma matriz não classificada de 5 elementos, comece com os dois primeiros elementos
e classifique-os em ordem crescente. (Compare o elemento para verificar qual é o maior).
2. Compare o segundo e o terceiro elemento para verificar qual é o maior e classifique-os em
ordem crescente.
3. Compare o terceiro e o quarto elemento para verificar qual é o maior e classifique-os em
ordem crescente.
4. Compare o quarto e o quinto elemento para verificar qual é o maior e classifique-os em
ordem crescente.
5. Repita as etapas 1–5 até que não sejam necessárias mais trocas.
Abaixo está uma imagem de uma matriz que precisa ser classificada. Usaremos o
algoritmo de classificação de bolhas para classificar esta matriz:
Provavelmente, o algoritmo de classificação mais famoso é a classificação por bolha. Vale
ressaltar que existem milhares de mutações a partir dele, e é usado principalmente para fins
educacionais — como o primeiro algoritmo que você aprende.
Então, qual é o tipo de bolha? Imagine que estamos pegando os dois primeiros elementos.
Se o primeiro elemento for maior que o segundo, nós os trocamos. Agora pegamos o segundo e o
terceiro elementos — repetimos. Assim, no final, o maior elemento será o último membro da
matriz. Agora, repetimos a operação para os primeiros n-1 números, portanto n-2 e assim por
diante.
Qual é a aparência de um tipo de bolha?
Se uma pessoa programadora ou analista quisesse organizar uma série de números em
ordem crescente, a abordagem de classificação por bolha seria semelhante ao exemplo ilustrado
aqui.
O algoritmo revistaria dois itens por vez, reorganizaria aqueles que ainda não estavam em
ordem crescente, da esquerda para a direita, e então continuaria a percorrer toda a sequência até
completar uma passagem sem trocar nenhum número.
Como e por que os programas de computadores usam Bubble Sort?
Os programadores de computador usam a classificação por bolha para organizar uma
sequência de números na ordem correta. Por ser o tipo mais simples de algoritmo de
classificação, a classificação por bolhas não é muito usada na ciência da computação do mundo
real. Seus usos mais comuns para pessoas programadoras incluem o seguinte:
1. Uma maneira de aprender a classificação básica
A classificação por bolha funciona como um método para ensinar novos programadores e
programadoras a classificar conjuntos de dados porque o algoritmo é simples de entender e
implementar.
2. Uma metodologia para classificar pequenos conjuntos de dados
Por ter que circular repetidamente por todo o conjunto de elementos, comparando apenas
dois itens adjacentes por vez, a classificação por bolha não é ideal para conjuntos de dados mais
massivos. Mas pode funcionar bem ao classificar apenas um pequeno número de elementos.
3. Uma metodologia de classificação para conjuntos de dados que, em sua maioria, já
estão em ordem
Finalmente, alguns cientistas da computação e analistas de dados usam o algoritmo como
uma verificação final para conjuntos de dados que eles acreditam já estarem em ordem quase
classificada.
Como o Bubble Sort Funciona?
Pegamos um array não classificado como nosso exemplo. A classificação por bolha leva Ο
(n 2 ) tempo, então estamos mantendo-a curta e precisa.
A classificação por bolha começa com os dois primeiros elementos, comparando-os para
verificar qual é o maior.
Nesse caso, o valor 33 é maior que 14, portanto, já está nos locais classificados. Em
seguida, comparamos 33 com 27.
Descobrimos que 27 é menor que 33 e esses dois valores devem ser trocados.
A nova matriz deve ser semelhante a esta:
Em seguida, comparamos 33 e 35. Descobrimos que ambos já estão em posições
ordenadas.
Em seguida, passamos para os próximos dois valores, 35 e 10.
Sabemos então que 10 é menor que 35. Portanto, eles não são classificados.
Trocamos esses valores. Descobrimos que atingimos o final da matriz. Após uma iteração,
o array deve ficar assim:
Para ser mais preciso, agora estamos mostrando como um array deve ficar após cada
iteração. Após a segunda iteração, deve ficar assim:
Observe que após cada iteração, pelo menos um valor se move no final.
E quando não há necessidade de troca, o bubble sort aprende que um array está
completamente classificado.
Exemplo de uso do Bubble Sort em python:
A lista não ordenada é: [5, 3, 8, 6, 7, 2]
A lista ordenada é: [2, 3, 5, 6, 7, 8]
Explicação:
No código acima, definimos uma função bubble_sort () que recebe list1 como um
argumento.
Dentro da função, definimos dois loops for — primeiro o loop for itera a lista completa e o
segundo loop for itera a lista e compara os dois elementos em cada iteração do loop externo.
O loop for será encerrado quando atingir o final.
Definimos a condição no loop for interno; se um primeiro valor de índice for maior que o
segundo valor de índice, troque suas posições entre si.
Chamamos a função e passamos uma lista; iterou e retornou a lista classificada.
Quais as Vantagens de usar o Bubble Sort?
Uma das principais vantagens de um tipo de bolha é que ele é um algoritmo muito simples
de ser descrito para um computador. Na verdade, há apenas uma tarefa a ser executada
(compare dois valores e, se necessário, troque-os). Isso o torna um programa de computador
muito pequeno e simples.
Quais as Desvantagens de usar o Bubble Sort?
Bubble Sort é um dos algoritmos mais amplamente discutidos, simplesmente por causa de
sua falta de eficiência para classificar matrizes. Se um array já estiver classificado, Bubble Sort
passará pelo array apenas uma vez (usando o conceito dois abaixo), no entanto, o pior cenário é
um tempo de execução de O (N²), que é extremamente ineficiente.
REFERÊNCIAS
KHAN ACADEMY. Insertion sort: CURSO: COMPUTER SCIENCE THEORY. [S. l.], 2017.
Disponível em: [Link]
sort/a/insertion-sort. Acesso em: 31 maio 2024.
BUBBLE Sort: o que é e como usar? Exemplos práticos!. [S. l.], 20 dez. 2022. Disponível em:
[Link] Acesso em: 31 maio 2024.