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.
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:
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:
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:
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:
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.
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.
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.
Códigos
Os códigos em Java, C e em JavaScript do Selection Sort podem ser obtidos nos links a seguir
Nenhum comentário:
Postar um comentário