Clasificación por inserción usando C++ STL

Implementación de ordenación por inserción usando funciones STL.

Requisitos previos : ordenación por inserción , std ::rotate , std::upper_bound , iteradores de C++ .

La idea es usar std::upper_bound para encontrar un elemento que haga que la array no esté ordenada. Luego podemos rotar la parte sin ordenar para que termine ordenada. Podemos atravesar la array haciendo estas operaciones y el resultado será una array ordenada.

El código está fuera de línea a propósito para mostrar un código codificado y fácil de entender.

// C++ program to implement insertion sort using STL.
#include <bits/stdc++.h>
  
// Function to sort the array
void insertionSort(std::vector<int> &vec)
{
    for (auto it = vec.begin(); it != vec.end(); it++)
    {        
        // Searching the upper bound, i.e., first 
        // element greater than *it from beginning
        auto const insertion_point = 
                std::upper_bound(vec.begin(), it, *it);
          
        // Shifting the unsorted part
        std::rotate(insertion_point, it, it+1);        
    }
}
  
// Function to print the array
void print(std::vector<int> vec)
{
    for( int x : vec)
        std::cout << x << " ";
    std::cout << '\n';
}
  
// Driver code
int main()
{
    std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};    
    insertionSort(arr);    
    print(arr);
}

Producción:

1 2 3 4 5 5 6 7

Este artículo es una contribución de Rohit Thapliyal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.