Implementar Algoritmo Quicksort em C++

1. Implementar Quicksort para recipiente std::vector
2. Investigue os níveis de recursão na implementação Quicksort

Este artigo demonstrará vários métodos sobre como implementar o algoritmo de classificação rápida em C++.

Implementar Quicksort para recipiente std::vector

Quicksort é um dos algoritmos de classificação de propósito geral mais rápidos usados ​​em bases de código contemporâneas. Ele utiliza a técnica de divisão e conquista semelhante ao algoritmo de classificação por mesclagem. Embora, o primeiro dependa de uma operação comumente chamada de particionamento. O vetor original é dividido no elemento conhecido como pivot, que delimita os elementos menores antes dele e os maiores depois. Observe que essas comparações são relativas ao valor pivô, que o usuário deve escolher. A escolha do valor do pivô passa a ser o fator crítico para o desempenho desse algoritmo, que analisaremos posteriormente neste artigo. Neste ponto, vamos supor que o elemento pivô seja o primeiro elemento no vetor original. Assim que tivermos o método para seleção de pivô, podemos particionar o vetor em dois vetores menores que serão classificados recursivamente no lugar. Observe que a operação de classificação rápida é semelhante à classificação por mesclagem, pois também particiona os vetores várias vezes até que suas posições iniciais se cruzem.

O código de exemplo a seguir implementa o algoritmo com uma função sort recursiva que chama a função partitionVec cada vez que é chamada. O processo de particionamento pode ser feito em tempo linear trocando elementos no mesmo objeto vetorial. A última operação é implementada usando a função partitionVec, que também atua como a função de classificação de uma determinada maneira.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary);
  sort(vec, boundary + 1, end);
}

template <typename T>
void quickSort(vector<T> &vec) {
  sort(vec, 0, vec.size() - 1);
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  quickSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Resultado:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Investigue os níveis de recursão na implementação Quicksort

Quicksort tem a complexidade de tempo médio O (n log n), que está no mesmo nível do algoritmo de classificação por mesclagem. Observe, porém, que o algoritmo de classificação rápida depende muito do método de seleção de pivô. Nesse caso, escolhemos a versão ingênua para escolher o valor do pivô, que foi o primeiro elemento do vetor. Isso pode resultar em tempos de execução bastante ruins com O (n²) em certos cenários. Na prática, a escolha do pivô aleatório tem uma alta probabilidade de gerar o desempenho O (n log n). No entanto, deve-se estar ciente do método de seleção de pivô com base nos dados de entrada se o desempenho máximo for necessário.

Podemos observar o processo recursivo no fragmento de código anterior usando o argumento de função adicional que conta cada invocação da função sort. O exemplo a seguir executa um teste semelhante em dois vetores de tamanhos diferentes e imprime as somas correspondentes. Observe que a soma das chamadas recursivas relaciona o tamanho do vetor com a seguinte função - 2n - 1, onde n denota o número de elementos.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary, ++level);
  sort(vec, boundary + 1, end, ++level);
}

template <typename T>
void quickSort(vector<T> &vec, int &level) {
  sort(vec, 0, vec.size() - 1, ++level);
}

int main() {
  vector<int> vec3(100, 10);
  vector<int> vec4(200, 10);

  int recursion_level = 0;

  quickSort(vec3, recursion_level);
  cout << "level: " << recursion_level << endl;

  recursion_level = 0;
  quickSort(vec4, recursion_level);
  cout << "level: " << recursion_level << endl;

  return EXIT_SUCCESS;
}

Resultado:

level: 199
level: 399