Método de Ordenação Bolha para o Concurso do BB (TI)

Olá pessoal, tudo bem? Se você está se preparando para o cargo de Agente de Tecnologia do concurso do Banco do Brasil e está com dificuldade de entender os algoritmos de ordenação, veja esta série de três artigos que estou preparando com o intuito de facilitar o seu aprendizado. Neste artigo, apresentamos o método de ordenação bolha, também chamado de bubble sort.

Primeiramente, é importante entender o que é a ordenação de elementos, que consiste basicamente em colocá-los em ordem crescente ou decrescente. Alguns exemplos de ordenação são: ordenar alunos pelas suas notas; ordenar uma lista telefônica pelo nome das pessoas; ordenar pessoas por idade; ordenar clientes de acordo com a renda; entre outras.

Além disso, é importante saber que a ordenação de elementos é realizada através de algoritmos de ordenação, e existem vários deles, mas iremos focar em três, que constam no edital do concurso do Banco do Brasil , os quais são: o método de ordenação bolha, a ordenação por seleção e a ordenação por inserção.

Neste artigo, abordaremos o método de ordenação bolha, contemplando os seguintes tópicos:

Entendendo o método de ordenação bolha: etapas
Pseudocódigo
Exemplo (passo a passo)
Análise de complexidade do método de ordenação bolha
Resumo
Vamos praticar!

Entendendo o método de ordenação bolha: etapas

Em primeiro lugar, bolha é um algoritmo de ordenação simples e bastante conhecido, que recebe este nome porque a cada iteração o maior elemento da sequência flutua para o topo, lembrando uma bolha. Ele consiste basicamente em percorrer uma lista comparando os elementos adjacentes (dois a dois) e trocando de posição os que estão fora de ordem.

Além disso, existem variações do método bolha: em alguns casos o método consiste em “flutuar” o maior valor para a última posição a cada iteração, já em outros casos, o menor valor vai para a primeira posição a cada interação.

Assim, como é um método de implementação simples, poucos são os passos necessários para sua implementação. Por exemplo, considerando uma lista de N elementos, as etapas do método bolha são as seguintes:

Percorrer a lista comparando os elementos adjacentes (dois a dois);
Trocar de posição os elementos que estiverem fora de ordem;
Repetir os dois primeiros passos N-1 vezes, sendo que a cada iteração a lista a ser percorrida diminui em uma posição, não sendo necessário comparar os elementos já ordenados.

Agora, vejamos algumas importantes observações:

Para uma lista de tamanho N, o número de iterações é N-1, ou seja, se a lista possui 5 elementos, o número de iterações será 4.
Ao final de uma iteração, um elemento já estará na ordem certa, sendo desnecessário realizar outras comparações com ele nas próximas iterações, o que faz diminuir o número de comparações. Assim, para a mesma lista com 5 elementos, na primeira iteração realizam-se 4 comparações, na segunda realizam-se 3 comparações, e assim por diante.

Pseudocódigo

Neste tópico, apresentaremos duas versões de pseudocódigo do método de ordenação bolha. Primeiramente, a versão clássica, que realiza todas as iterações, mesmo se a lista já estiver ordenada. Em seguida, uma versão que melhora o método, contendo uma condição de parada que finaliza o algoritmo quando a lista já estiver ordenada.

Pseudocódigo do algoritmo bolha: versão clássica

A seguir, iremos apresentar o pseudocódigo e explicaremos cada uma de suas linhas. Vejamos:

1 pseudocódigo bolha(lista X com N elementos):

2 para i de 1 até N-1 faça:

3 para j de 1 até N-i faça:

4 se X[j] > X[j+1] então

5 trocar(X[j], X[j+1])

6 fim_se

7 fim_para

8 fim_para

9 fim

Basicamente, as linhas de 2 a 5 definem o algoritmo:

Linha 2: inicia o laço com a quantidade de iterações. Observe que o número de iterações é N-1;
Linha 3: inicia o laço para percorrer a lista. Veja bem a expressão “até N – i”, indicando que a medida que aumenta o número de iterações (variável i), a lista a ser percorrida será menor. Isso ocorre porque como o maior elemento irá para o fim, ao final da primeira iteração ele já estará ordenado, não sendo necessário realizar comparações com ele nas demais iterações, fazendo com que, na segunda iteração, seja necessário percorrer somente até o penúltimo elemento, e assim, a cada iteração o algoritmo percorre um elemento a menos na lista.
Linhas 4 e 5: aqui é feita a comparação entre o elemento atual e o próximo. Se o valor do elemento atual for maior que o valor do próximo, é realizada a troca, indicada na linha 5.

Antes de mais nada, o problema deste pseudocódigo é que se ele receber uma lista ordenada como parâmetro, mesmo assim irá executar todas as iterações e percorrer a lista, fazendo todas as comparações, mas não realizando nenhuma troca. Isso é uma grande perda de desempenho.

Pseudocódigo do algoritmo bolha: versão melhorada

Para melhorar o método de ordenação bolha, há uma variação com condição de parada, que verifica se o houve troca em algum momento ao percorrer a lista. Assim, se não houve nenhuma troca após uma iteração, a lista está ordenada e não é necessário continuar a execução do algoritmo. Dessa forma, vejamos como fica:

1 pseudocódigo bolha2(lista X com N elementos):

2 i = 1

3 faça:

4 trocou = false

5 para j de 1 até N-i faça:

6 se X[j] > X[j+1] então

7 trocar(X[j], X[j+1])

8 trocou = true

9 fim_se

10 fim_para

11 i = i + 1

12 enquanto(trocou)

13 fim

Vejam que adicionamos a variável booleana “trocou”, que a cada iteração inicializará com o valor “false”, mas se durante a iteração houver alguma troca, o valor passará a ser “true”. Logo, quando não houver trocas, a lista estará ordenada. Por fim, para reduzir o número de comparações, mantivemos a variável i, incrementando-a a cada iteração.

Exemplo (Passo a passo)

Para facilitar a compreensão, vejamos a seguir um exemplo de ordenação, através do método de ordenação bolha, de uma lista com 5 elementos, ou seja, N = 5. A lista a ser ordenada é a seguinte [8, 4, 3, 5, 2]. Dessa forma, o número de iterações será 4, pois N – 1 = 5 – 1 = 4.

Na primeira iteração (i = 1), o método percorrerá a lista completa (N – i = 5 – 1 = 4), comparando os elementos dois a dois – na verdade percorrerá até o penúltimo elemento, mas este será comparado com o último, pois as comparações são sempre do elemento atual com o próximo. Vejamos:

Método de ordenação bolha: primeira iteração

Observe que ao final da primeira iteração, o maior elemento já está na ordem certa, não sendo necessário realizar novas comparações deste com outros elementos nas próximas iterações. Portanto, para a segunda iteração (i = 2), o último elemento não participará, sendo que o algoritmo só percorrerá até o 3º elemento (N – i = 5 – 2 = 3), que será comparado com o 4º.

Método de ordenação bolha: segunda iteração

Ao final da segunda iteração, já temos dois elementos ordenados nas últimas posições. Sendo assim, na terceira iteração (i = 3), serão realizadas comparações apenas com os três primeiros elementos.

Método de ordenação bolha: terceira iteração

Aqui já temos os três últimos elementos ordenados, restando apenas os dois primeiros, ou seja, apenas uma comparação. Para isso, na quarta iteração (i = 4) precisaremos de apenas uma comparação (j = N – i = 5 – 4 = 1).

Método de ordenação bolha: quarta iteração

Ao final da quarta iteração, temos a lista ordenada. Observe que para ordenar a lista foram feitas 10 comparações e 8 trocas. Saber disso é importante, pois as bancas costumam cobrar bastante, tanto é que caiu questão assim na última prova do Banco do Brasil e também do Banco da Amazônia, organizadas pelas banca Cesgranrio.

Para calcular rapidamente o número de comparações que o algoritmo bolha realiza, basta utilizarmos a seguinte fórmula: Comparações = N(N-1)/2, em que N é o tamanho da lista. Portanto, se o tamanho da lista é 5, então o algoritmo fará 5*(5-1)/2 = 5*4/2 = 10 comparações. Caso o tamanho seja 10, o algoritmo fará 10*9/2 = 45 comparações.

Apenas cuidado, pois o comando da questão pode dizer que o algoritmo irá parar de executar quando não houver mais trocas, ou em outro momento. Assim, se for dessa forma, para saber o número de comparações deverá ser realizado o passo a passo.

Por fim, em relação ao número de trocas realizadas, não tem jeito, deve ser realizado o passo a passo do algoritmo.

Análise de Complexidade do Método de Ordenação Bolha

O algoritmo de ordenação bolha, embora seja popular, apresenta desempenho ruim se comparado a outros algoritmos de ordenação.

Isso se deve à sua complexidade, que é quadrática, O(n²), ou seja, o esforço computacional despendido pelo algoritmo varia de ordem quadrática de acordo com o tamanho do problema. Isso acontece porque o método bolha utiliza dois laços de repetição aninhados.

Continuando, uma complexidade quadrática, O(n²), indica basicamente que conforme o tamanho da lista aumenta, o tempo para executar aumenta quadraticamente.

Por exemplo, suponhamos que para uma lista de 10 elementos, o algoritmo consome 100 segundos de tempo. Então, se aumentarmos a lista para 30 elementos, o tempo consumido passa a ser 900 segundos. Sendo assim, observe que o tempo gasto neste exemplo é o número de elementos ao quadrado, ou seja, complexidade quadrática.

Devido ao problema de desempenho, o algoritmo da bolha só é indicado para problemas pequenos, que requeiram uma pequena quantidade de dados. Assim, para problemas maiores e mais complexos, existem outros algoritmos que são mais eficientes, como quick sort e merge sort.

A seguir, veremos um pequeno resumo com informações importantes que podem cair na prova.

Resumo

O método de ordenação bolha é um método simples, popular e lento;
Seu funcionamento consiste em levar os maiores elementos para o final da lista, comparando os elementos adjacentes dois a dois e ordenando os que estão fora de ordem;
O número de comparações que o algoritmo faz segue a seguinte fórmula: comparações = N*(N-1)/2;
Este algoritmo possui complexidade quadrática O(n²).

Vamos praticar!

Agora faremos uma questão sobre o algoritmo de ordenação bolha que caiu no último concurso do Banco do Brasil.

Ano: 2021 Banca: CESGRANRIO Órgão: Banco do Brasil Prova: CESGRANRIO – 2021 – Banco do Brasil – Agente de Tecnologia

As agências bancárias negociam seguros residenciais com seus clientes e, muitas vezes, precisam arquivar cópias de forma ordenada para que consultas eventuais sejam facilitadas. O gerente de uma agência precisava ordenar um vetor de documentos referentes a esses seguros, e o seu adjunto, da área de TI, o aconselhou a usar o algoritmo de ordenação chamado Bubble Sort.

Utilizando-se o algoritmo sugerido, qual será a quantidade de trocas de posições realizadas para ordenar, de modo crescente, o vetor de números de contrato (77, 51, 11, 37, 29, 13, 21)?

a) 14

b) 15

c) 16

d) 17

e) 18

Comentário:

Vamos aos pontos chaves:

A sequência a ser ordenada pelo programador é [77, 51, 11, 37, 29, 13, 21];
O examinador quer saber o número de trocas de posições.

Vamos lá:

sequência : [77, 51, 11, 37, 29, 13, 21];
1ª iteração: [51, 11, 37, 29, 13, 21,77] → 6 trocas;
2ª iteração: [11, 37, 29, 13, 21,51, 77] → 5 trocas;
3ª iteração: [11, 29, 13, 21, 37, 51, 77] → 3 trocas;
4ª iteração: [11, 13, 21, 29, 37, 51, 77] → 2 trocas;
5ª iteração: [11, 13, 21, 29, 37, 52, 77] → 0 trocas;

Portanto, a resposta é 6+5+3+2 = 16, letra C.

Bem pessoal, enfim terminamos aqui o artigo sobre o método de ordenação bolha, espero que este conteúdo seja útil na sua jornada rumo à aprovação. No próximo artigo desta série, veremos como funciona na prática o algoritmo de ordenação por seleção. Então, bons estudos!