Módulo 10Aula Expositiva 12

4.3 Ordenação4.3.1 Seleção (SelectSort)4.3.2 Intercalação (MergeSort)4.3.3 Partição (QuickSort)4.3.4 Dividir para Conquistar

DCC 001Programação de Computadores

2º Semestre de 2011Prof. Osvaldo Carvalho

Ordenação (“sort”) Problema clássico da Ciência da Computação Dado um vetor A, obter outro vetor com os mesmos

elementos de A dispostos em ordem crescente (ou decrescente)

1 2 3 4 5 6 7

34 56 27 45 12 44 341 2 3 4 5 6 7

12 27 34 34 44 45 56

Vetor não ordenado

Vetor ordenado

2DCC001 - 2011-2

Conjunto Desordenado

DCC001 - 2011-2 3

Conjunto Ordenado

DCC001 - 2011-2 4

Ordenação por Seleção e Troca

Em inglês, Select Sort Cabeçalho da função:

function sA = SelectSort(A) // Constrói o vetor sA com os // mesmos elementos do vetor A // dispostos em ordem crescente.endfunction

5DCC001 - 2011-2

Ordenação por Seleção e Troca: Raciocínio Indutivo

Suponhamos que as k-1 primeiras posições do vetor A já contenham elementos em suas posições finais

Selecionamos o menor valor entre A(k) e A(length(A))

Trocamos o valor deste menor elemento com o valor em A(k), e fazemos k = k+1

Terminamos quando k = length(A)-1 O algoritmo se inicia com k igual a 1 6DCC001 - 2011-2

Passos da Ordenação por Seleção1 2 3 4 5 6 7

34 56 27 45 12 44 341 2 3 4 5 6 7

12 56 27 45 34 44 341 2 3 4 5 6 7

12 27 56 45 34 44 341 2 3 4 5 6 7

12 27 34 45 56 44 341 2 3 4 5 6 7

12 27 34 34 56 44 451 2 3 4 5 6 7

12 27 34 34 44 56 451 2 3 4 5 6 7

12 27 34 34 44 45 567DCC001 - 2011-2

Seleção de elementos a trocar de posição

DCC001 - 2011-2 8

Ordenação por Seleção Segunda Versão

function sA = SelectSort(A) for k = 1:length(A)-1 // Seleciona a posição entre A(k) e // A(length(A)) que contém o menor valor // Troca o valor de A(k) com o valor na // posição selecionada. end sA = A;endfunction

9DCC001 - 2011-2

Troca de Valores de Duas Variáveis

Se fizermos x = y; y = x; o valor antigo de x que queríamos armazenar em y é perdido

Se fizermos y = x; x = y; teremos o problema inverso

Solução: variável temporária:temp = x; x = y; y = temp;

10DCC001 - 2011-2

Função MinimoPosPrimeira Versão

Parece com a função Minimo que teremos que modificar para ter como parâmetro extra de entrada a

parte do vetor considerada ter também como parâmetro de saída a

posição do elemento de menor valor, e não apenas o seu valor

11DCC001 - 2011-2

A Função Minimo

function m = Minimo(A) // Encontra o menor valor presente no vetor A m = A(1); for k = 2:length(A) if m > A(k) m = A(k); end endendfunction

12DCC001 - 2011-2

Função MinimoPosVersão Final

function [m, im] = MinimoPos(A,low,high) // Encontra o menor valor (m) // presente no vetor A entre as // posições low e high, e informa // sua posição no vetor (im) m = A(low); im = low; for k = low+1:high if m > A(k) m = A(k); im = k; end endendfunction

13DCC001 - 2011-2

Programa MinimoPos_teste.sce// Programa que testa a função MinimoPosexec("MinimoPos.sci");exec("PrintMatrix.sci");

a = int(10*rand(1,10));PrintMatrix("A",a);inicio = input("Inicio = ");fim = input("Fim = ");while inicio > 0 [m im] = MinimoPos(a,inicio,fim) inicio = input("Inicio = "); fim = input("Fim = ");end

14DCC001 - 2011-2

Função SelectSortVersão Final

function sA = SelectSort(A) for k = 1:length(A)-1 // Seleciona a posição entre A(k) e // A(length(A)) que contém o menor valor [Min iMin] = MinimoPos(A,k,length(A)); // Troca os valores de A(k) com o valor // na posição selecionada. temp = A(k); A(k) = A(iMin); A(iMin) = temp; end sA = A;endfunction

15DCC001 - 2011-2

ComplexidadeOrdenação por Seleção

O primeiro passo realiza n-1 comparações;

O segundo, n-2; o terceiro, n-3, e assim por diante, até o último passo, que faz 1 comparação

Nós dizemos que este algoritmo é O(n2), ou que tem complexidade quadrática

16DCC001 - 2011-2

Teste de DesempenhoOrdenação por Seleção

n=5000

90s

17DCC001 - 2011-2

Ordenação por Intercalação(Merge Sort)

DCC001 - 2011-2 18

Intercalação Intercalação (merge) é uma operação

que produz um vetor ordenado a partir de dois outros já ordenados1 2 3 4 1 2 3 4 5 6

15 15 19 22 10 16 19 20 23 27

1 2 3 4 5 6 7 8 9 1010 15 15 16 19 19 20 22 23 27

a b

Intercalação de a e b

19DCC001 - 2011-2

Ordenação por Intercalação

Se o tamanho do vetor for maior que 1: divide-se o vetor em duas partes ordena-se cada parte separadamente faz-se a intercalação das partes já

ordenadas senão, o vetor já está ordenado

DCC001 - 2011-2 20

16 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

8 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

4 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

2 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

1 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

2 12 72 26 54 73 98 0 59 25 30 11 62 61 67 2 33

4 12 26 54 72 0 59 73 98 11 25 30 62 2 33 61 67

8 0 12 26 54 59 72 73 98 2 11 25 30 33 61 62 67

16 0 2 11 12 25 26 30 33 54 59 61 62 67 72 73 98

MergeSortExemplo com n = 16 = 24

21DCC001 - 2011-2

10 60 85 6 82 92 56 57 81 5 55

5 60 85 6 82 92 56 57 81 5 55

3 60 85 6 56 57 81

2 60 85 82 92 56 57 5 55

1 60 85 6 82 92 56 57 81 5 55

2 60 85 82 92 56 57 5 55

3 6 60 85 56 57 81

5 6 60 82 85 92 5 55 56 57 81

10 5 6 55 56 57 60 81 82 85 92

MergeSortExemplo com n = 10

22DCC001 - 2011-2

Função MergeSort

function sA = MergeSort(A) if length(A) <= 1 then sA = A; else m = int((1+length(A))/2); sA = Merge(MergeSort(A(1:m)),... MergeSort(A(m+1:length(A)))); endendfunction

23DCC001 - 2011-2

A Função Merge - Intercalação

function M = Merge(A,B) pA = 1; pB = 1; pM = 1 while pA <= length(A) & pB <= length(B) if A(pA) <= B(pB) then M(pM) = A(pA); pA = pA+1; else M(pM) = B(pB); pB = pB+1; end pM = pM+1; end// continua....

24DCC001 - 2011-2

“Consome” um elemento

de A“Consome” um elemento

de B

A Função Merge - Arremate // Esgota A while pA <= length(A) M(pM) = A(pA); pM = pM+1; pA = pA+1; end

// Esgota B while pB <= length(B) M(pM) = B(pB); pM = pM+1; pB = pB+1; endendfunction

25DCC001 - 2011-2

Intercalação - Complexidade

Cada passo “consome” um elemento de a ou de b; Se a e b têm tamanhos m e n, respectivamente, a

intercalação de a e b exige no máximo m+n passos

1 2 3 4 1 2 3 4 5 615 15 19 22 10 16 19 20 23 27

1 2 3 4 5 6 7 8 9 1010 15 15 16 19 19 20 22 23 27

a b

Intercalação de a e b

26DCC001 - 2011-2

MergeSort – Complexidade

DCC001 - 2011-2 27

16

8

4

2

1 12 72 26 54 98 73 0 59 30 25 62 11 61 67 33 2

2 12 72 26 54 73 98 0 59 25 30 11 62 61 67 2 33

4 12 26 54 72 0 59 73 98 11 25 30 62 2 33 61 67

8 0 12 26 54 59 72 73 98 2 11 25 30 33 61 62 67

16 0 2 11 12 25 26 30 33 54 59 61 62 67 72 73 98

O trabalho está na fase de intercalação O algoritmo é

16 passos

16 passos

16 passos

16 passos

4 =

log2

(16)

nnO 2log

Teste de DesempenhoOrdenação por Seleção

n=5000

90s

28DCC001 - 2011-2

MergeSort – Teste de Desempenho

50000

60

29DCC001 - 2011-2

Ordenação por Partição(quicksort)

DCC001 - 2011-2 30

Vetor Particionado

DCC001 - 2011-2 31

1 2 3 4 5 6 7 8 9

93 100 56 12 123 100 231 212 112

≤ 100 ≥ 100 Para ordenar um vetor particionado,

basta ordenar cada partição

Vetor Particionado

DCC001 - 2011-2 32

QuickSort, ou Ordenação por Partição

Uso de operação de partição, que divide um vetor com 2 ou mais elementos em três partes: a da esquerda, contendo somente elementos

menores ou iguais ao pivô, a do meio, contendo somente elementos iguais ao

pivô, e a da direita contendo somente elementos maiores

ou iguais ao pivô. Após a partição, o algoritmo é aplicado

recursivamente às partições esquerda e direita

33DCC001 - 2011-2

A Função QuickSort

function sA = quicksort(A) if length(A) > 1 then [l,m,r] = partition(A) sA = [quicksort(l) m quicksort(r)]; else sA = A; endendfunction

34DCC001 - 2011-2

Partições Sucessivas

35DCC001 - 2011-2

14 0 11 6 5 12 2 12 13 6

2 0 5 6 11 12 14 12 13 6

0 2 5 6 11 12 6 12 13 14

0 2 5 6 11 12 6 12 13 14

0 2 5 6 6 12 11 12 13 14

0 2 5 6 6 11 12 12 13 14

0 2 5 6 6 11 12 12 13 14

EsquerdaMeioDireita

x Pivô

A Função Partitionfunction [left,middle,right] = partition(A) pivot = A(int(length(A)/2)); inf = 1; sup = length(A); while sup >= inf while A(inf) < pivot inf = inf+1; end while A(sup) > pivot sup = sup-1; end if sup >= inf then temp = A(inf); A(inf) = A(sup); A(sup) = temp; inf = inf+1; sup = sup-1; end end left = A(1:sup); middle = A(sup+1:inf-1); right = A(inf:length(A));endfunction

36DCC001 - 2011-2

Notas sobre a Função Partition

O pivô é escolhido como o elemento posicionado ao meio do vetor A. Isto não é um requisito do algoritmo, que entretanto exige que o pivô seja um dos elementos de A;

inf é mantido de forma tal que, a qualquer momento, todos os elementos à sua esquerda são menores ou iguais ao pivô. Repare que isto é válido inicialmente, pois não existe nenhum elemento à sua esquerda, e que é mantido válido por todos os comandos;

37DCC001 - 2011-2

Notas sobre a Função Partition

sup é mantido de forma tal que, a qualquer momento, todos os elementos à sua direita são maiores ou iguais ao pivô; a argumentação para esta afirmativa é análoga à empregada para a variável inf;

inf avança sempre para a direita, e sup para a esquerda; o loop principal para quando estes dois ponteiros se cruzam;

38DCC001 - 2011-2

Notas sobre a Função Partition

no primeiro loop interno, inf avança para a direita até encontrar um elemento com valor maior ou igual ao pivô;

no segundo loop interno, sup avança para a esquerda até encontrar um elemento com valor menor ou igual ao pivô;

os elementos encontrados nestes dois loops internos são trocados de posição, a não ser que inf e sup já tenham se cruzado;

39DCC001 - 2011-2

QuickSort - Complexidade

Melhor Caso O pivô é tal que cada partição divide o vetor ao

meio São feitas n log(n) comparações

Pior Caso O pivô é tal que cada partição produz uma parte

com um elemento, e outra com n-1 elementos A complexidade é quadrática -

Prática Na prática os casos ruins são raros, e o QuickSort

apresenta um excelente desempenho 40DCC001 - 2011-2

2nO

DCC001 - 2011-2 41

DCC001 - 2011-2 42

MergeSort – Teste de Desempenho

50000

60

43DCC001 - 2011-2

Desempenho Quicksort

DCC001 - 2011-2 44

700.000

Desempenho QuicksortElementos Ordenados por Segundo

DCC001 - 2011-2 45

Dividir para Conquistar MergeSort e QuickSort são exemplos de uma

estratégia clássica em computação Dado um problema de tamanho n

O problema é dividido em 2 subproblemas de tamanho n/2 (ou 3 de tamanho n/3, ou...)

Cada subproblema é atacado recursivamente, com a mesma estratégia, a não ser que o seu tamanho seja suficientemente pequeno para permitir uma solução direta

As soluções dos subproblemas são combinadas para resolver o problema original

46DCC001 - 2011-2

Conclusões

Um mesmo problema pode admitir diversas soluções, cujo desempenho pode variar significativamente

Para problemas grandes a adoção de soluções mais elaboradas pode ser um imperativo

Recursividade é uma ferramenta poderosa para a descoberta e descrição de algoritmos

47DCC001 - 2011-2