Implementar o algoritmo de classificação por seleção em C++

Este artigo explicará como implementar o algoritmo de classificação de seleção em C++.

Implementar a classificação de seleção para o recipiente std::vector em C++

Entre os algoritmos de classificação simples, você pode considerar a classificação de seleção como um dos mais simples de implementar; embora tenha a complexidade O (n²), e torna-o totalmente ineficiente em vetores grandes.

A ordenação da seleção pode ser especificada como a seguinte rotina: Primeiramente, encontramos o valor mínimo no vetor e o trocamos pelo primeiro elemento. Em seguida, movemos o ponteiro para o segundo elemento e encontramos o valor mínimo do subvetor restante para trocar com o segundo elemento. Continuamos as etapas anteriores para o resto do vetor enquanto avançamos o ponteiro um elemento por vez.

Uma explicação alternativa para a ordenação por seleção poderia dizer dividir o vetor de entrada em duas partesL: a primeira é um subvetor ordenado e a segunda é o subvetor restante de elementos não ordenados (que está na ordem original). Uma vez que o subvetor classificado não pode ser assumido como estando presente no vetor fornecido, devemos escolher o primeiro elemento como o divisor entre os subvetores classificados e não classificados. Assim, quando começamos a trocar os valores mínimos com os elementos nas posições iniciais. O vetor será naturalmente dividido em partes ordenadas e não ordenadas.

No exemplo a seguir, implementamos a função selectionSort que leva a referência ao objeto std::vector e conduz uma modificação local dos elementos. Utilizamos o algoritmo std::min_element para encontrar o valor mínimo em cada iteração; isso ajuda a entender melhor o algoritmo pela primeira 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;
}

Resultado:

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

Alternativamente, podemos reescrever a função selectionSort com o segundo loop for que encontra o valor mínimo para cada subvetor não classificado restante de cada iteração. Esta versão é adequada para a análise da complexidade do algoritmo. Mesmo que o algoritmo de classificação de seleção tenha um tempo de execução quadrático, ele pode ser surpreendentemente eficiente em vetores menores em comparação com os algoritmos O (n log n), como classificação por mesclagem ou classificação heapsort. Observe que ainda utilizamos uma função STL, std::swap, que é uma operação de tempo constante neste caso, e é útil para o exemplo de código ser 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;
}

Resultado:

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