DAA - Classificação Rápida

É usado com base no princípio de dividir e conquistar. A classificação rápida é um algoritmo de escolha em muitas situações, pois não é difícil de implementar. É um bom tipo de uso geral e consome relativamente menos recursos durante a execução.

Vantagens

• Ele está no lugar, pois usa apenas uma pequena pilha auxiliar.

• Requer apenas n (log n) hora de classificar n Itens.

• Possui um laço interno extremamente curto.

• Este algoritmo foi submetido a uma análise matemática completa, uma declaração muito precisa pode ser feita sobre questões de desempenho.

Desvantagens

• É recursivo. Especialmente, se a recursão não estiver disponível, a implementação é extremamente complicada.

• Requer tempo quadrático (isto é, n2) no pior caso.

• É frágil, ou seja, um simples erro na implementação pode passar despercebido e causar um mau desempenho.

A classificação rápida funciona particionando um determinado array A[p ... r] em duas submatrizes não vazias A[p ... q] e A[q+1 ... r] de modo que cada chave em A[p ... q] é menor ou igual a cada chave em A[q+1 ... r].

Em seguida, os dois subarrays são classificados por chamadas recursivas para classificação rápida. A posição exata da partição depende da matriz e índice fornecidosq é calculado como parte do procedimento de particionamento.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Observe que para classificar a matriz inteira, a chamada inicial deve ser Quick-Sort (A, 1, length[A])

Como primeira etapa, a Classificação rápida escolhe um dos itens na matriz para ser classificado como pivô. Em seguida, a matriz é particionada em ambos os lados do pivô. Os elementos menores ou iguais ao pivô se moverão para a esquerda, enquanto os elementos maiores ou iguais ao pivô se moverão para a direita.

Particionando o Array

O procedimento de particionamento reorganiza as submatrizes no local.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Análise

O pior caso de complexidade do algoritmo Quick-Sort é O(n²). No entanto, usando essa técnica, em casos médios geralmente obtemos a saída emO(n log n) Tempo.