Ordene Selection Sort e Insertion Sort

Nome: Luciano Soares da Silva,

RGM 15760201

Diciplina: Estruturas de Dados  - Mauricio Wieler Orellana

CIÊNCIA DA COMPUTAÇÃO – UNICID

Ordene Selection Sort e Insertion Sort

Vetor { 8 7 6 5 4 3 2 1}

Selection Sort

Localiza menor elemento do array (1)e efetua troca  com elemento 8  (1<8)

Posição	0	1	2	3	4	5	6	7
Elemento	1	7	6	5	4	3	2	8

                       [pic 1][pic 2]

Fixa na elemento 1  na posição 0  array

Localiza menor elemento do array (2)  e efetua troca  com elemento(7). (2<7)

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	6	5	4	3	7	8

  [pic 3][pic 4]

Fixa na elemento 2  na posição 1  array

Localiza menor elemento do array (3)  e efetua troca  com elemento(6) (3<6)

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	5	4	6	7	8

  [pic 5][pic 6]

Fixa na elemento 3  na posição 2  array

Localiza menor elemento do array (4)  e efetua troca  com elemento(5) (4<5)

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	5	4	6	7	8

  [pic 7][pic 8]

Fixa na elemento  4  na posição 3  array

Localiza menor elemento do array (5) não efetua troca  pois o elemento encontra-se na posição ordenada

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	4	5	6	7	8

[pic 9]

Fixa na elemento  5  na posição 4  array

Localiza menor elemento do array (6) não efetua troca  pois o elemento encontra-se na posição ordenada

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	4	5	6	7	8

[pic 10]

Fixa na elemento  6  na posição 5  array

Localiza menor elemento do array (7) não efetua troca  pois o elemento encontra-se na posição ordenada

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	4	5	6	7	8

                                                                                                                                                                                        [pic 11]

Fixa na elemento  7  na posição 6  array

Localiza menor elemento do array (8) não efetua troca  pois o elemento encontra-se na posição ordenada!

Posição	0	1	2	3	4	5	6	7
Elemento	1	2	3	4	5	6	8	8

                                        [pic 12]

        Insertion Sort O(n²)

Seleciona 2º elemento é comparado com seu antecessor:

Sendo  elemento selecionado menor  que seu antecessor (7<8) #efetua troca de posição

Posição	0	1	2	3	4	5	6	7
Elemento	7	8	6	5	4	3	2	1

                       [pic 13][pic 14]

Seleciona 3º elemento é comparado com seu antecessor: