Escrito por
Mateus Almeida
em
Análise Selection Sort
Pseudocódigo
1 |PROCEDIMENTO SelectionSort(A[] : Inteiro):
2 |VAR
3 | |i, j, min, t : Inteiro
4 |INICIO
5 | |PARA i <- 1 ATÉ Comprimento(A) - 1, FAÇA:
6 | | |// Encontrar o menor elemento
7 | | |min <- i
8 | | |PARA j <- i+1 ATÉ Comprimento(A), FAÇA:
9 | | | |SE A[j] < A[min], ENTÃO:
10 | | | | |min <- j
11 | | | |FIM-SE
12 | | |FIM-PARA
13 | | |// Trocar o menor elemento com aquele da posição i
14 | | |t <- A[min]
15 | | |A[min] <- A[i]
16 | | |A[i] <- t
17 | |FIM-PARA
18 |FIM
Corretude
Laço invariante
Laço para as linhas 5 até 17.
Invariante
Na k-ésima iteração A[k-i-1] contém os (i-1)-menores elementos ordenados.
Inicialização
Antes da primeira iteração, temos que A[j..i-1] está vazio. Logo, o invariante é trivialmente verdadeiro.
Manutenção
Supondo que o invariante é verdadeiro antes da i-ésima iteração do laço invariante, temos que A[1..i-1] está ordenado com os (i-1)-menores elementos do vetor. Na i-ésima iteração, a posição do menor elemento em A[i..n] é guardada na variável min (linhas 7 até 12), em seguida, é realizada a troca entre os elementos das posições i e min (linhas 14 a 16).
Finalização
Desta forma, A[i+1..n] contém elementos maiores ou iguis a A[i] e temos que os elementos de A[j-i-1] são menores ou iguais a A[i] e estão ordenados. Então, antes da (i+1)-ésima iteração, temos que A[1..i] contém os i-menores elementos de A ordenados.
Complexidade de tempo
O melhor caso para o algoritmo Selection Sort ocorre quando o arranjo de elementos já está ordenado.
O pior caso para o algoritmo Selection Sort ocorre quando o arranjo de elementos está ordenado em ordem inversa, ou seja, em ordem decrescente, pois, precisará percorrer o vetor várias vezes para encontrar o menor elemento e colocá-lo na posição correta.
Para o caso médio, o algoritmo precisará fazer um número de comparações e trocas proporcional ao quadrado do tamanho da lista a ser ordenada.
Tempo total
Nº de Iterações: 1,2,3,…,n
Comparações: (n-1), (n-2), (n-3),…,1
\[(n-1)+(n-2)+(n-3)+...+1
\\= n(n-1)/ 2
\\=O(n^{2})\]