Insertion sort in C++
Tags: cpp, beginners, tutorial, programming
Published: 2024-02-29 03:06:48

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

1. Empiezas con la segunda carta y la comparas con la primera. Si la segunda carta es más pequeña, las intercambias.
2. Ahora, las dos primeras cartas están ordenadas.
3. 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.
4. Repites este proceso con cada carta hasta que toda la mano esté ordenada.

Mira este gif para entenderle mejor: 

![insertion-sort-gif](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/idaqame73idr1bexz4cz.gif)

## 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<size; ++i){
        sortedArray[i] = userArray[i];
    }

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

    // Mostrar resultados
    cout << "Original array: ";
    printArray(userArray,size);
    cout << endl;
    cout << "Sorted array: ";
    printArray(sortedArray,size);
    cout << 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 << "Ingrese la cantidad de elementos para su arreglo: ";
	cin >> 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<size; ++i){
        sortedArray[i] = userArray[i];
    }

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

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

## Ejemplo de uso:

![use-insertion](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ygguvqpsx8j2r53aiswm.png)

## 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](https://github.com/pol-cova/sorting)

**Gif utilizado author Swfung8:**[gif](https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif)