Como comparar algoritmos select 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:

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

Ufa, terminamos por aqui! Até a próxima!