Projeto e Análise de Algoritmos - DEINF/UFMAcsalles/paa/paa_01_ordenacao.pdf · Projeto e Análise Aula 1: Algoritmos Prof. Carlos de Terças-feiras , 8h20 ... algoritmo. Como detecto

Projeto e Análise

Aula 1: Algoritmos

Prof. Carlos de Terças-feiras, 8h20

Análise de Algoritmos

Algoritmos de Ordenação

Prof. Carlos de Salles, 8h20 às 11h10

Algoritmos de

• Insertsort

• Mergesort

• Heapsort

• Quicksort• Quicksort

de Ordenação

Algoritmos de

� Dado um vetor v com Nordenação consiste em organizar todos esses N elementos em uma ordem (nãonão-decrescente etc)

� Exemplo:

� v = {1, 9, 8, 5, 3, 7, 4}

− Depois de ordenado de forma não

− v = {1, 3, 4, 5, 7, 8, 9}

de Ordenação

N elementos, a ordenação consiste em organizar todos esses

elementos em uma ordem (não-crescente,

Depois de ordenado de forma não-decrescente, v fica:

Insert Sort

� Outros nomes:

� Bubble sort

� Selection sort

� Consite em posicionar� Consite em posicionarelemento em seu lugarconsecutivas

Insert Sort

o menor ou o maioro menor ou o maiorlugar correto N vezes

Insert Sort

for i=1,N do

for j=i+1,N do

if v[i]>v[j]

v[i],v[j] = v[j],v[v[i],v[j] = v[j],v[

end

end

end

Insert Sort

]>v[j] then

],v[j] = v[j],v[i]],v[j] = v[j],v[i]

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 41 9 8 5 3 7 4

j

Insert Sort

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j

Insert Sort

5 3 7 45 3 7 4

Insert Sort

1 8 9 5 3 7 4

i

1 8 9 5 3 7 4

j

Insert Sort

3 7 43 7 4

Insert Sort

1 5 9 8 3 7 4

i

1 5 9 8 3 7 4

j

Insert Sort

7 47 4

Insert Sort

1 3 9 8 5 7 4

i

1 3 9 8 5 7 4

j

Insert Sort

1 3 9 8 5 7 41 3 9 8 5 7 4

Insert Sort

1 3 9 8 5 7 4

i

1 3 9 8 5 7 4

j

Insert Sort

1 3 9 8 5 7 41 3 9 8 5 7 4

j

Insert Sort

1 3 9 8 5 7 4

i

1 3 9 8 5 7 4

j

Insert Sort

5 7 45 7 4

Insert Sort

1 3 8 9 5 7 4

i

1 3 8 9 5 7 4

j

Insert Sort

7 47 4

Insert Sort

1 3 5 9 8 7 4

i

1 3 5 9 8 7 4

j

Insert Sort

1 3 5 9 8 7 41 3 5 9 8 7 4

Insert Sort

1 3 5 9 8 7 4

i

1 3 5 9 8 7 4

j

Insert Sort

44

j

Insert Sort

1 3 4 9 8 7 5

i

1 3 4 9 8 7 5

j

Insert Sort

7 57 5

Insert Sort

1 3 4 8 9 7 5

i

1 3 4 8 9 7 5

j

Insert Sort

55

Insert Sort

1 3 4 7 9 8 5

i

1 3 4 7 9 8 5

j

Insert Sort

55

j

Insert Sort

1 3 4 5 9 8 7

i

1 3 4 5 9 8 7

j

Insert Sort

77

Insert Sort

1 3 4 5 8 9 7

i

1 3 4 5 8 9 7

j

Insert Sort

77

j

Insert Sort

1 3 4 5 7 9 8

i

1 3 4 5 7 9 8

j

Insert Sort

9 89 8

j

Insert Sort

1 3 4 5 7 8 91 3 4 5 7 8 9

Insert Sort

1 3 4 5 7 8 91 3 4 5 7 8 9

Insert Sort

1 3 4 5 7 8 91 3 4 5 7 8 9Número de operações:

(N-1) + (N-2) + (N-3) + … + 3 + 2 + 1

N*(N-1)2

Insert Sort

1 3 4 5 7 8 91 3 4 5 7 8 9Número de operações:

3) + … + 3 + 2 + 1

1)

Insert Sort

� Ideia:

� Se o vetor já estiver ordenadointeração, seria interessantealgoritmo.

Como detecto se um vetor� Como detecto se um vetor

ordenado = true

for i=1,N do

if v[i]>v[i+1] then ordenado

end

Insert Sort

ordenado em algumainteressante detectar isso e parar o

vetor está ordenado?vetor está ordenado?

ordenado = false end

Insert Sort (

for i=N,2,-1 do

trocas = false

for j=1,i-1 do

if v[j]>v[j+1] then

v[j],v[j+1] = v[j+1],v[j]v[j],v[j+1] = v[j+1],v[j]

trocas = true

end

end

if not trocas then break

end

Insert Sort (melhoria)

then

v[j],v[j+1] = v[j+1],v[j]v[j],v[j+1] = v[j+1],v[j]

break end

Insert Sort (

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j


1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

Insert Sort (

1 9 8 5 3 7 4

i

1 9 8 5 3 7 4

j


5 3 7 4

i

5 3 7 4

Insert Sort (

1 8 9 5 3 7 4

i

1 8 9 5 3 7 4

j


3 7 4

i

3 7 4

Insert Sort (

1 8 5 9 3 7 4

i

1 8 5 9 3 7 4

j


7 4

i

7 4

Insert Sort (

1 8 5 3 9 7 4

i

1 8 5 3 9 7 4

j


4

i

4

Insert Sort (

1 8 5 3 7 9 4

i

1 8 5 3 7 9 4

j


9 4

i

9 4

Insert Sort (

1 8 5 3 7 4 9

i

1 8 5 3 7 4 9

j


1 8 5 3 7 4 91 8 5 3 7 4 9

Insert Sort (

1 8 5 3 7 4 9

i

1 8 5 3 7 4 9

j


3 7 4 93 7 4 9

Insert Sort (

1 5 8 3 7 4 9

i

1 5 8 3 7 4 9

j


7 4 97 4 9

Insert Sort (

1 5 3 8 7 4 9

i

1 5 3 8 7 4 9

j


4 94 9

Insert Sort (

1 5 3 7 8 4 9

i

1 5 3 7 8 4 9

j


99

Insert Sort (

1 5 3 7 4 8 9

i

1 5 3 7 4 8 9

j


1 5 3 7 4 8 91 5 3 7 4 8 9

Insert Sort (

1 5 3 7 4 8 9

i

1 5 3 7 4 8 9

j


7 4 8 97 4 8 9

Insert Sort (

1 3 5 7 4 8 9

i

1 3 5 7 4 8 9

j


1 3 5 7 4 8 91 3 5 7 4 8 9

Insert Sort (

1 3 5 7 4 8 9

i

1 3 5 7 4 8 9

j


8 98 9

Insert Sort (

1 3 5 4 7 8 9

i

1 3 5 4 7 8 9

j


7 8 97 8 9

Insert Sort (

1 3 5 4 7 8 9

i

1 3 5 4 7 8 9

j


7 8 97 8 9

Insert Sort (

1 3 5 4 7 8 9

i

1 3 5 4 7 8 9

j


7 8 97 8 9

Insert Sort (

1 3 4 5 7 8 9

i

1 3 4 5 7 8 9

j


1 3 4 5 7 8 91 3 4 5 7 8 9

Insert Sort (

1 3 4 5 7 8 9

i

1 3 4 5 7 8 9

j


1 3 4 5 7 8 91 3 4 5 7 8 9

Insert Sort (

1 3 4 5 7 8 91 3 4 5 7 8 9


1 3 4 5 7 8 91 3 4 5 7 8 9

Mergesort

� Ordena inicialmente subou 2 e recursivamente dobra esse tamanho até ordenar o vetor total de tamanho N

� Baseia-se no merge de dois vetores ordenadosBaseia-se no merge de dois vetores ordenados

Mergesort

Ordena inicialmente sub-vetores de tamanho 1 ou 2 e recursivamente dobra esse tamanho até ordenar o vetor total de tamanho N

se no merge de dois vetores ordenadosse no merge de dois vetores ordenados

Merge de dois vetores ordenados

� Dados dois vetores V1 e V2, já ordenados, o merge cria um outro vetor V ordenado com os elementos de V1 e V2

local i,j,k = 1,1,1

for k=1,#v1+#v2 do

if j>#v2 then v[k]=v1[i]; i=i+1

else if i>#v1 then v[k]=v2[j]; j=j+1

else if v1[i]<=v2[j] then

else v[k]=v2[j]; j=j+1 end

end

Merge de dois vetores ordenados

Dados dois vetores V1 e V2, já ordenados, o cria um outro vetor V ordenado com os

v[k]=v1[i]; i=i+1

v[k]=v2[j]; j=j+1

then v[k]=v1[i]; i=i+1

end

Merge de dois vetores

1 3V1=

i

j

5 7V2=

V= 1

k


3 7 18 20

7 8 11 13


1 3V1=

i

j

5 7V2=

V= 1 3

k


3 7 18 20

7 8 11 13


1 3V1=j

5 7V2=

V= 1 3 5

k


3 7 18 20

i

7 8 11 13


1 3V1=j

5 7V2=

V= 1 3 5 7

k


3 7 18 20

i

7 8 11 13


1 3V1=j

5 7V2=

V= 1 3 5 7


3 7 18 20

i

7 8 11 13

7

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8 11

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8 11 13

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8 11 13 18

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8 11 13 18 20

k


1 3V1=

5 7V2=

V= 1 3 5 7


3 7 18 20

i

j

7 8 11 13

7 8 11 13 18 20

k

Mergesort

1 9 8 5 3 7 4

Mergesort

1 9 8 5 3 7 4

Mergesort

1 9 8 5 3 7 4

1 9 8 5

Mergesort

1 9 8 5 3 7 4

3 7 4

Mergesort

1 9 8 5 3 7 4

1 9 8 5

1 9 8 51 9 8 5

Mergesort

1 9 8 5 3 7 4

3 7 4

Mergesort

1 9 8 5 3 7 4

1 9 8 5

1 9 5 81 9 5 8

Mergesort

1 9 8 5 3 7 4

3 7 4

Mergesort

1 9 8 5 3 7 4

1 5 8 9

Mergesort

1 9 8 5 3 7 4

3 7 4

Mergesort

1 9 8 5 3 7 4

1 5 8 9

Mergesort

1 9 8 5 3 7 4

3 7 4

Mergesort

1 9 8 5 3 7 4

1 5 8 9

Mergesort

1 9 8 5 3 7 4

3 7 4

3 7 43 7 4

Mergesort

1 9 8 5 3 7 4

1 5 8 9

Mergesort

1 9 8 5 3 7 4

3 7 4

3 7 43 7 4

Mergesort

1 9 8 5 3 7 4

1 5 8 9

Mergesort

1 9 8 5 3 7 4

3 4 7

Mergesort

1 3 4 5 7 8 9

Mergesort

1 3 4 5 7 8 9

Mergesort -

1 9 8 5 3 7 4

1 9 8 5

1 9 8 51 9 8 5

- operações

1 9 8 5 3 7 4

3 7 4

3 7 43 7 4

Mergesort -

1 9 8 5 3 7 4

1 9 8 5

1 9 8 51 9 8 5

Total de operações:N * log

N operações em cada nível

- operações

1 9 8 5 3 7 4

3 7 4

3 7 4

log2 N

níveis

3 7 4

Total de operações:N * log

2 N

N operações em cada nível

Heapsort

� Ordenação baseada na estrutura de dados heap

� A heap é um vetor que pode ser visto como uma árvore binária completa

� Cada nó da árvore equivale a um valor no vetor

Heapsort

Ordenação baseada na estrutura de dados

é um vetor que pode ser visto como uma árvore binária completa

Cada nó da árvore equivale a um valor no vetor

Primitivas da Heap

� length(V)

� número de elementos no vetor V

� heap-size(V)

� número de elementos da � número de elementos da vetor V

Primitivas da Heap

número de elementos no vetor V

número de elementos da heap armazenados no número de elementos da heap armazenados no

Vetor Heap – primitivas de árvore

� parent(i)

� return i/2

� left(i)

� return 2i� return 2i

� right(i)

� return 2i+1

primitivas de árvore

Heap como um vetor

1 9 8 5

1

9

5 3

Heap como um vetor

5 3 7 4

1

8

7 4

Propriedade da Heap

� Para cada nó i que não seja a raiz, então:

� V[ parent(i) ] >= V[i]

� Exemplo:

99

5

1 3

Propriedade da Heap

Para cada nó i que não seja a raiz, então:

99

8

7 4

Primitiva Heapify

� Função para manter a propriedade da heapfunction heapify(V, i)

l = left(i)

r = right(i)

if l<=heap-size(V) and V[l]>V[i] if l<=heap-size(V) and V[l]>V[i] else largest = i end

if r<=heap-size(V) and V[r]>V[largest] then largest=r end

if largest != i thenV[i], V[largest] = V[largest], V[i]heapify(V, largest)

end

end

Primitiva Heapify

Função para manter a propriedade da heap

V[l]>V[i] then largest = lV[l]>V[i] then largest = l

V[r]>V[largest]

V[i], V[largest] = V[largest], V[i]

Construindo uma Heap

� Primitiva que constrói uma vetor de N elementos

function build_heap

heap-size(V) = lengthheap-size(V) = length

for i=length(V)/2,1,

heapify(V,i)

end

end


Primitiva que constrói uma heap a partir de um

build_heap(V)

length(V) -- #Vlength(V) -- #V

(V)/2,1,-1 do


1 9 8 5

1

9

5 3


5 3 7 4

1i

8

7 4

heapify


1 9 8 5

1i

9

5 3

heapify


5 3 7 4

1

8

7 4


1 9 8 5

1i

9

5 3

i


5 3 7 4

1i

heapify

8

7 4

i


9 1 8 5

9i

1

5 3

iheapify


5 3 7 4

9i

8

7 4

i


9 5 8 1

9i

5

1 3

i

heapify


1 3 7 4

9i

8

7 4

i


9 5 8 1

9

5

1 3


1 3 7 4

9

8

7 4

Heapsort

function heapsort(V)

for i=length(V),2,

V[1], V[i] = V[i], V[1]

heap-size(V) = heap-size(V) =

1

heapify(V,1)

end

end

Heapsort

heapsort(V)

(V),2,-1 do

V[1], V[i] = V[i], V[1]

(V) = heap-size(V)-(V) = heap-size(V)-

(V,1)

Heapsort

9 5 8 1

9

5

1 3

Heapsort

1 3 7 4

9

8

7 4

i

Heapsort

4 5 8 1

4

5

1 3

Heapsort

1 3 7 9

4 heapify

8

7 9

i

Heapsort

8 5 4 1

8

5

1 3

Heapsort

1 3 7 9

8

4

7 9

iheapify

Heapsort

8 5 7 1

8

5

1 3

Heapsort

1 3 4 9

8

7

4 9

i

heapify

Heapsort

8 5 7 1

8

5

1 3

Heapsort

1 3 4 9

8

7

4 9

i

Heapsort

4 5 7 1

4

5

1 3

Heapsort

1 3 8 9

4 heapify

7

8 9

i

Heapsort

7 5 4 1

7

5

1 3

Heapsort

1 3 8 9

7

4

8 9

iheapify

Heapsort

7 5 4 1

7

5

1 3

i

Heapsort

1 3 8 9

7

4

8 9

Heapsort

3 5 4 1

3

5

1 7

i

Heapsort

1 7 8 9

3 heapify

4

8 9

Heapsort

5 3 4 1

5

3

1 7

iheapify

Heapsort

1 7 8 9

5

4

8 9

Heapsort

5 3 4 1

5

3

1 7

i

Heapsort

1 7 8 9

5

4

8 9

Heapsort

1 3 4 5

1

3

5 7

i

Heapsort

5 7 8 9

1 heapify

4

8 9

Heapsort

4 3 1 5

4

3

5 7

i

Heapsort

5 7 8 9

4

1

8 9

heapify

Heapsort

4 3 1 5

4

3

5 7

Heapsort

5 7 8 9

4i

1

8 9

i

Heapsort

1 3 4 5

1

3

5 7

Heapsort

5 7 8 9

1 heapify

i

4

8 9

i

Heapsort

3 1 4 5

3

1

5 7

heapify

Heapsort

5 7 8 9

3i

4

8 9

i

Heapsort

3 1 4 5

3i

1

5 7

i

Heapsort

5 7 8 9

3

4

8 9

Heapsort

1 3 4 5

1i

3

5 7

i

Heapsort

5 7 8 9

1 heapify

4

8 9

Heapsort

1 3 4 5

1

3

5 7

Heapsort

5 7 8 9

1

4

8 9

Operações do Heapsort

1 3 4 5

1

3

5 7

N-1 (i varia de 1 a N


5 7 8 9

1

4

8 9

log2N

(heapify –depende da

altura da heap)

(i varia de 1 a N-1)


1 3 4 5

1Total de operações:

3

5 7

N-1 (i varia de 1 a N

operações:(N-1) * log

2N


5 7 8 9

1

4

8 9

log2N

(heapify –depende da

altura da heap)

(i varia de 1 a N-1)

Quicksort

� Ordena o vetor particionando recursivamente

� A cada iteração, localiza a posição final de um elemento aleatório (pivôem duas partes para prosseguir a ordenaçãoem duas partes para prosseguir a ordenação

Quicksort

Ordena o vetor particionando recursivamente

A cada iteração, localiza a posição final de um pivô) e subdivide o vetor

em duas partes para prosseguir a ordenaçãoem duas partes para prosseguir a ordenação

Partição

� Localiza a posição final do aleatório do vetor) e divide o vetor em duas partes, garantindo:

� Todos os elementos à esquerda do pivô são menores ou iguais a elemenores ou iguais a ele

� Todos os elementos à direita do pivô são que ele

Partição

Localiza a posição final do pivô (um elemento aleatório do vetor) e divide o vetor em duas

Todos os elementos à esquerda do pivô são a elea ele

Todos os elementos à direita do pivô são maiores

Partiçãofunction partition(V, left, right)

pivot = V[left]i = left-1

j = right+1while true do

repeat j=j-1 untilrepeat i=i+1 untilrepeat i=i+1 until

if i<j thenV[i], V[j] = V[j], V[i]

else

return jend

end

end

Partiçãopartition(V, left, right)

until V[j]<=pivotuntil V[i]>=pivotuntil V[i]>=pivot

V[i], V[j] = V[j], V[i]

Quicksort

function quicksort(V, left, right)

if left<right then

middle = partition

quicksort(V, left, middle)(V, left, middle)

quicksort(V, middle+1, right)

end

end

Quicksort

quicksort(V, left, right)

partition(V, left, right)

(V, left, middle)(V, left, middle)

(V, middle+1, right)

Quicksort - quicksort

5 9 8 11 2 3 4 5 6 7

quicksort(1,7)

1 3 7 41 2 3 4 5 6 7

Quicksort - partition

5 9 8 1i

partition(1,7)

1 3 7 4j


5 9 8 1i

until V[j]<=5 ?

partition(1,7)

1 3 7 4j

until V[j]<=5 ?


5 9 8 1i

until V[i]>=5 ?

partition(1,7)

1 3 7 4j

until V[i]>=5 ?


4 9 8 1i

V[i], V[j] = V[j], V[i]

partition(1,7)

1 3 7 5j

V[i], V[j] = V[j], V[i]


4 9 8 1i

until V[j]<=5 ?

partition(1,7)

1 3 7 5jj

until V[j]<=5 ?


4 9 8 1i

until V[j]<=5 ?

partition(1,7)

1 3 7 5jj

until V[j]<=5 ?


4 9 8 1i

until V[i]>=5 ?

partition(1,7)

1 3 7 5jj

until V[i]>=5 ?


4 3 8 1i

V[i], V[j] = V[j], V[i]

partition(1,7)

1 9 7 5jj

V[i], V[j] = V[j], V[i]


4 3 8 1i

until V[j]<=5 ?

partition(1,7)

1 9 7 5jj

until V[j]<=5 ?


4 3 8 1i

until V[i]>=5 ?

partition(1,7)

1 9 7 5jj

until V[i]>=5 ?


4 3 1 8i

V[i], V[j] = V[j], V[i]

partition(1,7)

8 9 7 5jj

V[i], V[j] = V[j], V[i]


4 3 1 8i

jjjj

until V[j]<=5 ?

partition(1,7)

8 9 7 5

until V[j]<=5 ?


4 3 1 8i

jjjj

until V[i]>=5 ?

partition(1,7)

8 9 7 5i

until V[i]>=5 ?


4 3 1 8middle

4 3 14 3 1quicksort(1,3)

quicksort(1,7)

8 9 7 5

8 9 7 58 9 7 5quicksort(4,7)


4 31 2 3

quicksort(1,3)

3 11 2 3


4 3

i

partition(1,3)

3 1

j


4 3

i

until V[j]<=4 ?

partition(1,3)

3 1

j

until V[j]<=4 ?


4 3

i

until V[i]>=4 ?

partition(1,3)

3 1

j

until V[i]>=4 ?


1 3

i

V[i], V[j] = V[j], V[i]

partition(1,3)

3 4

j

V[i], V[j] = V[j], V[i]


1 3

i j

until V[j]<=4 ?

partition(1,3)

3 4

until V[j]<=4 ?


1 3

i

j

i

until V[i]>=4 ?

partition(1,3)

3 4

until V[i]>=4 ?


1 3

j

until V[i]>=4 ?

partition(1,3)

3 4

ii

until V[i]>=4 ?


1 3

middle

partition(1,3)

3 4

Documents

Projeto e Análise de Algoritmos - DEINF/UFMAcsalles/paa/paa_01_ordenacao.pdf · Projeto e Análise Aula 1: Algoritmos Prof. Carlos de Terças-feiras , 8h20 ... algoritmo. Como detecto