Algoritmos de Ordenacao

Marcelo K. Albertini

7 de Maio de 2014

Aula de hoje

Nesta aula veremos:

Ordenacao interna

Complexidade

2/1

Revisao

Conceitos

Vetor: int vetor[] = 5, 1, 7, 3, 0;

3/1

Revisao

Conceitos

Vetor: int vetor[] = 5, 1, 7, 3, 0;

Variavel ındice: posicao para acesso de elemento

3/1

Revisao

Conceitos

Vetor: int vetor[] = 5, 1, 7, 3, 0;

Variavel ındice: posicao para acesso de elemento

Variavel auxiliar: armazenamento temporario

3/1

Revisao

Conceitos

Vetor: int vetor[] = 5, 1, 7, 3, 0;

Variavel ındice: posicao para acesso de elemento

Variavel auxiliar: armazenamento temporario

util para troca de posicao de elementos do vetor

3/1

Ordenacao interna

ordenar em memoria

Pre-condicoes: vetor em memoria principal, inicializado comelementos

4/1

Ordenacao interna

ordenar em memoria

Pre-condicoes: vetor em memoria principal, inicializado comelementos

Pos-condicoes: vetor com elementos em ordem crescente (oudecrescente)

4/1

Ordenacao interna

ordenar em memoria

Pre-condicoes: vetor em memoria principal, inicializado comelementos

Pos-condicoes: vetor com elementos em ordem crescente (oudecrescente)

Como fica ordenado?

4/1

Vetores e Ordenacao: exemplos

Exemplos:

Numeros inteiros ou ponto flutuante

5/1

Vetores e Ordenacao: exemplos

Exemplos:

Numeros inteiros ou ponto flutuante

Vetor de strings

5/1

Vetores e Ordenacao: exemplos

Exemplos:

Numeros inteiros ou ponto flutuante

Vetor de stringsTipos compostos: necessario definir funcao para comparar

5/1

Vetores e Ordenacao: exemplos

Exemplos:

Numeros inteiros ou ponto flutuante

Vetor de stringsTipos compostos: necessario definir funcao para comparar

int compare(ITEM item1, ITEM item2);

Exemplo

1 i n t compare ( Aluno a ) 2 i f ( t h i s . media > a . media ) 3 r e t u r n 1 ;4 5 e l s e i f ( t h i s . media == a . media ) 6 r e t u r n (−1) ;7 e l s e 8 r e t u r n (0 ) ;9

10

5/1

Algoritmo de ordenacao

Definicao de ordenacao

Sequencia de comparacoes e trocas de posicao entre elementospara obter vetor ordenado.

6/1

Algoritmo de ordenacao

Definicao de ordenacao

Sequencia de comparacoes e trocas de posicao entre elementospara obter vetor ordenado.

Complexidade

Quantas trocas, comparacoes (complexidade de tempo) e variaveisauxiliares (de espaco) sao necessarias?

6/1

Bubblesort - Ordenacao em“bolhas”

Como programar um algoritmo de ordenacao simples?

Ideia

Comparar pares consecutivos de elementos e troca-los de posicaocaso o primeiro seja maior que o segundo.

1 i f ( v e t o r [ i ] > v e t o r [ i +1]) 2 aux = v e t o r [ i ] ;3 v e t o r [ i ] = v e t o r [ i +1] ;4 v e t o r [ i +1] = aux ;5

7/1

Bubblesort - Ordenacao em“bolhas”

Como programar um algoritmo de ordenacao simples?

Ideia

Comparar pares consecutivos de elementos e troca-los de posicaocaso o primeiro seja maior que o segundo.

1 i f ( v e t o r [ i ] > v e t o r [ i +1]) 2 aux = v e t o r [ i ] ;3 v e t o r [ i ] = v e t o r [ i +1] ;4 v e t o r [ i +1] = aux ;5

Variavel auxiliar aux e essencial.

7/1

Primeira iteracao

8/1

Primeira iteracao

8/1

Primeira iteracao

8/1

Primeira iteracao

8/1

Primeira iteracao

8/1

Primeira iteracao

8/1

Primeira iteracao

Maior elemento sempre esta na sua posicao ordenada na primeiraiteracao.

8/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem )

9/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem ) 2 i n t i , i t e r a c a o , aux ;

9/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem ) 2 i n t i , i t e r a c a o , aux ;34 /∗ c o n t r o l e do numero de i t e r a c o e s ( n − 1) ∗/5 f o r ( i t e r a c a o = 0 ; i t e r a c a o < nelem−1; i t e r a c a o++)

9/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem ) 2 i n t i , i t e r a c a o , aux ;34 /∗ c o n t r o l e do numero de i t e r a c o e s ( n − 1) ∗/5 f o r ( i t e r a c a o = 0 ; i t e r a c a o < nelem−1; i t e r a c a o++)6 /∗ r e p e t i c a o i n t e r n a , p e r c o r r e v e t o r ( n − 1) ∗/7 f o r ( i = 0 ; i < nelem − 1 ; i++)

9/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem ) 2 i n t i , i t e r a c a o , aux ;34 /∗ c o n t r o l e do numero de i t e r a c o e s ( n − 1) ∗/5 f o r ( i t e r a c a o = 0 ; i t e r a c a o < nelem−1; i t e r a c a o++)6 /∗ r e p e t i c a o i n t e r n a , p e r c o r r e v e t o r ( n − 1) ∗/7 f o r ( i = 0 ; i < nelem − 1 ; i++)8 i f ( v e t o r [ i ] > v e t o r [ i +1])

9/1

Algoritmo Bubblesort: versao simplificada

1 vo i d b u bb l e s o r t ( i n t v e t o r [ ] , i n t nelem ) 2 i n t i , i t e r a c a o , aux ;34 /∗ c o n t r o l e do numero de i t e r a c o e s ( n − 1) ∗/5 f o r ( i t e r a c a o = 0 ; i t e r a c a o < nelem−1; i t e r a c a o++)6 /∗ r e p e t i c a o i n t e r n a , p e r c o r r e v e t o r ( n − 1) ∗/7 f o r ( i = 0 ; i < nelem − 1 ; i++)8 i f ( v e t o r [ i ] > v e t o r [ i +1])9 /∗ e n e c e s s a r i a uma t r o c a ∗/

10 aux = v e t o r [ i ] ;11 v e t o r [ i ] = v e t o r [ i +1] ;12 v e t o r [ i +1] = aux ;13 14 15 16

9/1

Outras iteracoes

10/1

Limite assintotico de complexidade

Limite assintotico superior O(g(n))

Objetivo: encontrar funcao limitante superior g(n) para representaro“teto”do custo do algoritmo.

11/1

Limite assintotico de complexidade

Limite assintotico superior O(g(n))

Objetivo: encontrar funcao limitante superior g(n) para representaro“teto”do custo do algoritmo.

Bubblesort simplificado

Para n elementos, faz-se n − 1 iteracoes e n − 1 comparacoes emcada iteracao: g(n) = (n − 1)2. Pior caso de numero de trocas:g(n) = n × (n − 1)/2. Entao a complexidade de tempo e O(n2).

11/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

10 wh i l e ( b a l d e s [ j ] > 0 ) 11 ba l d e s [ j ] = ba l d e s [ j ] − 1 ;

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

10 wh i l e ( b a l d e s [ j ] > 0 ) 11 ba l d e s [ j ] = ba l d e s [ j ] − 1 ;12 v e t o r [ i ] = j ;

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

10 wh i l e ( b a l d e s [ j ] > 0 ) 11 ba l d e s [ j ] = ba l d e s [ j ] − 1 ;12 v e t o r [ i ] = j ;13 i = i + 1 ;

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

10 wh i l e ( b a l d e s [ j ] > 0 ) 11 ba l d e s [ j ] = ba l d e s [ j ] − 1 ;12 v e t o r [ i ] = j ;13 i = i + 1 ;14 15 16

12/1

Bucket sort

Ideia: ordenacao de numeros inteiros

Cada elemento e representado por uma posicao em um vetor (umbalde). Conta-se as repeticoes de cada numero.

1 vo i d bucke tSo r t ( i n t [ ] v e to r , i n t max) 23 long [ ] b a l d e s = new long [max+1] ;4 f o r ( i n t i = 0 ; i < v e t o r . l e n g t h ; i++) 5 ba l d e s [ v e t o r [ i ] ]++;6 7 // o l h a r cada ba l d e em ordem e t i r a r os numeros8 i n t i = 0 ;9 f o r ( i n t j = 0 ; j < ba l d e s . l e n g t h ; j++)

10 wh i l e ( b a l d e s [ j ] > 0 ) 11 ba l d e s [ j ] = ba l d e s [ j ] − 1 ;12 v e t o r [ i ] = j ;13 i = i + 1 ;14 15 1617 r e t u r n ( v e t o r ) ;18

12/1

Complexidades

Complexidade de tempo

Como cada numero e avaliado apenas uma vez, o Bucket sort temcomplexidade de tempo O(n).

13/1

Complexidades

Complexidade de tempo

Como cada numero e avaliado apenas uma vez, o Bucket sort temcomplexidade de tempo O(n).

Complexidade de espaco

Somente viavel com inteiros ou poucas casas decimais. Cresce coma faixa de valores consideradas, ou seja, O(10|w |), com |w | sendo otamanho do numero.

13/1

Complexidade de espaco do Bucket sort

Problema do banco: ordenacao de 40 milhoes de numeros

Se 1% das transacoes forem de mais de 1 milhao de reais, entao epossıvel usar 2 algoritmos de ordenacao:

14/1

Complexidade de espaco do Bucket sort

Problema do banco: ordenacao de 40 milhoes de numeros

Se 1% das transacoes forem de mais de 1 milhao de reais, entao epossıvel usar 2 algoritmos de ordenacao:

Para transacoes de ate 1 milhao, usa-se o Bucket sort: 4segundos.

Para transacoes de mais de 1 milhao, pode-se usar o Bubblesort: 2.5 minutos.

14/1

Complexidade de espaco do Bucket sort

Problema do banco: ordenacao de 40 milhoes de numeros

Se 1% das transacoes forem de mais de 1 milhao de reais, entao epossıvel usar 2 algoritmos de ordenacao:

Para transacoes de ate 1 milhao, usa-se o Bucket sort: 4segundos.

Para transacoes de mais de 1 milhao, pode-se usar o Bubblesort: 2.5 minutos.

Balanceamento de complexidades

Bucket sort: complexidade de tempo baixa e complexidade deespaco altaBubble sort: complexidade de tempo alta e complexidade deespaco baixa

14/1

Ordenacao por selecao

Funcionamento

1 seleciona menor elemento de regiao nao ordenada

2 troca o primeiro elemento da regiao pelo menor elemento

3 diminui tamanho da regiao nao ordenada

15/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++)

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;56 f o r ( i n t j = i +1; j < v e t o r . l e n g t h ; j++)

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;56 f o r ( i n t j = i +1; j < v e t o r . l e n g t h ; j++) 7 i f ( v e t o r [ j ] < menor )

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;56 f o r ( i n t j = i +1; j < v e t o r . l e n g t h ; j++) 7 i f ( v e t o r [ j ] < menor ) 8 menorI = j ;9 menor = v e t o r [ j ] ;

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;56 f o r ( i n t j = i +1; j < v e t o r . l e n g t h ; j++) 7 i f ( v e t o r [ j ] < menor ) 8 menorI = j ;9 menor = v e t o r [ j ] ;

10 11

16/1

Algoritmo: ordenacao por selecao

1 vo i d s e l e c t i o n S o r t ( i n t [ ] v e t o r ) 2 f o r ( i n t i = 0 ; i < v e t o r . l eng th −1; i++) 3 i n t menor = v e t o r [ i ] ;4 i n t menorI = i ;56 f o r ( i n t j = i +1; j < v e t o r . l e n g t h ; j++) 7 i f ( v e t o r [ j ] < menor ) 8 menorI = j ;9 menor = v e t o r [ j ] ;

10 11 1213 i n t aux = v e t o r [ i ] ; // t r o c a14 v e t o r [ i ] = menor ;15 v e t o r [ menorI ] = aux ;16 17

16/1

Custo: ordenacao por selecao

Exercıcio 1

Qual e a funcao de custo considerando apenas comparacoes?

Exercıcio 2

Qual e a funcao de custo considerando apenas trocas?

Exercıcio 3: Qual e a complexidade?

Notacao O, Notacao Ω, Notacao Θ

17/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;

18/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;45 f o r ( i n t j = 1 ; j < n ; j++)

18/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;45 f o r ( i n t j = 1 ; j < n ; j++) 6 i n t chave = v e t o r [ j ] ;

18/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;45 f o r ( i n t j = 1 ; j < n ; j++) 6 i n t chave = v e t o r [ j ] ;7 i n t i = j − 1 ;

18/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;45 f o r ( i n t j = 1 ; j < n ; j++) 6 i n t chave = v e t o r [ j ] ;7 i n t i = j − 1 ;89 // p rocu ra l u g a r de i n s e r c a o e d e s l o c a numeros

10 wh i l e ( i >= 0 && ve t o r [ i ] > chave ) 11 v e t o r [ i +1] = v e t o r [ i ] ;12 i = i − 1 ;13

18/1

Algoritmo: ordenacao por insercao

1 vo i d i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;45 f o r ( i n t j = 1 ; j < n ; j++) 6 i n t chave = v e t o r [ j ] ;7 i n t i = j − 1 ;89 // p rocu ra l u g a r de i n s e r c a o e d e s l o c a numeros

10 wh i l e ( i >= 0 && ve t o r [ i ] > chave ) 11 v e t o r [ i +1] = v e t o r [ i ] ;12 i = i − 1 ;13 14 v e t o r [ i +1] = chave ;15 16

18/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

1 2 5 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

1 2 5 6 9 6chave = 91 2 5 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

1 2 5 6 9 6chave = 91 2 5 6 9 6chave = 61 2 5 6 9 6

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

1 2 5 6 9 6chave = 91 2 5 6 9 6chave = 61 2 5 6 9 6

1 2 5 6 9 9

19/1

Algoritmo: ordenacao por insercao

1 i n s e r t i o n S o r t ( i n t [ ] v e t o r ) 23 i n t n = v e t o r . l e n g t h ;4 f o r ( i n t j = 1 ; j<n ; j++)5 i n t chave = v e t o r [ j ] ;6 i n t i = j − 1 ;78 // d e s l o c a numeros9 wh i l e ( i >= 0 &&

10 v e t o r [ i ] > chave ) 1112 v e t o r [ i +1] = v e t o r [ i ] ;13 i = i − 1 ;14 15 // i n s e r e chave16 v e t o r [ i +1] = chave ;17 18

chave = 56 5 2 1 9 6

6 5 2 1 9 6

6 6 2 1 9 6

5 6 2 1 9 6chave = 65 6 2 1 9 6chave = 25 6 2 1 9 6

5 6 6 1 9 6

5 5 6 1 9 6

2 5 6 1 9 6

chave = 12 5 6 1 9 6

2 5 6 6 9 6

2 5 5 6 9 6

2 2 5 6 9 6

1 2 5 6 9 6chave = 91 2 5 6 9 6chave = 61 2 5 6 9 6

1 2 5 6 9 9

1 2 5 6 6 9

19/1

Custo: ordenacao por insercao

Custo e complexidade

Melhor caso, notacao Ω

Pior Caso, notacao O

20/1

Shell Sort

Inventado por Donald Shell em 1959

Primeiro a baixar a complexidade de ordenacao

Ideia

Similar ao Insertion Sort, mas compara uma sequencia deelementos distantes (com distancia variavel) em vez de elementosconsecutivos

21/1

Shell Sort

Inventado por Donald Shell em 1959

Primeiro a baixar a complexidade de ordenacao

Ideia

Similar ao Insertion Sort, mas compara uma sequencia deelementos distantes (com distancia variavel) em vez de elementosconsecutivos

Complexidade empırica

Entre O(n1.2) e O(1.6n1.25)

21/1

Quicksort

Quicksort

Tony Hoare, Moscou, Uniao Sovietica, 1960

Aplicacao original: ordenar dicionario russo-ingles

22/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r )

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e15 inse reNoF im ( x , v e t o rMa i o r e s )

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e15 inse reNoF im ( x , v e t o rMa i o r e s )16

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e15 inse reNoF im ( x , v e t o rMa i o r e s )16 17 q u i c k s o r t ( ve to rMenore s ) // o rdena r os menores18

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e15 inse reNoF im ( x , v e t o rMa i o r e s )16 17 q u i c k s o r t ( ve to rMenore s ) // o rdena r os menores18 q u i c k s o r t ( v e t o rMa i o r e s ) // o rdena r os ma io r e s19

23/1

Pseudo-codigo: quicksort simplificado

1 i n t [ ] q u i c k s o r t ( v e t o r ) 2 i f ( tamanho ( v e t o r ) <= 1) 3 r e t u r n ( v e t o r ) // v e t o r j a o rdenado4 5 // p i v o t e e l emento de r e f e r e n c i a para o rdena r6 p i v o t = e s c o l h e r E r emov e r ( v e t o r )7 // c r i a r v e t o r e s de e l emento s menores e ma io r e s8 ve to rMenore s = new i n t [ tamanho ( v e t o r ) ]9 v e t o rMa i o r e s = new i n t [ tamanho ( v e t o r ) ]

1011 f o r ( x i n v e t o r ) 12 i f ( x <= p i v o t )13 inse reNoF im ( x , ve to rMenore s )14 e l s e15 inse reNoF im ( x , v e t o rMa i o r e s )16 17 q u i c k s o r t ( ve to rMenore s ) // o rdena r os menores18 q u i c k s o r t ( v e t o rMa i o r e s ) // o rdena r os ma io r e s19 r e t u r n ( j u n t a r ( vetorMenores , p i vo t , v e t o rMa i o r e s ) ) ;20

23/1

Escolha do pivot

1 p i v o t = e s c o l h e r E r emov e r ( v e t o r )

custo do algoritmo depende da escolha do pivot

possibilidades

o primeiro/ultimo elementoaleatorioo elemento do meioa mediana entre o primeiro, meio e ultimo

24/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

0 2 2 3 5 5 6

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

0 2 2 3 5 5 6

7 7

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

0 2 2 3 5 5 6

7 7

7 7

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

0 2 2 3 5 5 6

7 7

7 7

0 2 2 3 5 5 6 6 7 7

25/1

Simulacao: pivot – o primeiro elemento

6 7 5 5 2 0 6 2 3 7

5 5 2 0 6 2 3 6 7 7

3 5 2 0 2 5 6

2 2 0 3 5

0 2 2

0 2

0 2

0 2 2

0 2 2 3 5

0 2 2 3 5 5 6

7 7

7 7

0 2 2 3 5 5 6 6 7 7

25/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

2 4 4 5 6 7

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

2 4 4 5 6 7

2 4 4 5 6 7 8

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

2 4 4 5 6 7

2 4 4 5 6 7 8

2 4 4 5 6 7 8 9

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

2 4 4 5 6 7

2 4 4 5 6 7 8

2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 8 9

26/1

Simulacao: pivot – o primeiro elemento – degeneracao

1 2 4 4 5 6 7 8 9

1 9 2 4 4 5 6 7 8

8 2 4 4 5 6 7 9

7 2 4 4 5 6 8

6 2 4 4 5 7

5 2 4 4 6

4 2 4 5

4 2 4

2 4

2 4

2 4 4

2 4 4 5

2 4 4 5 6

2 4 4 5 6 7

2 4 4 5 6 7 8

2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 8 9

26/1

Pivot aleatorio

1 p u b l i c s t a t i c i n t e s c o l h e r P i v o t ( i n t [ ] v e t o r ) 23 Random s o r t e i o = new Random ( ) ;45 r e t u r n ( s o r t e i o . n e x t I n t ( v e t o r . l e n g t h ) ) ;6

27/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

1 2 4 4 5 6

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

1 2 4 4 5 6

8 9

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

1 2 4 4 5 6

8 9

8 9

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

1 2 4 4 5 6

8 9

8 9

1 2 4 4 5 6 7 8 9

28/1

Simulacao: pivot aleatorio evita degeneracao

1 2 4 4 5 6 7 8 9

1 2 4 4 5 6 7 9 8

1 2 6 4 4 5

4 4 5 6

4 4

4 4

4 4 5 6

1 2 4 4 5 6

8 9

8 9

1 2 4 4 5 6 7 8 9

28/1

Pivot mediana

1 p u b l i c s t a t i c i n t e s c o l h e rP i v o tMed i ana ( i n t [ ] v e t o r ) 23 i n t f im = ve t o r . l eng th −1;4 i n t meio = ( i n t ) v e t o r . l e n g t h /2 ;5 i n t comeco = 0 ;67 i f ( v e t o r [ f im ] > v e t o r [ meio ] ) 8 i f ( v e t o r [ meio ] > v e t o r [ comeco ] ) 9 r e t u r n ( meio ) ;

10 e l s e 11 r e t u r n ( comeco ) ;12 13 e l s e 14 i f ( v e t o r [ f im ] > v e t o r [ comeco ] ) 15 r e t u r n ( f im ) ;16 e l s e 17 r e t u r n ( comeco ) ;18 19 20

29/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

6 7

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

6 7

6 7 8

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

6 7

6 7 8

6 7 8 9

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

6 7

6 7 8

6 7 8 9

1 2 4 4 5 6 7 8 9

30/1

Simulacao: pivot mediana

1 2 4 4 5 6 7 8 9

1 2 4 4 5 9 6 7 8

1 2 4 4

1 2 4

1 2 4

1 2 4 4

8 6 7 9

7 6 8

6 7

6 7

6 7 8

6 7 8 9

1 2 4 4 5 6 7 8 9

30/1

Pivot mediana: propriedades

“Implementing Quicksort programs”, Robert Sedgewick

31/1

Pivot mediana: propriedades

“Implementing Quicksort programs”, Robert Sedgewick

Estudos praticos sobre o Quicksort

31/1

Pivot mediana: propriedades

“Implementing Quicksort programs”, Robert Sedgewick

Estudos praticos sobre o Quicksort

Recomenda o uso de pivot mediana

31/1

Pivot mediana: propriedades

“Implementing Quicksort programs”, Robert Sedgewick

Estudos praticos sobre o Quicksort

Recomenda o uso de pivot mediana

Estatisticamente, o custo do Quicksort tende a ser menor paravetores maiores

31/1

Quicksort: versoes

Existem muitas versoes do Quicksort

Em geral eles atuam no vetor original para fazer as particoes

economia de uso de espaco

Existem muitas otimizacoes

“A origem de todo o mal e a otimizacao precoce”, DonaldKnuth

32/1

Custo: Quicksort simplificado

Custo e complexidade

Melhor caso, notacao Ω

altura da arvore de recursao

Pior Caso, notacao O

degeneracao

33/1