Olá pessoal, tudo bem? Neste artigo apresentaremos um resumo dos algoritmos de ordenação da bolha, ordenação por seleção e ordenação por inserção. Este é um assunto que a Cesgranrio gosta muito, assim é muito provável que caia alguma questão na prova do concurso do Banco do Brasil.
Dessa forma, a ideia deste artigo é fazer um comparativo desses algoritmos, abordando os seguintes tópicos:
O método da bolha funciona percorrendo a lista, comparando elementos adjacentes (pares consecutivos) e trocando-os de posição caso não estejam em ordem. Assim, a cada iteração, o maior elemento “flutua” para a última posição, e o processo é repetido até que todos os elementos estejam na ordem correta.
Vejamos abaixo, um exemplo de ordenação da lista [8, 2, 3, 5, 1]:
Perceba que, a cada iteração, o elemento maior, dentre os não ordenados, flutua para última posição destes. Além disso, observe que foram realizadas 10 comparações e 7 trocas.
Outro ponto importante, é que no método da bolha, o número de comparações realizadas é dado pela seguinte equação:
comparações = N * (N - 1) / 2,
sendo N o número de elementos da lista.
O algoritmo de ordenação por seleção funciona selecionando o menor elemento de uma lista não ordenada e colocando-o na primeira posição. Esse processo é realizado a cada iteração, excluindo os elementos já ordenados, ou seja, sempre selecionando o menor elemento do lista remanescente, que não está ordenada, e colocando na primeira posição dela.
Vejamos, então, abaixo uma imagem com um exemplo de ordenação, considerando a lista [8, 5, 3, 2, 1]:
Observe que a cada iteração o menor elemento dentre os não ordenados é trocado pelo primeiro elemento deles. Sendo assim, algoritmo realiza, no máximo, uma troca a cada iteração, sendo isso um ponto positivo. Por outro lado, uma desvantagem deste algoritmo é que mesmo com lista já ordenada, ele compara todos os elementos da parte não ordenada por ele para descobrir o menor elemento.
O algoritmo ao todo faz 10 comparações e apenas 2 trocas, pois a partir da terceira iteração, a lista já está ordenada, não precisando realizar novas trocas de posição.
O algoritmo realiza essas comparações para encontrar o menor elemento. Na primeira iteração, o algoritmo compara os cinco elementos, ou seja, realiza 4 comparações. Em seguida, na segunda iteração, como o primeiro elemento já está ordenado, o algoritmo só compara os quatro elementos restantes, realizando três comparações.
Enfim, o número de comparações é 4 + 3 + 2 + 1 = 10.
Assim como no método da bolha, a equação C = n * (n-1) / 2 encontra o número de comparações realizadas pela ordenação por seleção.
O algoritmo de ordenação por inserção funciona dividindo a lista em duas partes, uma com elementos já ordenados e a outra com elementos ainda não ordenados. Assim, a cada iteração do algoritmo, o primeiro elemento da parte não ordenada é inserido em sua posição correta na parte ordenada. Ao final das iterações, a lista estará ordenada.
Observe que inicialmente o algoritmo considera o elemento 8 como ordenado. Em seguida, o algoritmo seleciona sempre o primeiro elemento dentre os não ordenados e o insere na posição correta dentre os ordenados. Assim, considerando a parte ordenada [2, 8] e o elemento 3 selecionado, este será inserido entre os dois valores, resultando em [2, 3, 8]. Ao final, a lista estará ordenada, mas o algoritmo realiza muitas movimentações e comparações.
O número de comparações e movimentações realizadas pelo algoritmo varia de acordo com o quanto a lista está ordenada. Por exemplo, para listas pouco ordenadas, são realizadas muitas comparações e movimentações. Por outro lado, para listas quase ordenadas, são necessárias poucas comparações e movimentações.
Aqui está um quadro comparativo da complexidade dos algoritmos de ordenação bolha, por seleção e por inserção nos casos pior, médio e melhor:
| Algoritmo de Ordenação | Pior Caso | Caso Médio | Melhor Caso |
| Bolha | O(n^2) | O(n^2) | O(n^2)** |
| Seleção | O(n^2) | O(n^2) | O(n^2) |
| Inserção | O(n^2) | O(n^2) | O(n) |
** Uma variação do método bolha com condição de parada tem complexidade linear, ou seja, N, no melhor caso, isto é, quando a lista está ordenada. Neste caso, o algoritmo apenas percorre a lista uma vez, e estando ela ordenada, finaliza a execução.
Em resumo, temos:
Dentre os três algoritmos apresentados neste artigo, o menos eficiente é o da bolha. Embora ele seja simples de entender, na prática ele é lento, quando comparado aos demais algoritmos de mesma complexidade, pois apresenta um número muito grande de movimentações e comparações.
Por outro lado, o algoritmo de ordenação por seleção, apresenta quantidade menores de movimentos, sendo vantajoso seu uso para ordenação de estruturas complexas. Então, uma desvantagem é que o número de comparações desse algoritmo é igual para qualquer lista, mesmo as que estejam previamente ordenadas.
Enfim, o algoritmo de ordenação por inserção apresenta o melhor desempenho na prática, se comparado com os demais aqui estudados. Entretanto, ressaltamos número de comparações e movimentações realizadas depende do quão ordenada a lista está. Por exemplo, para uma lista em ordem inversa, o número de comparações e movimentações é elevado. Por outro lado, para uma lista já ordenada, o número de comparações e movimentações é mínimo, sendo que, neste caso, a complexidade do algoritmo é linear. Por fim, este algoritmo é indicado para conjuntos pequenos de dados.
Um algoritmo de ordenação é dito estável se ele mantém a ordem original dos elementos iguais quando é aplicado a uma lista. Isso significa que, se dois elementos são iguais, e aparecem na ordem original como A e B, então depois de ordenados, eles continuarão aparecendo como A e B, independentemente da ordem em que eles foram comparados pelo algoritmo.
No entanto, o algoritmo de ordenação por seleção é não estável, pois ele escolhe o menor elemento da lista e o coloca na primeira posição, sem levar em consideração a ordem original dos elementos iguais. Isso pode resultar em mudanças na ordem original dos elementos iguais.
A imagem abaixo apresenta um exemplo de ordenação de uma lista que contém elementos repetidos, considerando os três algoritmos:
Neste exemplo, a lista contém dois elementos de valor 2 colocados em cores diferentes, pois assim facilita o entendimento.
Antes de tudo, observe que os algoritmos de ordenação bolha e por inserção são estáveis, pois preservam a ordem original dos elementos iguais. Perceba, então, que nestes algoritmos o elemento 2 (vermelho) aparece antes do 2 (azul) tanto na lista inicial quanto na lista ordenada.
Por outro lado, o algoritmo de ordenação por seleção é não estável, pois não garante que a ordem dos elementos iguais seja preservada. Perceba, portanto, que no início o elemento 2 (vermelho) aparecia antes do elemento 2 (azul). Entretanto, ao ordenar a lista pela ordenação por seleção, a ordem original destes dois elementos foi alterada, fazendo com que o elemento 2 (azul) ficasse antes do 2 (vermelho).
O quadro abaixo apresenta um resumo comparativo dos algoritmos de ordenação bolha, por seleção e por inserção:
| Característica | Bolha | Seleção | Inserção |
| Complexidade | O(n²) | O(n²) | O(n²) para o pior e médio casos e O(n) no melhor caso |
| Eficiência | Baixa | Média | Alta para pequenos conjuntos de dados |
| Estabilidade | Estável | Não estável | Estável |
| Modo de operação | Comparações consecutivas | Seleção do menor elemento | Inserção ordenada |
| Uso | Pouco comum | Pouco comum | Comum em listas encadeadas ou pequenos conjuntos de dados |
Ano: 2022 Banca: IBFC Órgão: AFEAM Prova: IBFC – 2022 – AFEAM – Especialista de Fomento – Desenvolvimento de Sistemas
Relacione os números que referem-se a algoritmos de ordenação com as respectivas letras de suas principais características técnicas:
1. Insertion Sort
2. Selection Sort
3. Bubble sort
A. Consiste em selecionar o menor item e colocar na primeira posição, selecionar o segundo menor item e colocar na segunda posição, segue estes passos até que reste um único elemento.
B. Consiste em cada passo, a partir do segundo elemento, selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação.
C. Percorre o vetor diversas vezes e, a cada passagem faz flutuar para o topo o maior elemento da sequência.
Assinale a alternativa com a correlação correta de cima para baixo.
A) 1B – 2A – 3C
B) 1C – 2A – 3B
C) 1B – 2C – 3A
D) 1A – 2B – 3C
Comentário:
A letra A se refere ao algoritmo de ordenação por seleção (Selection Sort), que é o algoritmo que seleciona os menores elementos e os coloca nas posições iniciais.
A letra B se refere ao Insertion Sort, pois percorre a lista selecionando selecionando o próximo elemento e o colocando na posição correta dentre os elementos ordenados, ou seja, os que estão à sua esquerda.
A letra C se refere ao algoritmo da bolha. A questão facilitou ao colocar a expressão “flutuar para o topo”. O que o algoritmo bolha faz é basicamente percorrer a lista comparando os elementos adjacentes e trocando-os caso não estejam em ordem.
Portanto, a alternativa A) está certa.
Ano: 2022 Banca: IBADE Órgão: SEA-SC Prova: IBADE – 2022 – SEA-SC – Analista de Informática
Sistemas operacionais como o Linux, e linguagens como Python, dispõem de rotinas de classificação (sort). Dentre os algoritmos dessas rotinas há um método que percorre um vetor de elementos da esquerda para a direita e, à medida que avança, vai ordenando os elementos à esquerda. Consiste em cada passo, a partir do segundo elemento, selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação. Esse método é chamado:
A) selection sort.
B) bubble sort.
C) inserction sort.
D) quick sort.
E) merge sort.
Comentário:
A questão descreve o funcionamento do algoritmo de ordenação por inserção, ou seja, insertion sort. Portanto, a letra C é a alternativa correta.
Ano: 2022 Banca: IBADE Órgão: SES-MG Prova: IBADE – 2022 – SES-MG – T01 – Área de TI – Tarde
O algoritmo de ordenação decrescente onde cada entidade é comparada com o seu posterior e, se maior, invertidas as posições sucessivamente, até que a coleção esteja ordenada, é chamado :
A) selection sort.
B) digital sort.
C) bubble sort.
D) quick sort.
E) random sort.
Comentário:
A questão descreve o funcionamento do algoritmo bolha ou bubble sort, que percorre a lista comparando os elementos adjacentes e os trocando de posição caso não estejam em ordem. Portanto, a letra C é a alternativa correta.
Ano: 2021 Banca: FGV Órgão: Banestes Provas: FGV – 2021 – Banestes – Analista em Tecnologia da Informação – Desenvolvimento de Sistemas
Considere um processo de ordenação dos elementos do array [16,8,6,14,12,4] em ordem crescente. Supõe-se um algoritmo que percorra o array repetidamente até que esteja ordenado, sem utilização de memória auxiliar para os elementos do array (in place).
A lista a seguir mostra a disposição dos elementos no array após cada ciclo de iteração.
[8, 6, 14, 12, 4, 16]
[6, 8, 12, 4, 14, 16]
[6, 8, 4, 12, 14, 16]
[6, 4, 8, 12, 14, 16]
[4, 6, 8, 12, 14, 16]
Nesse caso, é correto concluir que foi utilizado o algoritmo:
A) Bubble Sort;
B) Insertion Sort;
C) QuickSort;
D) Selection Sort;
E) Shellsort.
Comentário:
A questão apresenta um exemplo de execução do algoritmo bolha (bubble sort), em que os maiores elementos “flutuam” para o topo da lista. O algoritmo funciona comparando os elementos adjacentes e trocando-os de posição caso não estejam ordenados.
Perceba que a cada iteração os elementos maiores irão para fim da lista. Na primeira iteração, o maior elemento, 16, vai para o final. Na segunda, o elemento 14 vai para a penúltima posição. E, assim, o algoritmo continua até que todos os elementos estejam ordenados.
Portanto, a letra A é a alternativa correta.
Ano: 2014 Banca: CESGRANRIO Órgão: Petrobras Prova: CESGRANRIO – 2014 – Petrobras – Técnico(a) de Informática Júnior
Os algoritmos de ordenação por seleção (SS) e bubble sort (BS) foram usados para ordenar a sequência 31, 11, 23, 17, 13 de forma crescente.
Quantas trocas e comparações foram realizadas, respectivamente, por cada um?
a) SS – 3 e 10 / BS – 7 e 10
b) SS – 3 e 11 / BS – 8 e 16
c) SS- 8 e 16/ BS – 3 e 11
d) SS – 7 e 16 / BS – 3 e 10
e) SS- 4 e 11/ BS – 8 e 16
Comentário:
Gabarito: letra A.
Pela fórmula do número de comparações do algoritmo de ordenação por seleção e bolha já mataríamos a questão. Veja que a lista possui 5 elementos, assim:
C = n * (n – 1) / 2;
C = 5 * 4 / 2;
C = 10.
Dessa forma, tanto o método da bolha, quanto a ordenação por seleção fazem 10 comparações. Portanto, a única alternativa que possui 10 comparações para o algoritmo de ordenação por seleção e da bolha é a letra A.
Mas, para o desencargo de consciência, vamos verificar o número de trocas realizadas.
Vejamos:
Observe que, no método bolha tivemos 7 trocas e na ordenação por seleção tivemos 3 trocas.
Portanto, a letra A é a alternativa correta.
Ano: 2011 Banca: CESGRANRIO Órgão: FINEP Prova: CESGRANRIO – 2011 – FINEP – Analista – Desenvolvimento de Sistemas
Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?
a) O(n²)
b) O(1)
c) O(n)
d) O(n log n)
e) O(log n)
Comentário:
Gabarito: letra A.
A complexidade do algoritmo de ordenação por inserção é:
Portanto, a letra A é a alternativa correta.
Ano: 2021 Banca: CESGRANRIO Órgão: Banco do Brasil Prova: CESGRANRIO – 2021 – Banco do Brasil – Agente de Tecnologia
Dentre os problemas identificados pela gerência de um banco comercial, está a localização das contas dos seus titulares nas listagens e nos relatórios impressos em diferentes situações. Um especialista de TI sugeriu ordenar as contas por meio dos CPF dos seus n titulares antes das impressões.
Dentre alguns algoritmos pré-selecionados para essa ordenação, o especialista escolheu o algoritmo de ordenação por inserção, no qual o consumo de tempo é, no melhor caso, proporcional a
a) n log n
b) log n
c) n²
d) n
e) 1
Comentário:
Questão semelhante à anterior. A complexidade do algoritmo de ordenação por inserção é:
Portanto, a letra D é a alternativa correta.
Bom pessoal, enfim finalizamos este artigo. Espero muito que este estudo tenha uma ótima contribuição para seu estudo e sua aprovação. Por fim, tenham fé e disciplina, que as aprovações chegarão. Bons estudos!
Pacote para o cargo Agente de Tecnologia
Pacotaço (Conteúdo + Passo estratégico) para o cargo Agente de Tecnologia
A edição 2024.2 do Exame CFC está chegando e muitos bacharéis ou estudantes do último…
No Resumo da Semana você encontra diversas informações sobre concursos públicos previstos e editais publicados!…
O edital do concurso do Instituto Nacional do Semiárido (INSA) foi publicado com oferta de 19…
Está em pauta a realização de um novo concurso PC AL (Polícia Civil de Alagoas)…
Autorização de novo edital iminente! O próximo concurso PC ES (Polícia Civil do Espírito Santo)…
Salário inicial de R$ 7,8 mil! Atenção, corujas: a autorização para realização de um novo…