Ordenação rápida

1. Algoritmo de classificação rápida
2. Exemplo de classificação rápida
3. Implementação do algoritmo de classificação rápida
4. Complexidade do algoritmo de classificação rápida

A classificação rápida é um algoritmo de classificação altamente eficiente baseado no princípio do algoritmo de divisão para conquistar. A classificação rápida funciona particionando a matriz em duas partes em torno de um elemento pivô selecionado. Ele move elementos menores para o lado esquerdo do pivô e elementos maiores para o lado direito. Depois disso, as subpartes esquerda e direita são classificadas recursivamente para classificar todo o array. É chamado de classificação rápida porque é cerca de 2 ou 3 vezes mais rápido do que os algoritmos de classificação comuns. A classificação rápida é amplamente usada para pesquisa de informações e cálculos numéricos dentro de estruturas de dados.

Algoritmo de classificação rápida

Vamos supor que temos um array não classificado A[] contendo n elementos. Pegue duas variáveis, beg e end, e armazene o índice do elemento inicial e final.

Partição()

QuickSort()

Exemplo de classificação rápida

Suponha que temos o array: (6,5,1,4,2,3). Vamos classificá-lo usando o algoritmo de classificação rápida.

Implementação do algoritmo de classificação rápida

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexidade do algoritmo de classificação rápida

Complexidade de tempo

• Caso Médio

O tempo gasto pela classificação rápida é dado pela seguinte relação de recorrência:

 T(n) = T(k) + T(n-k-1) + θ(n)

k aqui representa o número de elementos menores / maiores do que o elemento pivô.

Este resultado desta relação de recorrência dá T(n) = nLogn. O caso médio ocorre quando obtemos partições desigualmente balanceadas aleatórias. A complexidade do tempo é da ordem de [Big Theta]: O(nLogn).

• Pior caso

T(n) = T(n-1) + θ(n)

O pior caso ocorre quando o elemento pivô é sempre o maior ou o menor elemento da matriz. Neste caso, todos os elementos caem em uma submatriz e no máximo n chamadas devem ser feitas. O pior caso de complexidade de tempo é [Big O]: O(n²).

• Melhor caso

 T(n) = 2T(n/2) + θ(n)

O melhor caso ocorre quando o elemento pivô selecionado é sempre o elemento do meio ou quando ambas as partições estão uniformemente equilibradas, ou seja, a diferença no tamanho é 1 ou menos. O melhor caso de complexidade de tempo é [Big Omega]: O(nLogn).

Complexidade do Espaço

A complexidade de espaço de caso médio para o algoritmo de classificação rápida é O(logn). É o espaço exigido pela pilha de recursão. Mas no pior caso, quando a classificação de uma matriz requer n recursiva, a complexidade do espaço é O(n).