Métodos de ordenação: Bubble Sort, Seleção Direta e

Algoritmos de Ordenação
Leandro Tonietto
Unisinos
[email protected]
http://professor.unisinos.br/ltonietto
Atualizado em 7-Jun-12
http://professor.unisinos.br/ltonietto/inf/lb2/sort.pdf
Sumário
! 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
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}
Métodos de 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.
Eficiência e Classificação dos Algoritmos de 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.
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)
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)- Insertion Sort
! Exemplo: dada a lista 20, 5, 18, 11, 9, 20, 4
e 10
i=1
20
5
18
11
9
20
4
10
i=2
i=3
i=4
i=5
i=6
i=7
Algoritmos Θ(n2)- Bubble Sort
! 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)- Bubble Sort
! Exemplo da mesma lista:
42
20
17
13
28
14
23
15
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)- Bubble Sort
! Exemplo: dada a lista 20, 5, 18, 11, 9, 20, 4
e 10
i=0
20
5
18
11
9
20
4
10
i=1
i=2
i=3
i=4
i=5
i=6
Algoritmos Θ(n2)- Selection Sort
! Procura o próximo menor valor da lista e coloca
na posição atual.
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 Θ(n2)- Selection Sort
! Exemplo da mesma lista:
i=0
42
20
17
13
28
14
23
15
i=1
i=2
i=3
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);
}
Algoritmos Θ(nlogn) - 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)
Algoritmos Θ(nlogn) - 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) - MergeSort
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) - 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) - 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) - 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;
}
! O pior tempo é Θ(n2), ocorre quando ...
! E o melhor é Θ(nlogn), ocorre quando ...
Tarefa: implementar o quicksort e preencher as lacunas acima
Algoritmos Θ(nlogn) - QuickSort
72
Algoritmos Θ(nlogn) - QuickSort
12 3 25 8 9 11 5 50 70 30 14
Algoritmos Θ(nlogn) - 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) - QuickSort
! Tarefas para casa:
!
!
!
!
Implementar todos os algoritmos usando templates; permitindo,
portanto, a ordenação de qualquer tipo de dado. Enviar por email.
Faça uma classe de testes (main) que gere um array com
números aleatórios e ordene uma cópia deste array com cada
algoritmo implementado. Não esqueça que computar o tem
processamento de cada execução para comparar a performance
dos algoritmos. Enviar junto com a implementação dos
algoritmos.
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] ou [email protected]
Demos
! 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á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/
NAPS, Thomas L. Introduction to Program Design and
Data Structures. West. 1993, pág. 396-407.
! SHAFFER, Clifford A. Data Structures and Algorithm
Analysis. Prentice Hall. 1997, pág. 146-153.
!
!
!
!
!