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<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:
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
Top comments (0)