Algoritmos de Ordenação

Sumá
Sumário
Algoritmos de Ordenação
Leandro Tonietto
Algoritmos e Estruturas de Dados em C++
Desenvolvimento de Jogos e Entretenimento Digital
[email protected]
http://www.inf.unisinos.br/~ltonietto
Objetivos
Dada uma lista de valores (números) numa
seqüência qualquer, gerar uma nova
seqüência ordenada destes valores.
Portanto, a nova seqüência terá: v1 <= v2
<= ... <= vn
Exemplo:
Dado conjunto de valores V={10, 32,
9, 20, 18, 18}, o conjunto V’ dos
elementos de V ordenados é: V’={9, 10,
18, 18, 20, 32}
Eficiência e Classificaç
Classificação dos Algoritmos de Ordenaç
Ordenação
Para determinar qual é o mais eficiente para determinada
tarefa, inicialmente, se compara algoritmos pela facilidade de
implementação e pelo tempo de execução
Na realidade, análise do tempo depende dos valores de entrada
e da aplicação; pode-se preferir um algoritmo que consuma
menos memória, por exemplo.
Também depende dos recursos disponíveis para execução, ou
seja, o critério “tempo” é subjetivo: o que é considerado para
calcular tempo? Questões de hardware podem interferir da
decisão...
Normalmente, métrica para classificação dos algoritmos é o
número de comparações e trocas de elementos ou chaves.
Objetivos
Métodos de Ordenação
Eficiência e Classificação dos Algoritmos de
Ordenação
Algoritmos Θ(n2) (mais “lentos”)
Algoritmos Θ(nlogn) (mais “rápidos”)
Demo
Trabalho
Referências
Métodos de Ordenaç
Ordenação
Uma das tarefas mais comuns em computação. Muitos
problemas permanecem abertos a espera de algoritmos
de ordenação que resolvam determinada aplicação.
Algoritmos considerados mais simples, com tempo de
Θ(n2) no pior caso, como: InsertionSort,
BubbleSort e SelectionSort.
Algoritmos considerados mais sofisticados, com tempo de
Θ(nlogn), como: MergeSort, QuickSort e
SearchSort.
Uma função comum é swap, que troca
os valores de duas variáveis.
Algoritmos Θ(n2)- Insertion Sort
O algoritmo de ordenação por inserção processa
seqüencialmente uma lista de valores e cada
registro (valor) é inserido na posição correta
numa lista de valores já ordenados.
void insertionSort(array, n){
para i de 1 até n, i++
para j de i até 1, j-se(array[j] < array[j-1])
entao swap(array, j, j-1)
}
Eficiente para poucos registros.
Melhor caso, já ordenado, o tempo é n-1
Pior caso Θ(n2)
1
Algoritmos Θ(n2)- Insertion Sort
Exemplo: dada a lista 42, 20, 17, 13, 28,
14, 23 15
42
20
17
13
28
14
23
15
i=1
i=2
i=3
i=4
i=5
i=6
i=7
20
42
17
13
28
14
23
15
17
20
42
13
28
14
23
15
13
17
20
42
28
14
23
15
13
17
20
28
42
14
23
15
13
14
17
20
28
42
23
15
13
14
17
20
23
28
42
15
13
14
15
17
20
23
28
42
Algoritmos Θ(n2)- Bubble Sort
i=0
i=1
i=2
i=3
i=4
i=5
i=6
13
42
20
17
14
28
15
23
13
14
42
20
17
15
28
23
13
14
15
42
20
17
23
28
13
14
15
17
42
20
23
28
13
14
15
17
20
42
23
28
13
14
15
17
20
23
42
28
13
14
15
17
20
23
28
42
Algoritmos Θ(n2)- Selection Sort
Exemplo da mesma lista:
i=0
42
20
17
13
28
14
23
15
i=1
i=2
i=3
Compara i vezes do último elemento até a iésima posição, trocando valor com anterior caso
v[j] < v[j-i], até i=n.
É um algoritmo simples e mais lento que o
inserção
Serve de base para algoritmos mais sofisticados.
void bubbleSort(array, n){
para i de 0 até n, i++
para j de n até i, j-se(array[j] < array[j-1])
entao swap(array, j, j-1)
}
O tempo de execução é Θ(n2)
Tempo melhor caso = tempo pior caso!!
Algoritmos Θ(n2)- Selection Sort
Procura o próximo menor valor da lista e coloca
na posição atual.
Exemplo da mesma lista:
42
20
17
13
28
14
23
15
Algoritmos Θ(n2)- Bubble Sort
i=4
i=5
i=6
void selectionSort(array, n){
para i de 0 até n-1, i++
k = i;
para j de n-1 enquanto j>i, j-se(array[j] < array[k])
entao k = j;
swap(array, i, k);
}
void selectionSort(array, n){
para i de 0 até n-1, i++
k = i;
para j de n-1 enquanto j>i, j– {
se(array[j] < array[k])
entao k=j;
}
swap(array, i, k);
}
O tempo ainda é Θ(n2).
É um bubble sort! Entretanto o número de swaps
bem menor. Portanto mais eficiente na maioria
das situações.
Algoritmos Θ(nlogn
logn) - MergeSort
Conceitualmente muito simples e tem um bom
tempo de execução (pequeno).
Dividir para conquistar. Divide a lista em duas,
essas duas mais duas e assim por diante até elas
fiquem dois elementos; aí então, ordena-se dois
elementos e retorna ordenando as sublistas.
O tempo de execução não depende do estado de
ordenação dos elementos da lista.
Tempo é medido em Θ(nlogn)
2
Algoritmos Θ(nlogn
logn) - MergeSort
Algoritmos Θ(nlogn
logn) - MergeSort
Algoritmo:
void mergeSort(array, temp, left, right){
meio = (left+right)/2;
se(left==right) retorna;
mergeSort(array, temp, left, meio);
mergeSort(array, temp, meio+1, right);
para i de left ate <= right, i++
temp[i] = array[i];
i1 = left, i2 = meio+1;
para curr de left ate <= right, curr++
se(i1==meio+1) entao array[curr] = temp[i2++];
senao
se(i2 > right) entao array[curr] = temp[i1++];
senao
se(temp[i1]<temp[i2])
entao array[curr] = temp[i1++];
senao array[curr] = temp[i2++];
}
Algoritmos Θ(nlogn
logn) - QuickSort
É o melhor algoritmo para grande maioria dos
casos, pois ele é o mais eficiente na média.
Idéia de dividir o problema em partes menores.
Algoritmo:
1. Elege um número “pivot” e fixa posição k.
(findpivot(array, 0, n))
2. Arranja o array considerando que: os números
menores fiquem à esquerda do pivot e o maiores à
direita (partição do array).
3. Executa recursivamente o mesmo para cada partição
(qsort(array, 0, k) e qsort(array, k+1, n))
Algoritmos Θ(nlogn
logn) - QuickSort
36 20 17 13 28 14 23 15
36 20 17 13 28 14 23 15
36 20 17 13 28 14 23 15
20 36 13 17 14 28 15 23
13 17 20 36 14 15 23 28
13 14 15 17 20 23 28 36
Algoritmos Θ(nlogn
logn) - QuickSort
Algoritmo completo:
void qsort(array, i, j){
pivotindex = findPivot(i, j);
swap(array, pivotindex, j);
k = partition(array, i, j, j)
swap(array, k, j);
se ((k-i)>1) entao qsort(array, i, k-1)
se ((j-k)>1) entao qsort(array, k+1, j)
}
int findPivot(i, j){
retorna (i+j)/2; // retorna parte inteira!!
}
Algoritmos Θ(nlogn
logn) - QuickSort
Algoritmo completo:
int partition(array, l, r, pivot){
faz{
enquanto(l<pivot e array[l] <= array[pivot])
l++;
enquanto(r>l e array[r] => array[pivot])
r--;
swap(array, l, r);
}enquanto(l<r);
swap(array, l, r);
retorna l;
}
72
O pior tempo é Θ(n2), ocorre quando ...
E o melhor é Θ(nlogn), ocorre quando ...
Tarefa: implementar o quicksort e preencher as lacunas acima
3
Algoritmos Θ(nlogn
logn) - QuickSort
12 3 25 8 9 11 5 50 70 30 14
Algoritmos Θ(nlogn
logn) - QuickSort
Algumas otimizações possíveis:
Alteração da função findPivot para
computar achar o índice de um valor mediano
na lista de valores
Como o qsort é bom para situações de
média a grande quantidade de elementos,
quando chegar a poucos elementos utilizar
outro método de ordenação, como por
exemplo, o insertionSort.
“Tirar” a recursividade e re-escrever o
algoritmo para trabalhar com pilhas.
Algoritmos Θ(nlogn
logn) - QuickSort
Demos
Tarefas para casa:
Implementar o algortimo quicksort otimizado até
21/11.
Implementar todos os algoritmos usando templates;
permitindo, portanto, a ordenação de qualquer tipo
de dado. Também enviar por e-mail.
Descubra como fazer uma operação que determina o
menor entre dois números sem usar comando “if”. O
mesmo vale para uma função que determina o maior
dos dois. Dica: use apenas operações aritméticas.
Enviar tudo por e-mail:
[email protected]
http://cg.scs.carleton.ca/~morin/misc/sortalg/
http://cs.smith.edu/~thiebaut/java/sort/demo.html
http://research.compaq.com/SRC/JCAT/jdk10/sorting/
Referências Bibliográ
Bibliográficas
http://atschool.eduweb.co.uk/mbaker/sorts.html
http://cs.smith.edu/~thiebaut/java/sort/demo.html
http://cg.scs.carleton.ca/~morin/misc/sortalg/
http://research.compaq.com/SRC/JCAT/jdk10/sorting/
http://www.inf.unisinos.br/~marcelow/ensino/grad/lab2
/ordenacao.html
NAPS, Thomas L. Introduction to Program Design and
Data Structures.
Structures West. 1993, pág. 396-407.
SHAFFER, Clifford A. Data Structures and Algorithm
Analysis.
Analysis Prentice Hall. 1997, pág. 146-153.
4