Concursos Públicos

Algoritmos de Ordenação: Resumo para o Concurso BB (TI)

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:

  • Funcionamento do algoritmo;
  • Desempenho do algoritmo:
    • Complexidade dos algoritmos de ordenação
    • Eficiência dos algoritmos de ordenação
  • Estabilidade dos algoritmos de ordenação
  • Quadro comparativo
  • Questões para revisão

Funcionamento do algoritmo

Método da bolha

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.

Algoritmo de Ordenação por Seleção

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. 

Algoritmo de Ordenação por Inserçã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.

Desempenho dos algoritmos

Complexidade dos algoritmos de ordenação

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çãoPior CasoCaso MédioMelhor Caso
BolhaO(n^2)O(n^2)O(n^2)**
SeleçãoO(n^2)O(n^2)O(n^2)
InserçãoO(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:

  • Pior e médio caso: os três algoritmos tem complexidade quadrática, ou seja, n².
  • Melhor caso:
    • Ordenação por seleção: complexidade quadrática, ou seja, n².
    • Ordenação por inserção: complexidade linear, ou seja, n.
    • Método da bolha:
      • algoritmo tradicional da bolha: complexidade quadrática, isto é, n²,
      • algoritmo com condição de parada: complexidade linear, isto é, n.

Eficiência dos algoritmos de ordenação

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.

Estabilidade dos algoritmos de ordenação

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).

Quadro comparativo dos algoritmos de ordenação

O quadro abaixo apresenta um resumo comparativo dos algoritmos de ordenação bolha, por seleção e por inserção:

CaracterísticaBolhaSeleçãoInserção
ComplexidadeO(n²)O(n²)O(n²) para o pior e médio casos e O(n) no melhor caso
EficiênciaBaixaMédiaAlta para pequenos conjuntos de dados
EstabilidadeEstávelNão estávelEstável
Modo de operaçãoComparações consecutivasSeleção do menor elementoInserção ordenada
UsoPouco comumPouco comumComum em listas encadeadas ou pequenos conjuntos de dados
  • Complexidade: refere-se ao número de operações que o algoritmo realiza para ordenar um conjunto de dados.
  • Eficiência: refere-se à velocidade do algoritmo em ordenar um conjunto de dados.
  • Estabilidade: refere-se à capacidade de manter a ordem relativa dos elementos iguais em um conjunto de dados durante a ordenação.
  • Modo de operação: refere-se à maneira como o algoritmo funciona para ordenar um conjunto de dados.

Questões para praticar

Questão 1

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. 

Questão 2

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.

Questão 3

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.

Questão 4

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.

Questão 5

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.

Questão 6

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 é:

  • Pior caso e caso médio:
  • Melhor caso: n

Portanto, a letra A é a alternativa correta.

Questão 7

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 é:

  • Pior caso e caso médio:
  • Melhor caso: n

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

Quer saber tudo sobre concursos previstos?
Confira nossos artigos!

Concursos abertos

Concursos 2023

Antoniel da Silva Rego

Posts recentes

Banco do Brasil: como estudar para a redação do concurso?

Olá! Tudo bem? Hoje vamos falar como estudar para o Concurso do Banco do Brasil!…

8 horas atrás

Aumento no piso salarial para Magistério em 2025!

Valor para 2025 é de R$ 4.867,77 Foi publicada a Portaria Interministerial MEC/Fazenda nº 13/2024,…

10 horas atrás

Transtorno de Personalidade Obsessivo-Compulsiva para Psicólogo da PC-DF

Neste artigo você encontrará um resumo do Transtorno de Personalidade Obsessivo-Compulsiva, pertencente ao tópico de…

10 horas atrás

EBSERH: quais são as etapas eliminatórias e classificatórias?

Quais são as etapas eliminatórias e classificatória do concurso EBSERH (Empresa Brasileira de Serviços Hospitalares)?…

10 horas atrás

ITCMD para SEFAZ-PR: Legislação Tributária Estadual

Olá, pessoal. Tudo certo? No artigo de hoje veremos o resumo sobre o ITCMD para…

10 horas atrás

Câmara de Manaus divulga o resultado final. Confira!

Foi divulgado nesta terça-feira (24) o resultado final do concurso Câmara de Manaus, no Amazonas.…

11 horas atrás