Algoritmos de Ordenação
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Auto-avaliação
(2) QuickSort
(3) MergeSort
(1) Auto-avaliação
Ordenação/Classificação
• Antes de prosseguir:
– Considerando o vetor de inteiros a seguir, execute os algoritmos vistos
na aula passada (insertionSort e selectionSort), e escreva as alterações
realizadas nesse vetor, em cada iteração realizada
vetor
iteração
4
8
3
2
1
7
1ª
2ª
3ª
4ª
5ª
6ª
...
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(2) QuickSort
Dividir e Conquistar
• É um paradigma geral de projeto de algoritmos:
– Dividir: divida os dados de entrada S em dois subconjuntos disjuntos
S1 e S2
– Recorrência: resolva os subproblemas associados a S1 e S2, geralmente
de forma recursiva
– Conquistar: combine as soluções para S1 e S2 em uma solução para S
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
3
(2) QuickSort
QuickSort
• É um algoritmo de ordenação baseado no paradigma de
dividir e conquistar
• Encontre um elemento na lista a ser ordenada para servir
como o pivô
• Divida a lista em duas partes - uma com elementos
maiores ou iguais ao elemento pivô e a outra com os
elementos menores do que pivô.
• Repita recursivamente o algoritmo para as duas partes da
lista original
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
4
(2) QuickSort
Pseudocódigo
Quicksort (0,5,v)
Algorithm Quicksort(inicio, fim, v)
Input initial position, final position, a
sequence v
Output the sequence v sorted
if (inicio >= fim) then return;
indicePivo  Partition(inicio, fim, v)
Quicksort(inicio, indicePivo-1, v)
Quicksort(indicePivo+1, fim, v)
7 4 1
9 3 2
Partition (0,5,v) retorna 4
3 4 1
Quicksort(0,3,v)
3 4 1
2
Partition (0,3,v) retorna 2
1
2
Quicksort(0,1,v)
3
2 7 9
Quicksort(5,5,v)
9
4
Quicksort(3,3,v)
1 2
4
Partition (0,1,v) retorna 0
1
Quicksort(0,-1)
return
Estrutura, Pesquisa e Ordenação de Dados
2
Quicksort(A,1,1)
2
Frederico Brito Fernandes
5
(2) QuickSort
Pseudocódigo
Partition(inicio, fim, v)
Input initial position, final position, a sequence v
Output the position of the pivot element
i  inicio
f  fim
pivo  v[inicio]
while(i<f)
while(v[i]<=pivo AND i<fim)
i  i+1
while (v[f] > pivo)
f  f-1
if (i<f) then
troca(v[i],v[f])
v[inicio]  v[f]
v[f]  pivo
return f
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
Exemplo: Partition (0,5,v)
i
7 4 1
9 3 2
pivo=7
f
i
7 4 1
2 3 9
pivo=7
f
3 4 1
2 7 9
pivo=7
f
return 4
6
(3) MergeSort
MergeSort
• Também chamado de ordenação por intercalação
• Também baseado no paradigma de dividir e conquistar
• Divide o vetor a ser ordenado em duas metades aproximadamente
iguais
• Cada metade é ordenada recursivamente e então são intercaladas
de volta para formar o vetor final ordenado
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
7
(3) MergeSort
Princípio: dividir e ordenar
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
8
(3) MergeSort
Exemplo
• Realizar Merge-sort em
uma sequência de entrada
S com n elementos
consiste de três passos:
– Dividir: particionar S em
duas sequências S1 e S2 de
cerca de n/2 elementos cada
– Recorrência: aplicar
recursivamente a operação
Merge-sort em S1 e S2
– Conquistar: intercalar S1 e
S2 em uma única sequência
S ordenada
7 4 1
7
4 1
9 3 2
9
3 2
4
1
3
2
4
1
3
2
Merge
7
1 4
Merge
9
2 3
Merge
Merge
1 4 7
2 3 9
Merge
1 2 3
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
4 7 9
9
(3) MergeSort
MergeSort - Dividir
mergeSort(0,6,S)
7 4 1
mergeSort(0,3,S)
9 3 2
mergeSort(3,6,S)
7 4 1
9 3 2
Algorithm mergeSort(ini, post, S)
Input initial position , final position + 1 and
sequence S
Output sequence S sorted
if (ini<post-1) then
mid  (ini+post)/2
Sini-(mid-1)  mergeSort(ini,mid, S)
Smid-(post-1)  mergeSort(mid,post,S)
Sini-(post-1)  merge(ini,mid,post,S)
mergeSort(0,1,S) mergeSort(1,3,S)
mergeSort(3,4,S) mergeSort(4,6,S)
7
4 1
mergeSort(1,2,S)
4
9
3 2
mergeSort(2,3,S)
1
Return S
mergeSort(4,5,S)
3
Estrutura, Pesquisa e Ordenação de Dados
mergeSort(5,6,S)
2
Frederico Brito Fernandes
10
(3) MergeSort
MergeSort - Conquistar
4
1
3
Merge (1,2,3,S)
7
Merge (4,5,6,S)
1 4
Merge (0,1,3,S)
9
2 3
Algorithm mergeSort(ini, post, S)
Input initial position , final position + 1 and
sequence S
Output sequence S sorted
Merge (3,4,6,S)
1 4 7
2 3 9
Merge (0,3,6,S)
1 2 3
2
4 7 9
if (ini<post-1) then
mid  (ini+post)/2
Sini-(mid-1)  mergeSort(ini,mid, S)
Smid-(post-1)  mergeSort(mid,post,S)
Sini-(post-1)  merge(ini,mid,post,S)
Return S
Possui tempo de execução de O(n log n)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
11
(3) MergeSort
Merge
7 4 1
7
4 1
9
3 2
4
1
3
2
4
1
3
2
Merge
7
Algorithm merge(ini, mid, post, S)
9 3 2
1 4
Merge
9
2 3
Merge
Merge
1 4 7
2 3 9
Merge
1 2 3
W empty sequence of size (post-ini)
i  ini
j  mid
k0
while (i < mid) and (j < post) do
if (S[i] <= S[j]) then
W[k]  S[i]
k  k+1
else
W[k]  S[j]
k  k+1
while (i < mid) do
W[k]  S[i]
k  k+1
while (j < post) do
W[k]  S[j]
k  k+1
for i  ini to post-1 do
S[i]  W[i-ini];
Return S
i  i+1
j  j+1
i  i+1
j  j+1
4 7 9
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
12