Defina formalmente o problema de ordenação.

Formalmente pode assim ser definido: Formalmente pode assim ser definido: Ordenação Entrada: Uma seqüência de n números ‹a1, a2, ..., an›. Saída: Uma reordenação da seqûëncia de entrada ‹a'1, a'2, ..., a'n›, onde a'1 ≤ a'2 ≤ ... ≤ a'n. Em geral, consideramos a seqüência de entrada como um array de n elementos.
Questão 2
Completo
Vale 1,00 ponto(s).
Marcar questão
Texto da questão

Forneça um exemplo de aplicação real que envolva o problema de ordenação e de encontrar o menor valor.

Uma lista de candidatos que ordenada por um sistema com base na menor pontuação
Questão 3
Completo
Vale 2,00 ponto(s).
Marcar questão
Texto da questão

Escreva um algoritmo que receba um vetor ordenado e um numero extra e insira esse número na sua posição correta no vetor ordenado, deslocando os outros números se necessário.

insere_vetor(int v[] ,int num)


inicio

    i --> aumenta_v (v[],1,tam);// retorna tamanho atualizado do vetor

     enquanto (i>0) &&(v[i-1]>num)

     inicio:

           v[i]-->v[i-1];

            i-->i-1;

      fim

    v[i] =num

fim


Questão 4
Completo
Vale 6,00 ponto(s).
Marcar questão
Texto da questão

Faça um teste de mesa com cada método de ordenação estudado até o momento, utilizando as seguintes sequencias de dados de entrada:

(a) 2, 4, 6, 8, 10, 12


(b) 11, 9, 7, 5, 3, 1


(c) 5, 7, 2, 8, 1, 6


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79


Em cada caso, mostre o número de comparações e trocas que realizam na ordenação de sequencias.

selectinon sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 15,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T= 15, S= 3


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8

T= 15

S= 4


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 10


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 45
 S = 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 45
 S = 8

insertion sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 5,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T= 15, S= 15


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8

T= 9

S= 7


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 40
 S = 35


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 25
 S = 20


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 28
 S = 26


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 25
 S = 25
Quick sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 21,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T = 63
 S = 42


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8
T = 32
 S = 21


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 84
 S = 42


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 45
 S = 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 45
S = 8
Merge sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 15,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T= 15, S= 3


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8

T= 15

S= 4


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 10


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 45
 S = 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 45
 S = 8

Radix sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 15,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T= 15, S= 3


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8

T= 15

S= 4


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 10


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 45
 S = 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 45
 S = 8
Bucket sort

(a) 2, 4, 6, 8, 10, 12


2--> 4--> 6 -->8--> 10--> 12

T= 15,S = 0


(b) 11, 9, 7, 5, 3, 1

1-- >3 -->5 -->7--> 9--> 11

T= 15, S= 3


(c) 5, 7, 2, 8, 1, 6

1--> 2--> 5--> 6--> 7--> 8

T= 15

S= 4


(d) 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 10


(e) 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11

1--> 2--> 3--> 4--> 5--> 6--> 7--> 8--> 9--> 10--> 11--> 12
 T = 66
 S = 11


(f) 8, 9, 7, 9, 3, 2, 3, 8, 4, 6

2--> 3--> 3--> 4--> 6--> 7--> 8--> 8--> 9--> 9
 T = 45
 S = 6


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 45
 S = 8