Implementar algoritmo de ordenación rápida en C++

1. Implementar Quicksort para el contenedor std::vector
2. Investigar los niveles de recurrencia en la implementación de Quicksort

Este artículo demostrará varios métodos sobre cómo implementar el algoritmo de ordenación rápida en C++.

Implementar Quicksort para el contenedor std::vector

Quicksort es uno de los algoritmos de clasificación de propósito general más rápidos que se utilizan en las bases de código contemporáneas. Utiliza la técnica de divide y vencerás similar al algoritmo de clasificación por fusión. Aunque, el primero depende de una operación comúnmente llamada particionamiento. El vector original se divide en el elemento conocido como pivot, que delimita los elementos más pequeños antes y los más grandes después. Tenga en cuenta que estas comparaciones son relativas al valor de pivote, que el usuario debe elegir. La elección del valor pivote resulta ser el factor crítico para el rendimiento de este algoritmo, que analizaremos más adelante en el artículo. En este punto, supongamos que el elemento pivote es el primer elemento del vector original. Una vez que tenemos el método para la selección de pivotes, podemos dividir el vector en dos vectores más pequeños que se ordenarán recursivamente en su lugar. Observe que la operación de ordenación rápida es similar a la ordenación de combinación en que también divide los vectores varias veces hasta que sus posiciones iniciales se cruzan entre sí.

El siguiente código de ejemplo implementa el algoritmo con una función recursiva sort que llama a la función partitionVec cada vez que se invoca. El proceso de partición se puede realizar en tiempo lineal intercambiando elementos en el mismo objeto vectorial. La última operación se implementa mediante la función partitionVec, que también actúa como función de clasificación de cierta manera.

#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;
}

Producción :

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

Investigar los niveles de recurrencia en la implementación de Quicksort

La ordenación rápida tiene la complejidad de tiempo promedio O (n log n), que está a la par con el algoritmo de ordenación por combinación. Sin embargo, tenga en cuenta que el algoritmo de ordenación rápida depende en gran medida del método de selección de pivote. En este caso, elegimos la versión ingenua para elegir el valor pivote, que fue el primer elemento del vector. Esto puede producir tiempos de ejecución bastante malos con O (n²) en ciertos escenarios. En la práctica, elegir el pivote aleatorio tiene una alta probabilidad de producir el rendimiento O (n log n). Sin embargo, uno debe conocer el método de selección de pivote basado en datos de entrada si se requiere el máximo rendimiento.

Podemos observar el proceso recursivo en el fragmento de código anterior usando el argumento de función adicional que cuenta cada invocación de la función sort. El siguiente ejemplo ejecuta una prueba similar en dos vectores de diferentes tamaños e imprime las sumas correspondientes. Observe que la suma de las llamadas recursivas relaciona el tamaño del vector con la siguiente función: 2n - 1, donde n denota el 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;
}

Producción :

level: 199
level: 399