04_Algoritmos de Ordenacao por Comparacao 01

Prévia do material em texto

1
Estrutura de Dados e 
Algoritmos
1
Algoritmos de Ordenação por
Comparação - I
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Contexto
2
2
The Maggie Sort
3 http://www.youtube.com/watch?v=Zybl598sK24
Ordenação
4
� Uma das tarefas mais fundamentais e 
extensivamente usadas na computação:
� Bancos de dados, compiladores, interpretadores, 
sistemas operacionais, etc.
� Ordenação é o processo de arranjar um conjunto de 
informações semelhantes em ordem crescente ou 
decrescente
� Diversos algoritmos
� Ordenação por comparação
� Ordenação em tempo linear
3
Algoritmo In-place
5
� A ordenação é feita no mesmo local onde os dados 
são armazenados. 
� No máximo precisa de memória extra de tamanho 
constante
Algoritmo Estável
6
� Um algoritmo de ordenação é estável se dados dois 
elementos R e S com a mesma chave, se R aparece 
antes de S na lista original, R aparecerá antes de S 
na lista ordenada final
� Exemplo:
10(Carlos) 2(Débora) 7(João) 7(José)
2(Débora) 7(João) 7(José) 10(Carlos)
4
Bubble Sort
7
Bubble Sort
8
� O bubble sort, ou ordenação por flutuação 
(literalmente "por bolha"), é um algoritmo de 
ordenação dos mais simples. A idéia é percorrer o 
vetor diversas vezes, a cada passagem fazendo 
flutuar para o topo o maior elemento da sequência.
� As trocas acontecem com o elemento subsequente 
� Exemplo:
[8,4,7,1]
[4,8,7,1]
[4,7,8,1]
[4,7,1,8]
[4,7,1,8]
[4,7,1,8]
[4,1,7,8]
[4,1,7,8]
[1,4,7,8]
[1,4,7,8]
Animação
5
Bubble Sort
9
� Exercício:
� Ordene a lista a seguir utilizando o bubble sort
� 21, 23, 2, 34, 245, 33, 66
Bubble Sort
10
� Como seria o algoritmo do Bubble Sort?
SWAP(A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
BUBBLE-SORT( A) {
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j] > A[j+1]) {
swap(A, j, j+1)
}
}
}
}
6
Bubble Sort
11
� Qual o tempo do Bubble Sort no pior caso?
BUBBLE-SORT( A) {
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j] > A[j+1]) {
swap(A, j, j+1)
}
}
}
}
)(
22
)1()( 2
21
1
n
nnnninT
n
i
Θ=−=−==∑
−
=
n – 1 iterações
n – 2 iterações
n – 3 iterações
…
1 iteração
Bubble Sort
12
� Qual o tempo do Bubble Sort no pior caso?
n – 1 iterações
n – 2 iterações
n – 3 iterações
…
1 iteração
BUBBLE-SORT( A) {
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j] > A[j+1]) {
swap(A, j, j+1)
}
}
}
}
)(
22
)1()( 2
21
1
n
nnnninT
n
i
Θ=−=−==∑
−
=
O que 
acontece no 
melhor
caso?
7
Bubble Sort
13
� O que esse algoritmo faz?
XXXXXX(A) {
n = length(A) 
for i← 1 to n-1 {
for j← n-1 to i {
if ( A[j-1] > A[j] ) {
swap(A, j-1, j)
}
}
}
}
Bubble Sort
14
� O que esse algoritmo faz?
YYYYYYYY(A) {
swapped = true;
n = length(A)
while swapped {
swapped = false;
for i← 1 to n-2 {
if (A[i] > A[i+1]) {
swap(A, i, i+1)
swapped = true
}
}
}
}
8
Características
15
� Fácil de implementar
� Fácil de entender
� In place: não precisa de espaço extra
� Stable: preserva a ordem
� Pode ser útil para valores de n pequenos
� Número alto
� comparações
� Swap (trocas) O(n2)
� Muito ruim na prática
“Bubble sort seems to have 
nothing to recommend it.” 
[Donald Knuth]
Selection Sort
16
9
Selection Sort
17
� Lógica do selection sort:
� Encontre o menor elemento da lista
� Troque com o primeiro elemento da lista
� Faça o processo novamente para o restante da lista, 
começando da próxima posição
� Exemplo:
[8,4,7,1]
[1,4,7,8]
[1,4,7,8]
[1,4,7,8]
[1,4,7,8]
[1,4,7,8]
Animação
Selection Sort
18
� Exercício:
� Ordene a lista a seguir utilizando o selection sort
� 21, 23, 2, 34, 245, 33, 66
10
Selection Sort
19
� Como seria o algoritmo do Selection Sort?
SELECTION-SORT(A) {
n = length(A) 
for i ← 1 to n-1 {
min ← i 
for j ← (i + 1) to n {
if A[j] < A[min] {
min ← j 
}
}
swap (A, i, min)
}
}
Selection Sort
20
� Qual o tempo do Selection Sort no pior caso?
SELECTION-SORT(A) {
n = length(A) 
for i ← 1 to n-1 {
min ← i 
for j ← (i + 1) to n {
if A[j] < A[min] {
min ← j 
}
}
swap (A, i, min)
}
}
11
Selection Sort
21
� Qual o tempo do Selection Sort no pior caso?
SELECTION-SORT(A) {
n = length(A) 
for i ← 1 to n-1 {
min ← i 
for j ← (i + 1) to n {
if A[j] < A[min] {
min ← j 
}
}
swap (A, i, min)
}
}
O que acontece 
no melhor caso?
2..n (n – 1) iterações
3..n (n – 2) iterações
4..n (n – 3) iterações
… …
n..n 1 iteração
)(
22
)1()( 2
21
1
n
nnnninT
n
i
Θ=−=−==∑
−
=
Selection Sort
22
� O que esse algoritmo faz?
XXXXXX-SORT(A) {
n = length(A) 
for i ← n downto 2 {
m ← i 
for j ← 1 to i {
if A[j] > A[m] {
m ← j 
}
}
swap (A, i, m)
}
}
12
Características
23
� Fácil de implementar
� Fácil de entender
� In place: não precisa de espaço extra
� Stable 
� Depende de como é feito o swap 
� Pode ser útil para valores de n pequenos
� Melhor que o bubble sort (tem menos trocas) mas 
perde para o insertion sort
� Menos swap (trocas)
Insertion Sort
24
13
Insertion Sort
25
� Lógica do insertion sort: similar à ordenação de 
cartas um baralho com a seguinte idéia:
� Coloque todas as cartas que deseja ordenar na mão 
direita;
� Pegue uma carta com a mão direita e coloque na mão 
esquerda;
� Faça isso para as demais cartas colocando-as de forma 
ordenada na mão esquerda. 
Insertion Sort
26
5
5
1
1
7
7
9
9
6
6
Como ordenar as cartas acima?
14
Insertion Sort
27
5
5
1
1
9
9
7
7
6
6
1
1
5
5
9
9
7
7
6
6
Insertion Sort
28
15
1
1
5
5
9
9
7
7
6
6
Insertion Sort
29
1
1
5
5
7
7
9
9
6
6
Insertion Sort
30
16
1
1
5
5
7
7
9
9
6
6
Insertion Sort
31
Animação
Insertion Sort
32
� Exercício:
� Ordene a lista a seguir utilizando o insertion sort
� 21, 23, 2, 34, 245, 33, 66
17
Insertion Sort
33
� Como seria o algoritmo do Insertion Sort?
INSERTION-SORT(A) {
n = length(A) 
for j ←2 to n {
key ←A[ j]
i ←j –1
while i > 0 and A[i] > key {
A[i+1] ← A[i]
i ←i –1
}
A[i+1] = key
}
}
Insertion Sort
34
� Como seria o algoritmo do Insertion Sort?
INSERTION-SORT(A) {
n = length(A) 
for j ←2 to n {
key ←A[ j]
i ←j –1
while i > 0 and A[i] > key {
A[i+1] ← A[i]
i ←i –1
}
A[i+1] = key
}
}
1..1 1 iteração
2..1 2 iterações
3..1 3 iterações
… …
(n-1)..1 (n – 1) iterações
)(
22
)1()( 2
21
1
n
nnnninT
n
i
Θ=−=−==∑
−
=
18
Insertion Sort
35
� O que esse algoritmo faz?
XXXXXXXX(A) {
n = length(A);
endOfOrderedList = 1;
while(endOfOrderedList < n){
int next = A[endOfOrderedList + 1];
for j ← endOfOrderedList downto 1 {
if (next < A[j]) {
swap(A, j, j+1);
}
}
endOfOrderedList++;
}
}
Características
36
� Fácil de implementar
� Fácil de entender
� In place: não precisa de espaço extra
� Stable
� Muita escrita (troca) e menos comparações
� Melhor Caso
� O(n)
� Caso Médio
� O(n2/4)
� Eficiente para valores de n pequenos
� Melhor do que bubble e selection sort
19
Outros Algoritmos de Ordenação por
Comparação
37
Gnome Sort
38
� Inventor: Hamid Sarbazi-Azad (2000)
� Idéia:
� Adota um pivot (que tenha anterior);
� Normalmenteo 2° elemento;
� Olha para o anterior;
� Se o pivot e o anterior estão na ordem correta então
incrementa o pivot.
� Se eles não estão na ordem correta então troca eles e 
decrementa o pivot;
� Condições: se não existe anterior ao pivot então anda
para frente (ao invés de decrementar). Se não tem 
próximo, então termina.
20
Gnome Sort
39
� Como seria o algoritmo?
Array Atual Ação
[5,3,2,4] A[pos] < A[pos-1], swap.
pos <= 2, incrementa pos
[3,5,2,4] A[pos] < A[pos-1], swap
pos > 2, decrementa pos
[3,2,5,4] A[pos] < A[pos-1], swap 
pos <= 2, incrementa pos
[2,3,5,4] A[pos] >= A[pos-1], incrementa pos.
[2,3,5,4] A[pos] < A[pos-1], swap
pos > 2, decrementa pos
[2,3,4,5] A[pos] >= A[pos-1], incrementa pos.
[2,3,4,5] A[pos] >= A[pos-1], incrementa pos.
[2,3,4,5] pos > length(A), fim !
Gnome Sort
40
� Como seria o algoritmo?
� Animação
21
Gnome Sort
41
� Como seria o algoritmo?
GNOME-SORT(A) {
pos := 2 //começando com 1 
while pos <= length(A) { //enquanto não atinge o último elemento
if (A[pos] >= A[pos-1]) { //se está na ordem correta
pos := pos + 1 
} else {
swap (A, pos, pos-1) 
if (pos > 2) { //se maior que 2, decrementa
pos := pos - 1 
} else { //se menor ou igual a 2, incrementa
pos := pos + 1 
} 
} 
}
}
Gnome Sort
42
� Análise
� Pior caso = O(n2)
� Melhor caso = O(n)
� Caso médio = O(n2)
22
Comb Sort
43
� Variação do bubble sort
� Inventor Wlodzimierz Dobosiewicz (1980)
� Focado em melhorar a entrada do bubble sort antes 
de aplicá-lo (bubble compara elementos de distância 
1)
� Idéia:
� A distância começa por gap = tamanho/fator (fator=1.25)
� A entrada é ordenada com as trocas considerando 
elementos distanciados por gap
� gap é atualizado (gap = gap/fator) até 1
� Quando gap=1 combo sort continua até o array estar todo 
ordenado
� Animação
Comb Sort
44
� Como seria o algoritmo?
23
Comb Sort
45
� Como seria o algoritmo?
COMB-SORT(A) 
gap := length(A) //initialize gap size 
while (gap > 1 and swaps) {
gap := gap / 1.25 
if (gap<1) gap := 1 
i := 1
swaps := false
while (i + gap <= length(A) ) {
if ( A[i] > A[i+gap] ) { //faz trocas considerando distancia = gap
swap(A, i, i+gap) 
swaps := true // ocorreu troca 
}
i := i + 1 
}
}
}
Comb Sort
46
� Análise
� Pior caso = O(n2)
� Melhor caso = O(n)
24
Questões de Implementação
47
� Como desenvolver/adaptar os algoritmos de 
ordenação vistos para ordenar tipos genéricos?
� Ao invés de trabalhar com inteiros precisamos
trabalhar com um tipo T.
Questões de Implementação
48
SWAP(A, int i, int j) {{ // A é uma lista de itens comparáveis
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
BUBBLE-SORT( A) { // A é uma lista de itens comparáveis
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j] > A[j+1]) {
swap(A[j]), A[j+1])
}
}
}
}
25
Questões de Implementação
49
SWAP(A, int i, int j) {{ // A é uma lista de itens Comparable
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
BUBBLE-SORT( A) { // A é uma lista de itens Comparable
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j] > A[j+1]) {
swap(A[j]), A[j+1])
}
}
}
}
Questões de Implementação
50
SWAP(A, int i, int j) {{ // A é uma lista de itens Comparable
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
BUBBLE-SORT( A) { // A é uma lista de itens Comparable
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n – i {
if (A[j].compareTo(A[j+1]) > 0) {
swap(A[j]), A[j+1])
}
}
}
}
26
Questões de Implementação
51
� Exemplo: bubblesort
� Como implementar o bubblesort considerando apenas 
um “pedaço” do vetor a ser ordenado?
bubbleSort( A, int leftIndex, int rightIndex ) {
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n-i {
if (A[j].compareTo(A[j+1]) > 0){
swap(A,j,j+1)
}
}
}
}
Questões de Implementação
52
� Exemplo: bubblesort
� Como implementar o bubblesort considerando apenas 
um “pedaço” do vetor a ser ordenado?
bubbleSort( A, int leftIndex, int rightIndex ) {
n = length(A) 
for i ← 1 to n – 1 {
for j ← 1 to n-i {
if (A[j].compareTo(A[j+1]) > 0){
swap(A,j,j+1)
}
}
}
}
Adaptar para os novos limites!