Algoritmos de Ordenação: Selection Sort
Seguindo com a série, iremos falar de outro algoritmo de ordenação conhecido como selection sort (ordenação por seleção).
Vamos ao Selection Sort
Resumo do resumo: sua ideia consiste em ordenar a lista “selecionando” a cada iteração o menores itens possíveis e os colocam da esquerda para a direita.
Assim como o Bubble Sort, é necessário para cada item da lista percorrê-la toda (logo, serão necessários dois loops: um para cada elemento da lista e outro para cada um desses elementos percorrer toda a lista).
Suas principais vantagens estão na fácil implementação do algoritmo, além de ocupar pouca memória se comparado a algoritmos como quick e merge sort que utilizam a estratégia de “dividir e conquistar” (que serão explicados em outros posts futuramente).
A desvantagem é que um dos algoritmos de maior tempo de execução em todos os casos (O(n²) — será explicado o porquê deste tempo de execução neste artigo), o que o torna uma opção ruim para listas com um grande número de itens.
Para entender melhor a ideia que algoritmo aplica — ao invés de uma lista, pense que temos duas sublistas: uma sublista que está ordenada e outra que está desordenada.
Como não foi iniciado o processo de “seleção” (que será explicado a seguir), faz sentido considerar que a lista toda não está ordenada. Logo, não há nenhum elemento na “lista ordenada” ainda e a lista desordenada contém todos os elementos.
Temos então na lista ordenada: nenhum elemento. E na lista desordenada? Todos os elementos da lista principal: 5, 3, 1, 2, 4
Agora, o que este “processo de seleção” citado acima realmente significa?
O processo de seleção obtém o menor elemento da lista desordenada. Por enquanto, ignore os detalhes da implementação e imagine que percorremos a lista desordenada item a item para saber qual o menor número.
Qual é o menor número desta lista desordenada? É o número 1, obviamente!
Este então, foi o número selecionado pelo processo. Colocamos ele então na lista ordenada e retiramos da lista desordenada.
Para não nos perdermos, eis aqui o que feito:
- A lista principal contém os elementos sequencialmente: 5, 3, 1, 2, 4;
- A lista principal foi subdividida logicamente em duas sublistas: a lista ordenada (que inicialmente está vazia) e a lista desordenada (que inicialmente contém todos os elementos da lista principal);
- O processo de seleção rodou uma vez. Com isso, se obteve o menor item da lista desordenada (que tinha os números 5, 3, 1, 2, 4: logo, o menor número dentro deste conjunto é o número 1).
- Colocamos o número 1 (menor item da lista) na lista ordenada ( que na verdade é o índice da primeira posição da lista principal) e remove este número da lista desordenada (não se preocupe, pois maiores detalhes serão explicados sobre essa parte. Mas o que ocorre no algoritmo é que os itens são trocados dentro da lista principal: assim o certo a se dizer é que o elemento que estava no índice da lista que está se iterando no primeiro loop pela posição do elemento que possui menor valor);
Este processo de seleção é realizado até que a lista desordenada esteja vazia (ou mais precisamente, quando o primeiro loop terminar). Com isso, há a certeza de que a lista ficará ordenada.
No próximo processo de seleção, será ignorado o número 1 (ou o que está à esquerda).
Mas por que? Ora, ele já foi “selecionado” e agora faz parte da sublista ordenada e sabe-se também que não será encontrado ninguém menor dentro da sublista desordenada.
Pronto! Os elementos encontram-se ordenados, pois não há mais nada na lista desordenada.
Vamos ignorar esta divisão lógica das sublistas ordenadas e desordenadas para entender o que ocorre de fato no processo do algoritmo. Existe apenas uma lista principal e os itens obtidos por meio do processo de seleção são colocados da posição mais à esquerda da lista principal. Em outras palavras: os itens são posicionados da esquerda para a direita, conforme o processo de seleção obtém os menores itens.
Na próxima iteração do primeiro loop, são ignorados os itens que estão à esquerda da posição do mesmo, somente iterando e comparando os itens que estão à direita. Esse comportamento ocorre porque sabe-se que tudo que está à esquerda já está na ordem correta e o que está à direita, pode ou não estar ordenado (o algoritmo considera que o que está à direita está desordenado). Isto significa que se a lista possui os itens 1, 2, 5, 4, 3 e o primeiro loop está no terceiro item (5) — todos os itens à esquerda do terceiro item (1 e 2) não serão considerados para a realização do processo de seleção.
Ao ter certeza de qual é o menor item (essa informação é obtida ao fim do segundo loop) e sua posição na lista, pode-se então trocar os valores de posição. Com isso, o item de menor valor obtido ficará na posição que está sendo iterado no primeiro loop e o valor que estava neste entra na lista dos “desordenados”. (Se não ficou claro, dê uma olhada nas imagens acima, pois é exatamente aquilo que ocorre a cada processo de seleção)
Aplicando o processo de seleção citado acima, a lista modifica-se da seguinte maneira:
Estado Inicial: [5, 3, 1, 2, 4]
Após a primeira seleção : [1, 3, 5, 2, 4]
Após a segunda seleção: [1, 2, 5, 3, 4]
Após a terceira seleção: [1, 2, 3, 5, 4]
Após a quarta seleção: [1, 2, 3, 4, 5]
Desempenho
Agora, vamos entender o desempenho do selection sort. Sabe-se que o processo de seleção precisa varrer sempre a “lista desordenada” para comparar os itens. Essa lista, como pôde ser observado na explicação acima, vai decrementando em um conforme as iterações.
Utilizando o exemplo acima como base:
Dado uma lista de cinco posições [5,4,3,2,1]:
Serão inicialmente quatro comparações (ou 5–1) para o processo de seleção obter o menor item (o item que está sendo iterado (no caso índice 0) não precisa ser comparado. Logo, conta-se do segundo ao quinto item, ou seja dos índices 1 a 4: 1, 2, 3, 4).
No segundo processo de seleção, serão três comparações (ou 5–2) nos índices 3, 4 e 5
No terceiro processo de seleção serão duas comparações (ou 5–3) nos índices 4 e 5.
No quarto processo de seleção será apenas uma comparação (ou 5–4) no índice 5
Pode-se expressar isso então, da seguinte forma:
(5–1) + (5- 2) + (5–3) + (5–4) = 4 + 3 + 2 + 1 = 10Se os pares somados forem sempre agrupados do maior para menor par, teremos como resultado o mesmo valor do tamanho da lista (no exemplo acima, 5):
[(5 - 1) + (5 - 4)] + [(5 - 3) + (( 5- 2))][4 + 1] + [2 + 3] = 5 + 5 = 10
Em caso de agrupar em pares e algum acabe ficando sem par (isso ocorre quando a quantidade de itens na lista é par), basta somá-lo isoladamente da mesma forma (o que sobrar valerá sempre a metade do tamanho da lista).
Por exemplo, imagine que a lista tenha seis elementos, então, seguindo o mesmo raciocínio acima:
[(6–1) + (6–5)] + [(6–2) + (( 6 - 4)] + [(6–3)][5 + 1] + [4 + 2] + [3] = 6 + 6 + 3 = 15
Se consideramos n como o número de elementos na lista, pode-se descobrir o número de pares da seguinte forma:
número de pares = (n — 1) / 2Para uma lista com cinco elementos:
(5–1) / 2 = 2 paresPara uma lista com seis elementos:
(6 – 1) / 2 = 5 / 2 = 2,5 paresMas ainda não sabemos o que realmente queremos: o número de operações executadas. Sabemos como descobrir o número de “pares” dado o tamanho da lista. Porém precisamos ainda multiplicar pelo tamanho da lista, pois conforme explicado acima, a soma de cada agrupamento é igual ao tamanho da lista.
Para uma lista com cinco elementos:
5 * 2 = 10 operações6 * 2,5 = 15 operações
A fórmula para calcular o número de operações no selection sort é:
n * (n — 1) / 2Vamos aplicar a fórmula e validar se o número de operações está sendo calculado corretamente:
4 * [(4–1) / 2] = 4* (3 / 2) = 6 operaçõesPara uma lista com cinco elementos:
5 * [(5 - 1) / 2] = 5 * (4 / 2) = 10 operaçõesPara uma lista com seis elementos:
6 * ([(6 — 1) / 2]) = 6 * (5 / 2) = 15 operaçõesLogo, abstraindo a fórmula acima:
n * (n — 1) / 2 = (n² — n) / 2Para análise assintótica, podemos ignorar os valores constantes. O que importa mesmo n² / 2 , pois conforme a lista crescer, este valor irá aumentar quadraticamente. Por isso, o algoritmo selection sort possui tempo de execução O(n²).
Por fim, segue uma implementação em Python para o algoritmo selection sort
Ufa, terminamos por aqui! Até a próxima!
