Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André, Parar no igual faz o…
IF672 (2020.1) - Levitin Aluno: Marcos André
(5.2) Quicksort (176–181)
Algoritmo de ordenação
Baseado no divide-and-conquer
Divide os elementos de acordo com seus valores
Particionar
Todos os elementos à esquerda de A[s] são menores ou iguais à A[s]
Todos os elementos à direita de A[s] são maiores ou iguais à A[s]
Os dois subarrays restantes são ordenados com o mesmo método
A solução aparece naturalmente
Métodos de particionamento
Hoare
Escanear da esquerda para a direita (i)
Para ao encontrar elemento maior ou igual
Escanear da direita para a esquerda (j)
Para ao encontrar elemento elemento menor ou igual
Dependendo do cruzamento dos índices (i e j)
i < j
Troca i por j continuando os scans, incrementando i e decrementando j
i > j
Particionado o subarray após trocar o pivô por A[j]
i = j
Pararam no pivô, subarray particionado
Escolhe um elemento como pivô
Criar uma sentinela
Desnecessário
Lomuto
Não é muito sofisticado
Eficiência
Melhor caso
Cbest (n) pertence a Θ(n log2 n)
Pior caso
Cworst(n) pertence a Θ(n²)
Médio caso
Cavg(n) pertence a 1.39n log2 n
Eficiência alta num geral
Melhorias descobertas
Escolher pivô de forma randomizada
Escolher pivô como a média do elemento mais a esquerda, mais a direita e o do meio
Uso do Insertion sort para subarrays pequenos
Modificações do particionamento do algoritmo
Partição em 3
Segmentos menores, iguais, ou maiores que o pivô
Fraquezas
Instável
Requer o uso de uma pilha
Ocupa mais espaço que o Heapsort
Pior caso ainda tem baixa eficiência, apesar de ter formas de amenizar
Performance em arrays randomicamente ordenadas é sensível
Aos detalhes de implementação
À arquitetura do computador e tipo de dados
Ainda assim é um dos mais influentes algoritmos
Parar no igual faz o algoritmo ser mais eficiente quando se tem muitas duplicatas