Insertion sort in C++

Introducción

En términos simples el insertion sort es como ordenar una mano de cartas:

Empiezas con la segunda carta y la comparas con la primera. Si la segunda carta es más pequeña, las intercambias.
Ahora, las dos primeras cartas están ordenadas.
Pasas a la tercera carta y la comparas con la segunda. Si es más pequeña, la mueves a la posición correcta entre las cartas ya ordenadas.
Repites este proceso con cada carta hasta que toda la mano esté ordenada.

Mira este gif para entenderle mejor:

Programa para ordenar un array con inserción

El primer paso es identificar las funciones que podremos utilizar para este programa, las cuales serian: printArray, fillArray, insertion.

printArray: Esta función se utiliza para imprimir el arreglo.
fillArray: Esta función se utiliza para llenar el arreglo con los datos que da el usuario.
insertion: Esta función se utiliza para realizar el ordenamiento.

`printArray`

La función printArray recibe un arreglo de números enteros y su tamaño. Luego, imprime los elementos del arreglo en la consola, separados por comas y encerrados entre corchetes. Por ejemplo, si se pasa el arreglo {1, 2, 3, 4, 5}, la función imprimirá [1, 2, 3, 4, 5]. Esto permite visualizar fácilmente los elementos del arreglo en un formato legible.
Codigo:



// Print array function

void printArray( const int *userArray , int size){

    // Imprimir cada elemento con un for loop

    cout << "[" << userArray[0];

    for (int i=1; i < size; ++i){

        cout << "," << userArray[i];

    }

    cout << "]" << endl;

}

`fillArray`

La función fillArray recibe como argumento un puntero a un arreglo de enteros y el tamaño del arreglo. Utiliza un bucle for para iterar sobre cada posición del arreglo. En cada iteración, le pide al usuario que ingrese un valor para esa posición del arreglo utilizando cin >> userArray[i];. De esta manera, la función permite al usuario llenar un arreglo con valores ingresados desde el teclado.
Codigo:



// Fill array

void fillArray(int *userArray, int size){

    // For loop para ingresar elementos

    for (int i = 0; i < size; ++i) {

        // utilizo i+1 para facilitar al usuario el ingresar el elemento

        cout << "Ingrese elemento " << i+1 << " : ";

        // leemos de teclado y lo almacenamos en el arreglo en la posición i

        cin >> userArray[i];

    }

}

`insertion`

La función insertion toma un arreglo de números enteros, lo copia, lo ordena utilizando el algoritmo de ordenación por inserción y luego muestra el arreglo original y el arreglo ordenado. Esto ayuda a los principiantes a comprender cómo funciona el algoritmo de inserción y cómo se pueden ordenar los arreglos en la práctica.



// Insertion algorithm

void insertion(const int *userArray, int size){

    // Print header

    cout << setfill('-') << setw(40) << "" << endl;

    cout << "|           Insertion sort          |" << endl;

    cout << setfill('-') << setw(40) << "" << endl;

    // Puntero temporal asociado al arreglo

    auto *sortedArray = new int[size];

// Copia del arreglo dado por el usuario
for (int i=0; i&lt;size; ++i){
    sortedArray[i] = userArray[i];
}

// Insertion algorithm
for (int i=1; i&lt;size; ++i){
    int k = sortedArray[i];
    int j = i-1;
    while (j &gt;= 0 &amp;&amp; sortedArray[j] &gt; k){
        sortedArray[j+1] = sortedArray[j];
        --j;
    }
    sortedArray[j+1] = k;
}

// Mostrar resultados
cout &lt;&lt; "Original array: ";
printArray(userArray,size);
cout &lt;&lt; endl;
cout &lt;&lt; "Sorted array: ";
printArray(sortedArray,size);
cout &lt;&lt; endl;
// Deallocate memory
delete [] sortedArray;



    

    




}

Implementación

Ahora que ya sabemos cuales funciones utilizaremos, tendremos que saber como implementarlas, en el archivo main.cpp tenemos esto:



// Encabezados

// librerías estándar

  
  
  include <iostream>


  
  
  include <iomanip>


using namespace std;

// Prototipo de las funciones 

// Esto se utiliza para no tener problema con la definición de las funciones 

// cuando se utilizan en el código principal. Ayuda al compilador a conocer 

// la firma de las funciones antes de que se definan más adelante en el código.

void printArray( const int *userArray , int size);

void fillArray(int *userArray, int size);

void insertion(const int *userArray, int size);

// Funcion principal

int main() {

        // Variable para almacenar el tamaño deseado del arreglo

    int size;

        // Variable para almacenar el arreglo de enteros ingresados por el usuario

        int *array;

// Solicitamos la cantidad de elementos 
cout &lt;&lt; "Ingrese la cantidad de elementos para su arreglo: ";
cin &gt;&gt; size;
// Definimos arreglo con el tamaño ingresado por el usuario
array = new int[size];
// Llenamos el arreglo
fillArray(array, size);
// Ordenamos el arreglo
insertion(array, size);
// deallocate memory
delete [] array;
return 0;



    

    




}

// Funciones desarrolladas

// Print array function

void printArray( const int *userArray , int size){

    // Imprimir cada elemento con un for loop

    cout << "[" << userArray[0];

    for (int i=1; i < size; ++i){

        cout << "," << userArray[i];

    }

    cout << "]" << endl;

}

// Fill array

void fillArray(int *userArray, int size){

    // For loop para ingresar elementos

    for (int i = 0; i < size; ++i) {

        // utilizo i+1 para facilitar al usuario el ingresar el elemento

        cout << "Ingrese elemento " << i+1 << " : ";

        // leemos de teclado y lo almacenamos en el arreglo en la posición i

        cin >> userArray[i];

    }

}

// Insertion algorithm

void insertion(const int *userArray, int size){

    // Print header

    cout << setfill('-') << setw(40) << "" << endl;

    cout << "|           Insertion sort          |" << endl;

    cout << setfill('-') << setw(40) << "" << endl;

    // Puntero temporal asociado al arreglo

    auto *sortedArray = new int[size];

// Copia del arreglo dado por el usuario
for (int i=0; i&lt;size; ++i){
    sortedArray[i] = userArray[i];
}

// Insertion algorithm
for (int i=1; i&lt;size; ++i){
    int k = sortedArray[i];
    int j = i-1;
    while (j &gt;= 0 &amp;&amp; sortedArray[j] &gt; k){
        sortedArray[j+1] = sortedArray[j];
        --j;
    }
    sortedArray[j+1] = k;
}

// Mostrar resultados
cout &lt;&lt; "Original array: ";
printArray(userArray,size);
cout &lt;&lt; endl;
cout &lt;&lt; "Sorted array: ";
printArray(sortedArray,size);
cout &lt;&lt; endl;
// Deallocate memory
delete [] sortedArray;



    

    




}

Ejemplo de uso:

Conclusion

La ordenación por inserción es un método sencillo y rápido para ordenar elementos en un arreglo. Aunque es eficiente para conjuntos de datos pequeños, puede volverse menos eficaz con conjuntos de datos grandes. Es importante elegir el algoritmo de ordenación adecuado según el tamaño y la naturaleza de los datos a ordenar.

Puedes encontrar el codigo completo en:repositorio

Gif utilizado author Swfung8:gif

Blog

Insertion sort in C++

Paul Contreras

Introducción

Programa para ordenar un array con inserción

`printArray`

`fillArray`

`insertion`

Implementación

include <iostream>

include <iomanip>

Ejemplo de uso:

Conclusion

Join Our Newsletter. No Spam, Only the good stuff.

Related