3.
Ordenao por Seleco (Selection Sort)
3.1. Ideia Bsica
Neste processo de ordenao, pretende-se utilizado o mtodo mais simples possvel, na qual percorre-se o conjunto de elementos a ordenar e procura-se o maior/menor elemento do conjunto. Estando este elemento j ordenado, procura -se o segundo maior/menor elemento, e assim por diante at obter-se todos os elementos ordenados.
" I PB&&E
) 3 ) ' %#" 765$&4 210($&$!
3.2. Mtodo
Neste mtodo, pretende -se ordenar os elementos de um array, que vo ser ordenados desde a primeira posio at lt a posio, na qual em cada iterao da ordenao calculado o maior/menor (maior elemento para ordenao por ordem decrescente, menor caso contrrio) valor dos elementos que ainda faltam ordenar. ordenados. O processo repete -se at que todos os elementos do array estejam Para ordenar os seguintes dados por ordem crescente, processa-se do seguint modo: 10 8 6 2 16 4 18 11 14 12 Menor elemento do array 2 8 6 10 16 4 18 11 14 12 2 4 6 10 16 8 18 11 14 12
HH %#" "E "@ $D$&$G7CFDCBA&!79 8
1 de 4
d VSt PcB&&r
WUT h c VWi R a h g Tfedc a`U b a` YT X VUT R 765T$&4a 210($&$!W S Q
2 4 6 10 16 8 18 11 14 12 2 4 6 8 16 10 18 11 14 12
3.3.
1. 2.
Algoritmo
Iniciar achando o menor elemento. Trocar o menor elemento pelo primeiro. Parte do vector est agora ordenada. 3. 4. Achar o menor elemento da parte no ordenada. Troque com o primeiro elemento da parte no ordenada. Adicionar mais um nmero parte ordenada. 5. 6. Aumentar o tamanho da parte ordenada em um elemento. Voltar ao passo 3. Pode-se parar quando a parte no ordenada tem apenas um nmero, sendo este o maior elemento.
3.4.
Eficincia Tempos de Ordenao (sendo N o nmero de elementos a ordenar)
Melhor caso = N (dados j ordenados), dado que o ciclo interno nunca ser executado, pois a sua condio falha sempre. 2 Mdia = N Pior caso = N (dados ordenados em ordem inversa), sendo N o nmero de elementos do array, o ciclo mais abrangente dever ser executado N vezes, e o ciclo interno ser executado N vezes por cada ciclo mais abrangente... No difcil verificar que o algoritmo de seleco, tal como o de insero, faz cerca de n2 comparaes en re elementos do vector.
2
ss Tfed XdUSTUr a` Yc aSdq S $D$&$G7CFDCBA&!79cV p
2 de 4
w PB&&
yx v x y x yx v 765x$&4 210($&$! w u
3.5. Implementao em C++
void SelectionSort(int array[], int num_elem) { for (int i = 0; i < num_elem -1; i++) { int min = i; // ndice do elemento a ordena for (int j = i; j < num_elem -1; j++) // Clculo do mnimo { if (a ray[j] < array[min]) { min = j; } } int temp = array[min]; array[min] = array[i]; array[i] = temp; } }
3.6.
Exemplo
Array com 10 elementos a ordenar por ordem crescente. 10
[0]
8
[1]
6
[2]
2
[3]
16
[4]
4
[5]
18
[6]
11
[7]
14
[8]
12
[9]
1 passo de ordenao: menor elemento: dados[3] que colocado na posio dados[0] 2
[0]
8
[1]
6
[2]
10
[3]
16
[4]
4
[5]
18
[6]
11
[7]
14
[8]
12
[9]
2 passo de ordenao: menor elemento: dados[5] que colocado na posio dados[1] 2
[0]
4
[1]
6
[2]
10
[3]
16
[4]
8
[5]
18
[6]
11
[7]
14
[8]
12
[9]
3 passo de ordenao: menor elemento: dados[2] que colocado na posio dados[2] 2
[0]
4
[1]
6
[2]
10
[3]
16
[4]
8
[5]
18
[6]
11
[7]
14
[8]
12
[9]
x ywxy w w $D$&$G7CFDCBA&!79
3 de 4
p hez PoB&&x
igf t o hiu d m t s frqpo mlg n ml kf j hgf d 765f$&4m 210($&$!i e
4 passo de ordenao: menor elemento: dados[5] que colocado na posio dados[3] 2
[0]
4
[1]
6
[2]
5
[3]
16
[4]
10
[5]
18
[6]
11
[7]
14
[8]
12
[9]
5 passo de ordenao: menor elemento: dados[5] que colocado na posio dados[4] 2
[0]
4
[1]
6
[2]
5
[3]
10
[4]
16
[5]
18
[6]
11
[7]
14
[8]
12
[9]
Nota: O processo repete-se at que todos os elementos do array estejam ordenados.
3.7.
Resumo
Mtodo de ordenao, na qual so procurados sucessivos elementos que se encontram fora de ordem, retira o elemento da lista e depois insere o elemento de forma ordenada. Este t po de ordenao em pequenas listas rpido, sendo extremamente lento para grandes listas.
yy frqp jpgefgx ml ko mepw e $D$&$G7CFDCBA&!79oh v
4 de 4