Seguindo com a série, iremos falar de outro algoritmo de ordenação conhecido como selection sort (ordenação por seleção). 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: 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] 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:Vamos ao Selection Sort
Desempenho
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:
Se 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):
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:
Se consideramos n como o número de elementos na lista, pode-se descobrir o número de pares da seguinte forma:
Para uma lista com cinco elementos:
Para uma lista com seis elementos:
Mas 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:
A fórmula para calcular o número de operações no selection sort é:
Vamos aplicar a fórmula e validar se o número de operações está sendo calculado corretamente:
Para uma lista com cinco elementos:
Para uma lista com seis elementos:
Logo, abstraindo a fórmula acima:
Para 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
Exemplo código selection sort usando PythonUfa, terminamos por aqui! Até a próxima!