Pesquisa e Ordenação - Aula 07 - Métodos de Ordenação (Bin sort - Bucket sort)

# Pesquisa e Ordenação #Aula 07 – Métodos de Ordenação

(Bin Sort - Bucket Sort)

Prof. Leinylson Fontinele Pereira

Na aula anterior...

Métodos de Ordenação# Quick Sort

09:21 Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

O que vamos aprender?

Métodos de Ordenação# Bucket Sort

09:21 Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Vamos começar?

09:21 4Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

09:21 5

Ordenação comBucket Sort

Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Pressupõe que a entrada consiste em números inteirosdistribuídos uniformemente sobre um intervalo

Ou seja, há um limite nos valores das chaves.

O intervalo é então dividido em 𝑛 subintervalos detamanhos iguais, os chamados buckets (baldes)

Cada chave vai para o balde correspondente à suafaixa de valor

Ordenação com Bucket Sort

09:20Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Complexidade:𝑂(𝑛)

Quantidade de dados:

Muitos, porém, com valores limitados.

Um Bucket Sort com apenas dois buckets é na verdade oQuicksort (com pivoteamento ruim).

Estabilidade e Adaptabilidade

Dependem do algoritmo de ordenação interna dos buckets.

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

A lista de idades é: 41, 15, 17, 32, 18, 28, 77 𝑒 54

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

A lista de idades é: 41, 15, 17, 32, 18, 28, 77 𝑒 54

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

A lista final será: 15, 17, 18, 28, 32, 41, 54, 77

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Cada balde é posteriormente ordenado, isoladamente dos demais

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Considerando o limite [0,1), e chaves com dois dígitosdecimais, determinamos o número de baldes como:

N = 10 (0, …9) A função para determinação do índice balde correto é

𝐵[ 𝑛 ∗ 𝐴[𝑖] ]

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

𝐴 = (0.5, 0.1, 0.3, 0.4, 0.3, 0.2, 0.1, 0.1, 0.5, 0.4, 0.5)

Lista ordenada

0.1, 0.1, 0.1, 0.2, 0.3, 0.3, 0.4, 0.4, 0.5, 0.5, 0.5

Bucket

A

1 2 3 4 5 6

.74 .17 .26 .72 .39 .21

Bucket: Loop 1

A

1 2 3 4 5 6

.74 .17 .26 .72 .39 .21

B

0 1 2 3 4 5

n=6

Bucket: Loop 2

A

1 2 3 4 5 6

.17 .26 .72 .39 .21

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.74 ]=B[ 4.44 ]=B[4]

Para n=6, i=1

.74

Bucket: Loop 2

A

1 2 3 4 5 6

.74 .26 .72 .39 .21

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.17 ]=B[ 1.02 ]=B[1]

Para n=6, i=2

.17

.74

Bucket: Loop 2

A

1 2 3 4 5 6

.74 .17 .72 .39 .21

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.26 ]=B[ 1.56 ]=B[1]

Para n=6, i=3

.74

.26

.17

Bucket: Loop 2

A

1 2 3 4 5 6

.74 .17 .26 .39 .21

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.72 ]=B[ 4.32 ]=B[4]

Para n=6, i=4

.74

.72

.17.26

Bucket: Loop 2

A

1 2 3 4 5 6

.74 .17 .26 .72 .21

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.39 ]=B[ 2.34 ]=B[2]

Para n=6, i=5

.74

.39

.17.26

.72

Bucket: Loop 2

A

1 2 3 4 5 6

.74 .17 .26 .72 .39

B

0 1 2 3 4 5

B[ n A[i] ] = B[ 6X.94 ]=B[ 5.64 ]=B[5]

Para n=6, i=6

.74

.94

.17.26

.72.39

Bucket: Fim do Loop 2

A

1 2 3 4 5 6

.74 .17 .26 .72 .39 .94

B

0 1 2 3 4 5

.74.17

.26

.72.39 .94

Bucket: Loop 3

A

1 2 3 4 5 6

.74 .17 .26 .72 .39 .94

B

0 1 2 3 4 5

Aplica insertion sort em cada balde

.17 .26 .72 .74 .94.39

Bucket

A

1 2 3 4 5 6

.74 .17 .26 .72 .39 .94

B

0 1 2 3 4 5

Concatena os baldes em ordem

.17 .26 .72 .74 .94.39

B0 1 2 3 4 5

.17 .26 .39 .72 .74 .94

Saída ordenada

Exemplo - Bucket Sort

.78

.17

.39

.26

.72

.94

.21

.12

.23

.68

0

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

.21

.12 /

.72 /

.23 /

.78

.94 /

.68 /

.39 /

.26

.17

/

/

/

/

A B

Distribuindo dentro dos buckets

Exemplo - Bucket Sort0

1

2

3

4

5

6

7

8

9

.23

.17 /

.78 /

.26 /

.72

.94 /

.68 /

.39 /

.21

.12

/

/

/

/

Ordenando cada bucket

Exemplo - Bucket Sort

.17.12 .23 .26.21 .39 .68 .78.72 .94 /

Vetor ordenado

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Ordenação com Bucket Sort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Concluindo...

09:36 45Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Teorema do macaco infinito

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

BozoSort (Bogo Sort)

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

BozoSort

09:36Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Nesta aula aprendemos...Métodos de Ordenação

# Bucket Sort

09:36 Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Na próxima aula veremos...Métodos de Ordenação

# Shell Sort

09:36 Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Material: https://sites.google.com/site/leinylsonnassau

09:36

Material baseado nas aulas de:

MD. Shakhawat Hossain, Student of Computer Science & Engineering Dept. University of Rajshahi

Pesquisa e Ordenação: Aula 07 – Métodos de Ordenação (Bin Sort - Bucket Sort)

Alguma Dúvida?

09:36

Até a próxima aula...

leinylson@gmail.com