Selection Sort

Por
|

O Selection Sort (ordenação por seleção) é um dos algoritmos de ordenação quadráticos mais populares. A implementação dele também é bem simples.

Algoritmo de ordenação por seleção Selection Sort

Nesta postagem, é feita uma análise do funcionamento do algoritmo. Também apresento o mesmo codificado em Java, em C e em JavaScript.

Índice

Funcionamento do Selection Sort

Sabemos que, num vetor ordenado em ordem crescente, o menor valor ocupa a primeira posição, o segundo menor valor ocupa a segunda posição e assim sucessivamente. É claro, isso é óbvio.

A ideia do Selection Sort é justamente utilizar esse fato para realizar ordenação. Como exemplo, ordenaremos o vetor [40, 9, 4, -1, 6]. Vamos considerar o 0 (zero) como o primeiro índice do vetor.

Na primeira iteração, procuramos o menor valor entre os índices 0 e 4 (índice da última posição). O menor valor é o -1, que está no índice 3. Então, trocamos os valores dos índices 0 e 3:

Selection sort ilustração

Como o valor do índice 0 já está na posição correta, então não precisamos fazer mais nada nesse índice. Ou seja, nos resta ordenar o subvetor que vai do índice 1 até o índice 4.

Na segunda iteração, procuramos o menor valor entre os índices 1 e 4. O menor valor é o 4, que está no índice 2. Então, trocamos os valores dos índices 1 e 2:

Selection sort ilustração

Na terceira iteração, procuramos o menor valor entre os índices 2 e 4. O menor valor é o 6, que está no índice 4. Então, trocamos os valores dos índices 2 e 4:

Selection sort ilustração

Na quarta iteração, procuramos o menor valor entre os índices 3 e 4. O menor valor é o 9, que está no índice 4. Então, trocamos os valores dos índices 3 e 4:

Selection sort ilustração

Agora, nos resta apenas um subvetor com um único elemento [40], que obviamente já está ordenado.

A cada iteração, um elemento é colocado na posição correta. Você pode, alternativamente, fazer a ordenação começando pela última posição do vetor, ou seja, começamos colocando o maior elemento na última posição, depois o segundo maior na penúltima posição e continuamos até chegarmos no início do vetor.

Ir para o índice

Pseudocódigo

Ao implementar o Selection Sort, é conveniente também implementarmos um método que retorna o índice do menor elemento de um vetor num certo intervalo (será o método min). O pseudocódigo é dado a seguir (vou utilizar o 1 como índice inicial)

1. selectionSort(A[1...n])
2. |  para i ← 1 até n - 1
3. |  |   minIndex ← min(A, i, n)
4. |  |   trocar(A, i, minIndex)
5. |  fim_para
6. fim_selectionSort

O método min é (k ≤ l)

1. min(A[1...n], k, l)
2. |  minIndex ← k
3. |  para i ← k + 1 até l
4. |  |   se(A[minIdex] > A[i])
5. |  |   |   minIndex ← i
6. |  |   fim_se
7. |  fim_para
8. |  retorne minIndex
9. fim_min

O método trocar(A, i, j) troca os valores das posições i e j do vetor A

1. trocar(A, i, j)
2. |  temp ← A[i]
3. |  A[i] ← A[j]
4. |  A[j] ← temp
5. fim_trocar

É claro, você pode fazer tudo num único método (o clássico "código linguiça")

01. selectionSortSausage(A[1...n])
02. |   para i ← 1 até n - 1
03. |   |   minIndex ← i
04. |   |   para j ← i + 1 até n
05. |   |   |   se(A[minIdex] > A[j])
06. |   |   |   |   minIndex ← j
07. |   |   |   fim_se
08. |   |   fim_para
09. |   |   temp ← A[i]
10. |   |   A[i] ← A[minIndex]
11. |   |   A[minIndex] ← temp
12. |   fim_para
13. fim_selectionSortSausage

Observe que os laços externos os pseudocódigos só iteram até a penúltima posição, pois depois disso só restará o último elemento, que já estará na posição correta.

Ir para o índice

Complexidade assintótica

O laço duplo aninhado no método selectionSortSausage deixa evidente que o algoritmo é $O(n^2)$. Isso também é válido para a versão modular, uma vez que as duas versões são equivalentes.

A quantidade de comparações A[minIdex] > A[j] realizadas pelo Selection Sort é expressa por

$$\begin{align*}\sum_{i=1}^{n-1} \sum_{j=i+1}^n 1&=\sum_{i=1}^{n-1} (n-i)\\&=n(n-1)-\frac{n(n-1)}{2}\\&=\frac{n(n-1)}{2}\\&=\frac{n^2-n}{2}\\&=\frac{n^2}{2}-\frac{n}{2}\end{align*}$$

Portanto, a complexidade é $O(n^2)$. Mesmo se contássemos as demais operações, ainda obteríamos a mesma complexidade.

Ir para o índice

Códigos

Os códigos em Java, C e em JavaScript do Selection Sort podem ser obtidos nos links a seguir

Ir para o índice

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário