Olá pessoal! Tudo bem? Para você que está se preparando para o concurso do Banco do Brasil, cargo Agente de Tecnologia, neste artigo estudaremos o algoritmo ordenação por seleção ou selection sort.
Antes de mais nada, a ordenação de elementos 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, para ordenação dos elementos, podem ser utilizados diversos algoritmos de ordenação, dentre os quais, três deles constam no edital do concurso do Banco do Brasil: método da bolha, ordenação por seleção e ordenação por inserção.
Neste artigo, abordaremos os seguintes tópicos sobre o algoritmo de ordenação por seleção:
Primeiramente, para ordenar uma lista, o algoritmo de ordenação por seleção funciona, inicialmente, selecionando o menor valor da lista e trocando com o primeiro elemento. Em seguida, como o primeiro elemento já está em sua posição, o algoritmo seleciona o menor elemento do restante da lista e troca com o primeiro elemento deste restante.
E isso acontece em cada iteração, com a lista restante ficando um elemento menor que na iteração anterior e a primeira parte da lista ficando ordenada. Este processo ocorre até que todos os elementos sejam comparados e, consequentemente, ordenados.
Para facilitar o entendimento, vejamos as etapas do algoritmo de ordenação por seleção:
Observe que o que o algoritmo de ordenação por seleção faz é basicamente dividir a lista principal em duas sub-listas, uma ordenada e a outra desordenada. Inicialmente, a lista ordenada começa vazia e a lista desordenada com todos os elementos da lista principal. Ao longo do tempo, a lista ordenada vai crescendo e a desordenada diminuindo, considerando que a junção das duas equivale à lista principal.
A divisão lógica em sub-listas ordenada e não ordenada é utilizada apenas para fins didáticos, para facilitar o entendimento. Assim, o que o algoritmo faz na verdade é percorrer a lista e a cada iteração ir colocando os menores elementos à esquerda.
Assim, na primeira iteração, o menor elemento é selecionado e vai para a primeira posição; na segunda iteração, ignora-se o primeiro elemento, e seleciona-se o menor entre o restante da lista, que vai para a segunda posição; e assim por diante, até a última iteração.
Abaixo está o pseudocódigo do algoritmo de ordenação por seleção e, logo após, a explicação de cada linha:
Vejamos, então, a explicação do pseudocódigo:
Para exemplificar, iremos considerar a seguinte lista: [8, 4, 2, 5, 3]. Inicialmente, temos toda a lista fora de ordem. Dessa forma, a sub-lista ordenada começa vazia e a sub-lista não ordenada começa com todos os elementos.
Na primeira iteração temos:
O algoritmo de ordenação por seleção inicia selecionando o menor elemento da sub-lista não ordenada, que é o valor 2, e o troca com o primeiro elemento desta sub-lista, que é o valor 8. Ao fim da primeira iteração, o valor 2, que está ordenado, passa a fazer parte da sub-lista ordenada. Dessa forma, a sub-lista ordenada passa a ter seu primeiro elemento, [2], enquanto que a sub-lista não ordenada diminui um elemento, passando a ser [4, 8, 5, 3].
Vejamos, então, a segunda iteração do algoritmo:
Veja que na segunda iteração, o valor 2 já não faz mais parte do processo de seleção, pois está na sub-lista ordenada. Assim, o menor dentre os desordenados é o 3, que é trocado com o primeiro deles, que é o 4. Ao final então temos os valores ordenados [2, 3] e o restante desordenados [8, 5, 4].
Observe que este processo é repetitivo. Sendo assim, para não tornar a explicação repetitiva, apresentamos em conjunto a terceira e a quarta iteração:
Vejamos, então, algumas observações importantes:
Em resumo, 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. Isso é repetido para cada posição subsequente até a lista inteira estar ordenada. É um algoritmo simples, porém ineficiente em termos de tempo de execução, principalmente quando aplicado em grandes conjuntos de dados.
O algoritmo de ordenação por seleção não preserva a ordem original dos elementos iguais. Essa propriedade é conhecida como estabilidade de um algoritmo de ordenação.
Um algoritmo de ordenação é estável se ele mantém a ordem original dos elementos iguais. 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 o algoritmo realiza a comparação deles.
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.
Vejamos um exemplo que mostra como o algoritmo de ordenação por seleção não preserva a ordem original de elementos iguais (neste caso, temos dois elementos de valor 2 colocados em cores diferentes para facilitar o entendimento):
Lista original: (2, 5, 3, 2, 1)
Como podemos perceber, a ordem original dos dois 2’s foi alterada. No início, o 2 azul aparecia antes do 2 vermelho. Entretanto, com a ordenação por seleção, essa ordem mudou. No entanto, se tivéssemos usado um algoritmo de ordenação estável, a ordem original dos 2’s teria sido preservada.
Uma importante observação é que, diferente do algoritmo de ordenação por seleção, os algoritmos de ordenação bolha e por inserção são estáveis, preservando a ordem original dos elementos iguais.
Um dos pontos importantes no estudo e desenvolvimento de algoritmos é a análise de complexidade dos algoritmos, que é uma forma de calcular o desempenho de um algoritmo através do número de operações realizadas (como comparações, atribuições, etc.) à medida que o tamanho da entrada aumenta.
Assim, com base na análise da complexidade, é possível calcular o tempo de execução de um algoritmo. A análise de complexidade é importante pois permite que entendamos como o desempenho de um algoritmo é afetado pelo tamanho da entrada, possibilitando a escolha de algoritmos mais adequados de acordo com o problema.
De cara, podemos observar que no algoritmo de ordenação por seleção temos um laço de repetição dentro de outro, ou seja, de grosso modo, a lista é percorrida N * N, ou N², sendo N o tamanho da lista. Portanto, a complexidade do algoritmo de ordenação por seleção é n², em todos os casos: pior, médio e melhor.
Além disso, é importante saber o número de comparações e de trocas realizadas. É importante observar que algoritmo realiza, para cada iteração, uma quantidade de comparações diferente, pois o processo de seleção ignora os elementos já ordenados.
Então, considerando uma lista de 5 elementos, temos:
Dessa forma, realizam-se 4 + 3 + 2 + 1 = 10 comparações.
De forma mais rápida, podemos calcular o número de comparações realizadas pelo algoritmo de ordenação por seleção através da seguinte equação:
C = n * ( n - 1 ) / 2, onde C é o número de comparações.
Assim, para uma lista de tamanho 5, o número de comparações é (5 * 4)/2 = 10.
Além disso, é interessante observar que em cada iteração acontece no máximo uma troca de posição na lista, podendo não acontecer nenhuma, caso o menor valor já esteja no início da lista considerada na iteração. Sendo assim, para uma lista de n elementos, como temos n – 1 iterações, teremos, no máximo, n – 1 trocas. Logo:
T ≤ n - 1, onde T é o número de trocas.
Portanto, para uma lista de 5 elementos, teremos, no máximo, 4 trocas com o algoritmo de ordenação por seleção.
Além disso, é importante ressaltar que essas fórmulas são meramente aproximações e que a quantidade real de comparações e trocas pode variar dependendo da implementação do algoritmo.
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.
Antes de tudo, pela fórmula do número de comparações do algoritmo de ordenação por seleção já mataríamos a questão. Veja que a lista possui 5 elementos, logo:
C = n * (n - 1) / 2;
C = 5 * 4 / 2;
C = 10.
Assim, a única alternativa que possui 10 comparações para o algoritmo de ordenação por seleção é a letra A.
Mas, para o desencargo de consciência, vamos verificar o número de trocas realizadas. Vejamos:
| Lista inicial | [31, 11, 23, 17, 13] | |
| Primeira iteração | [11, 31, 23, 17, 13] | Houve troca: 31 e 11 |
| Segunda iteração | [11, 13, 23, 17, 31] | Houve troca: 31 e 13 |
| Terceira iteração | [11, 13, 17, 23, 31] | Houve troca: 23 e 17 |
| Quarta iteração | [11, 13, 17, 23, 31] | Não houve troca: o 23 já era o menor |
Portanto, houve três trocas e 10 comparações pelo algoritmo de ordenação por seleção, letra A.
Enfim terminamos o artigo sobre o algoritmo de ordenação por seleção, espero que este estudo seja útil para sua jornada rumo à aprovação no concurso do Banco do Brasil.
Pacote para o cargo Agente de Tecnologia
Pacotaço (Conteúdo + Passo estratégico) para o cargo Agente de Tecnologia