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

Este artigo demonstrará como implementar um algoritmo de classificação por inserção em C++.

Implementar a classificação por inserção para o recipiente std::vector em C++

Neste guia, mostraremos como implementar a classificação por inserção como uma função separada que leva uma referência ao objeto std::vector e modifica o conteúdo no local. A classificação por inserção itera por meio de cada elemento do vetor. Ele garante que todos os elementos antes da posição atual sejam classificados, comparando o elemento atual com os anteriores na ordem inversa.

Geralmente, a ordem de comparação não importa muito no desempenho do algoritmo, mas assumimos a ordem reversa e implementamos o código de forma correspondente. Também presumiremos que estamos classificando os elementos em ordem crescente. Ainda assim, em casos reais, o algoritmo de classificação genérico deve ser capaz de usar uma função de comparação personalizada como argumento. Observe que a operação de comparação freqüentemente força o elemento a ser deslocado para a direita se o elemento atual for menor que o anterior. A última operação é implementada usando outro loop for aninhado, que invoca a função std::swap em elementos que estão na ordem errada.

O trecho de código a seguir inclui a função insertionSort em que o loop for externo é responsável por toda a travessia do array. Inicializamos o iterador para o segundo elemento no vetor porque as próximas etapas incluem a comparação com as anteriores - o loop interno itera do elemento atual até o primeiro para compará-los. Se a função de comparação for avaliada como true, o par é trocado. Observe que a expressão else força o loop interno a quebrar quando pelo menos um elemento anterior acaba sendo menor que o elemento atual.

#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>
void insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

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

  printVector(vec1);
  insertionSort(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 reimplementar a função insertionSort usando construções de loop while se a última for preferida como uma forma mais legível para o usuário. Dois algoritmos seguem uma lógica de implementação semelhante e ambos utilizam a função std::swap para deslocar os elementos. A classificação por inserção é um algoritmo bastante ineficiente em grandes conjuntos de dados e seu desempenho médio é O (n²).

A ordenação por inserção é semelhante a outro algoritmo quadrático denominado ordenação por seleção; ambos iteram por meio do vetor. Após as iterações n, os primeiros elementos n são classificados. Embora, a classificação de seleção avalie os elementos para frente da posição atual em contraste com a classificação de inserção.

#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>
void insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

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

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Resultado:

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

A classificação por inserção pode ser mais eficiente na prática em comparação com outros algoritmos O (n²) porque nem sempre é necessário comparar o elemento atual com todos os anteriores. Enquanto isso, a classificação de seleção deve sempre pesquisar cada elemento no subarray não classificado para encontrar o menor (ou o maior) elemento. Observe que podemos utilizar a implementação da função insertionSort no vetor de std::string como a última classe implementa as sobrecargas do operador de comparação. O próximo exemplo demonstra seu uso básico com o vetor string e imprime a lista classificada de palavras.

#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>
void insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Resultado:

highway;
song;
work;
borland;
death;
woman;
borland;
death;
highway;
song;
woman;
work;