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

a0|a1|a2|a3....|an
1ª iteração a1(a0)
2ª iteração a2(a1,a0)
3ª iteração a3(a2,a1,a0)
nesse algoritmo cada componente do vetor nao ordenado e comparado com a parte odenada do vetor para achar sua posição

(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
a0|a1|a2|a3....|an
seleciono um pivor p{an}agrupo os iferiores a esquerda e os superiores a direita
comparo o pivor com n{an-1}utilizo 2 vareáveis{i,j} i incrementa caso an+i seja >p{an}e j incrementa caso contrário e os elementos de indece j e i trocam de posição. esse procedimento e realizado para os n-1 numeros ao final o pivor fica posicionado isso se repete até o vetor ficar ordenado.

(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 = 69
 S = 21


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

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


(g) 89, 79, 32, 38, 46, 26, 43, 38, 32, 79
26--> 32--> 32--> 38--> 38--> 43--> 46--> 79--> 79--> 89
 T = 95
S = 61
Merge sort
a0|a1|a2|a3|a5|a6
a0|a1|a2|   |a3|a4|a5
a0|a1||a2|   |a3|a4||a5
a0|a1||a2|	 |a3|a4||a5
a0||a1|      a3||a4|
vetores temporários
{a1<a0}       {a4<a3}
a1|a0          a4|a3
nesta etapa um vetor cujo o tamanho é igual a soma dos 2 vetores comparados
(a) 2, 4, 6, 8, 10, 12


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

 T = 59
 S = 40



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

1-- >3 -->5 -->7--> 9--> 11
 T = 62
 S = 40

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

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

 T = 62
 S = 40



(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 = 147
 S = 98


(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 = 147
 S = 98


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

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



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