Implementar el algoritmo de ordenación de selección en C++

Este artículo explicará cómo implementar el algoritmo de ordenación por selección en C++.

Implementar el orden de selección para el contenedor std::vector en C++

Entre los algoritmos de ordenación simples, puede considerar la ordenación por selección como uno de los más simples de implementar; aunque tiene la complejidad O (n²) y lo hace completamente ineficiente en vectores grandes.

El orden de selección se puede especificar como la siguiente rutina: Al principio, encontramos el valor mínimo en el vector y lo intercambiamos con el primer elemento. Luego, movemos el puntero al segundo elemento y encontramos el valor mínimo del subvector restante para intercambiar con el segundo elemento. Continuamos con los pasos anteriores para el resto del vector mientras avanzamos el puntero un elemento a la vez.

Una explicación alternativa para la ordenación por selección podría decir dividir el vector de entrada en dos partes L: la primera es un subvector ordenado y la segunda es el subvector restante de elementos no clasificados (que está en el orden original). Dado que no se puede suponer que el subvector clasificado esté presente en el vector dado, debemos elegir el primer elemento como divisor entre los subvectores ordenados y no clasificados. Por lo tanto, cuando comenzamos a intercambiar los valores mínimos con los elementos en las posiciones iniciales. El vector se dividirá naturalmente en partes clasificadas y no clasificadas.

En el siguiente ejemplo, implementamos la función selectionSort que toma la referencia al objeto std::vector y realiza una modificación in situ de los elementos. Utilizamos el algoritmo std::min_element para encontrar el valor mínimo en cada iteración; esto ayuda a comprender mejor el algoritmo por primera vez.

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

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

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

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

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

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

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

Alternativamente, podemos reescribir la función selectionSort con el segundo bucle for que encuentra el valor mínimo para el sub-vector restante sin clasificar de cada iteración. Esta versión es adecuada para el análisis de complejidad de algoritmos. Aunque el algoritmo de ordenación por selección tiene un tiempo de ejecución cuadrático, puede ser sorprendentemente eficiente en vectores más pequeños en comparación con los algoritmos O (n log n), como la ordenación por fusión o la ordenación por montón. Tenga en cuenta que todavía utilizamos una función STL, std::swap, que es una operación de tiempo constante en este caso, y es útil que el ejemplo de código sea conciso.

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

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

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

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    auto min = it;

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

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

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Producción :

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