MO417 - Ata da Aula (Quicksort)
Ata - Aula do dia 14/03/2003
Dia da digitação: 16/03/2003
Redator: Ricardo Luís Lachi 972929
Tópicos desta ata:
1. Introdução
2. Quicksort
2.1. Descrição
2.2. Algoritmo
2.3. Particionamento do arranjo
2.4. Pior particionamento do arranjo
2.5. Melhor particionamento do arranjo
2.6. Particionamento balanceado
3. Assuntos extras
- Quicksort, quanto melhor ?
4. Conclusões
5. Referências bibliográficas
Resumo
O quicksort (ordenação rápida) é um algoritmo de ordenação cujo tempo de execução do
pior caso é Teta(n^2) sobre um arranjo de entrada de n números. Apesar desse tempo de execu-
ção lento no pior caso, o quicksort com freqüência é a melhor opção prática para ordenação,
devido a sua notável eficiência na média: seu tempo de execução esperado é Teta(n*lg(n)), e os
fatores constantes ocultos na notação Teta(n*lg(n)) são bastante pequenos. Ele também apresen-
ta a vantagem da ordenação local e funciona bem até mesmo em ambientes de memória virtual
1. Introdução
Nesta ata é apresentada uma descrição dos tópicos do capítulo 7 do livro do Cormen (2002) abordados durante a aula da disciplina Complexidade de Algoritmos
ministrada no 1º semestre letivo de 2003 pelo professor João Meidanis.
2. Quicksort
2.1. Descrição
O quicksort, como a ordenação por intercalação, se baseia no paradigma de dividir e conquistar. A seguir é apresentado o processo
de dividir e conquistar em três passos para ordenar um subarranjo típico A[p..r].
Dividir: O arranjo A[p..r] é particionado (reorganizado) em dois subarranjos (possivelmente vazios) A[p..q-1] e A[q+1..r] tais que cada elemento de A[p..q-1] é menor que ou igual a A[q] que, por sua vez, é igual ou menor a cada elemento de A[q+1..r]. O índice q é calculado como parte desse procedimento de particionamento.
Conquistar: Os dois subarranjos A[p..q-1] e A[q+1..r] são ordenados por chamadas recursivas a quicksort.
Combinar: Como os subarranjos são ordenados localmente, não é necessário nenhum trabalho para combiná-los: o arranjo A[p..r] inteiro agora está ordenado.
2.2. Algoritmo
QUICKSORT(A, p, r)
1 if p < r then
2 q = PARTITION(A, p, r)
3 QUICKSORT(A, p, q-1)
4 QUICKSORT(A,q+1,r)
Para ordenar um arranjo A inteiro, a chamada inicial é QUICKSORT(A,1,comprimento[A]).
Discussão em aula a respeito desse tópico:
- Prof. seleciona o Fábio para falar um pouco sobre o QuickSort.
- Fábio:
Utiliza o método de dividir e conquistar em 3 passos. Divide em dois sub-arranjos de p a i e de i+1 a r-1
depois resolve recursivamente cada um dos pedaços e por fim combina os pedaços ordenados
- Prof. faz um comentário complementar:
Utiliza 3 passos. Pega um elemento X e faz com que todos os elementos menores que X do vetor fiquem à esquerda de X,
e, elementos maiores que X, fiquem à direita de X no vetor. Depois chama recursivamente para ordenar independentemente
cada parte do vetor dividido.
2.3. Particionamento do arranjo
A chave para o algoritmo é o procedimento PARTITION, que reorganiza o subarranjo A[p..r] localmente.
PARTITION(A,p,r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4 do if A[j] <= x
5 then i = i + 1
6 trocar A[i] com A[j]
7 trocar A[i+1] com A[r]
8 return i + 1
Discussão em aula a respeito desse tópico:
- Prof. chama por Augusto mas não estava presente.
- Prof. chama por José Augusto mas não estava presente.
- Prof. pergunta para o Patrick quanto tempo custa o algoritmo Partition.
- Patrick:
Leva O(n): precisa percorrer todo o vetor comparando os elementos
- Carlos pergunta:
No Manber o tempo é Teta(n) e no Cormen é O(n). Como pode ?
- Prof. responde:
Sem problemas pois esses dois tempos não são discordantes, a diferença
é que o Manber é mais preciso.
2.4. Pior particionamento do arranjo
O comportamento do pior caso para o quicksort ocorre quando a rotina de particionamento produz um subproblema com n - 1 elementos e um com 0 elementos. Vamos supor que esse particionamento não balanceado surge
em cada chamada recursiva. O particionamento custa o tempo Teta(n). Tendo em vista que a chamada recursiva sobre um arranjo de tamanho 0 simplesmente retorna,
T(0) = Teta(1), e a recorrência para o tempo de execução é:
T(n) = T(n - 1) + T(0) + Teta(n)
= T(n - 1) + Teta(n)
Intuitivamente, se somarmos os custos incorridos a cada nível da recursão, conseguimos uma série aritmética cujo custo é Teta(n^2). Na realidade, é simples usar o método de substituição para provar que a recorrência T(n) = T(n-1) + Teta(n) tem a solução
T(n) = Teta(n^2).
Portanto, se o particionamento é não balanceado de modo máximo em cada nível recursivo do algoritmo, o tempo de execução é Teta(n^2). Por conseguinte, o tempo de execução do pior caso do quicksort não é melhor que o da ordenação por inserção. Além disso, o tempo
de execução Teta(n^2) ocorre quando o arranjo de entrada já está completament ordenado - uma situação comum na qual a ordenação por inserção é executa no tempo O(n).
Discussão em aula a respeito desse tópico:
- Prof. pergunta para Camila qual o pior tipo de partição que pode ocorrer.
- Camila:
A pior partição ocorre quando a divisão divide o vetor em duas partes onde
uma delas fica com todos os elementos e a outra com nenhum.
Escolha pivô:
- Prof. pergunta para Guilherme como escolher o pivô.
- Guilherme:
Cita o caso do livro no qual o pivô é escolhido como sendo sempre o último elemento.
2.5. Melhor particionamento do arranjo
Na divisão mais uniforme possível, PARTITION produz dois subproblemas, cada um de tamanho
não maior que n/2, pois um tem tamanho Piso(n/2) e o outro tem tamanho Teto(n/2) - 1. Nesse caso, o
quicksort é executado com muito maior rapidez. A recorrência pelo tempo de execução é então
T(n) <= 2 * T(n/2) + Teta(n)
que, pelo caso 2 do teorema mestre tem a solução T(n) = O(n*lg(n)). Desse modo, o balanceamento equilibrado dos dois lados da partição em cada nível da recursão produz um
algoritmo assintoticamente mais rápido.
Discussão em aula a respeito desse tópico:
- Prof. pergunta para André qual a melhor partição possível de ser feita.
- André:
Quando o vetor é dividido em duas partes iguais: n/2 elementos em cada uma delas.
2.6. Particionamento balanceado
O tempo de execução do caso médio de quicksort é muito mais próximo do melhor caso que do pior caso. A chave para compreender por que isso poderia
ser verdade é entender como o equilíbrio do particionamento se reflete na recorrência
que descreve o tempo de execução.
Por exemplo, suponha que o algoritmo de particionamento sempre produza uma divisão proporcional de 9 para 1, que a princípio parece
bastante desequilibrada. Então, obtemos a recorrência
T(n) <= T(9n/10) + T(n/10) + c * n
no tempo de execução de quicksort, onde incluímos explicitamente a constate c oculta no termo Teta(n). Se montarmos a árvore de recursão
dessa recorrência pode-se ver que, assintoticamente, ela é executada tão rápida quanto O(n*lg(n)).
Discussão em aula a respeito desse tópico:
- Prof. pergunta para Eduardo o que é partição balanceada.
- Eduardo
Descreve o caso do livro no qual o vetor é dividido em duas partições na proporção 1 para 9 e que essa partição se aproxima do melhor caso.
- Prof. comenta:
Para se aproximar do melhor caso o particionamento balanceado deve dividir o vetor em uma proporção/fração de elementos para cada lado do vetor.
3. Assuntos extras
3.1. Quicksort, quanto melhor ?
Discussão em aula a respeito desse tópico:
- Prof. pergunta para Marcelo qual o tempo do algoritmo se ocorrer sempre a pior partição possível.
- Marcelo
Diz que custa O(n^2). Pergunta porque o Quicksort acaba sendo usado se o seu pior caso é pior que o de outros algoritmos, tais como, merge, heap.
- André comenta:
Diz que as constantes implícitas no Quicksort são menores que nos outros algoritmos.
- Marcelo pergunta:
Afinal, o Quicksort é muito melhor ou não ?
- Prof. responde:
Diz que as constantes são uma tentativa de explicar a observação prática de que o Quicksort é mais rápido que os outros. O que acontece é que há uma tentativa de se explicar
teoricamente esse fato (Quicksort ser mais rápido que os outros na prática) mas ainda não se consegue isso de forma satisfatória. Talvez uma causa seja a falta de amadurecimento da teoria pois essa área de teoria tem só 40 anos
- Marcelo pergunta:
Se já foi feito algum experimento para ver essa ordem de crescimento.
- Prof. responde:
A ordem é O(n*lg(n)). Agora, se fossem ser apuradas as contantes com exatidão, aconteceria que a análise acabaria tendo que se restringir a uma máquina espcífica o que não seria muito útil na prática.
- Prof. comenta:
Já viu um trabalho fazendo uma análise de como os algoritmos de ordenação se comportam com certos arranjos iniciais de vetores.
Cita as linguagens de programação (C, java) e diz que elas já vem com um algoritmo de ordenação embutido e que esse algoritmo é uma variação do Quicksort, a única diferença entre eles é com relação à escolha do pivô. Também comentou que, hoje em dia, não se escrevem mais algoritmos de sort, se é necessário
ordenar algo, normalmente, se aplica o Quicksort.
- Carlos comenta:
Comenta que a idéia de todos os sistemas é manter a base ordenada o que fará com que o Quicksort seja o mais rápido dentre todos e por isso é o mais aplicado na prática
- Alexandro pergunta:
Qual o custo de ordenar um lista ligada por meio desse algoritmo.
- Prof. comenta:
Se eu precisar ordenar uma lista ligada, joga-se ela para um vetor, ordena-se ele e depois monta a lista de novo. É o método mais rápido e barato que existe.
4. Conclusões
Foram abordados todos os tópicos previstos e também ocorreu uma discussão interessante a respeito de quão mais rápido o quicksort é realmente em relação aos outros algoritmos existentes.
5. Referências bibliográficas
(Cormen, 2002) Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.