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:
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:
Agora, vejamos algumas importantes observações:
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.
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:
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.
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.
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:
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º.
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.
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).
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.
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.
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:
Vamos lá:
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!
Pacote para o cargo Agente de Tecnologia
Pacotaço (Conteúdo + Passo estratégico) para o cargo Agente de Tecnologia
Assinatura Concursos: Assine 1 ou 2 anos