No Capítulo 5, você viu um método de classificação simples chamado
classificação de bolha. Foi mencionado naquele momento que existem
classificações significativamente melhores. Aqui, você desenvolverá uma versão de uma das melhores: a classificação rápida (Quicksort).
A classificação rápida, inventada e nomeada por C.A.R. Hoare, é o melhor algoritmo de classificação de uso geral disponível atualmente. Não pude mostrá-lo no Capítulo 5, porque a melhor implementação da classificação rápida se baseia na recursão. A versão que desenvolveremos classifica um array de caracteres, mas a lógica pode ser adaptada para classificar qualquer tipo de objeto.
A classificação rápida se baseia na ideia de partições. O procedimento geral envolve a seleção de um valor, chamado comparando, e depois é feita a divisão do array em duas seções. Todos os elementos maiores ou iguais ao valor da partição são inseridos em um lado e os menores são inseridos no outro. Esse processo é repetido para cada seção remanescente até o array estar classificado. Por exemplo, dado o array fedacb e usando o valor d como comparando, a primeira passagem da classificação rápida reorganizaria o array como mostrado a seguir:
Inicial f e d a c b
Passagem 1 b c a d e f
Esse processo é então repetido para cada seção – isto é, bca e def. Como você pode ver, o processo é essencialmente recursivo em sua natureza, e, na verdade, a implementação mais limpa da classificação rápida é recursiva.
Você pode selecionar o valor do comparando de duas maneiras. Pode selecioná-lo aleatoriamente ou achando a média de um pequeno conjunto de valores tirados do array. Para obter uma classificação ótima, deve selecionar um valor que esteja exatamente no meio do intervalo de valores. No entanto, não é fácil fazer isso na maioria dos conjuntos de dados. O pior caso é quando o valor selecionado está em uma extremidade. Mesmo assim, a classificação rápida será executada corretamente.
A versão da classificação rápida que desenvolveremos seleciona o elemento do meio do array como comparando.
Ver QSDemo.java.
Classificação Rápida:
- Um dos algoritmos de classificação mais eficientes e amplamente usados.
- Inventado por C.A.R. Hoare.
- Baseado no conceito de partições, onde o array é dividido em seções que são recursivamente classificadas.
- Mais eficiente que a classificação de bolha e outros métodos simples.
Funcionamento:
- Valor de Comparação (Pivot):
- Escolhe-se um valor como referência (pivot) e organiza-se o array em torno desse valor.
- Elementos menores que o pivot vão para um lado e os maiores para o outro.
- O processo é repetido recursivamente para cada seção até que o array esteja completamente ordenado.
Quicksort
QSDemo
Top comments (0)