Ordenamiento por Inserción en C++: Explicación Paso a Paso para Principiantes

el

 

Ordenamiento por Inserción en C++: Explicación Paso a Paso para Principiantes


Ordenamiento por Inserción en C++: Un Ejemplo Práctico

¡Hola de nuevo! En nuestro viaje por los algoritmos de ordenamiento, hoy vamos a revisar el Ordenamiento por Inserción con un código C++ que te permitirá ver cómo funciona en la práctica. Veremos cómo organiza un conjunto de números, simulando el proceso de clasificar una mano de cartas.

1. Entendiendo el Código: El Corazón del Ordenamiento por Inserción

Este código toma un arreglo predefinido de números (cedula) y lo ordena utilizando el algoritmo de inserción. Luego, muestra el arreglo tanto en orden ascendente como descendente.

Vamos a desglosar el código línea por línea para entender su funcionamiento:

C++
/* ordenamiento por insercion*/ // Un comentario que indica el propósito del código
#include<iostream> // Incluye la librería para entrada/salida de datos (como 'cout' para imprimir)
#include<conio.h>  // Incluye la librería 'conio.h' para funciones de consola (como 'getch()')
                   // Nota: 'conio.h' es específica de algunos compiladores de Windows (ej. MinGW, Borland C++).
                   // Puede que no funcione en otros sistemas o compiladores modernos.

using namespace std; // Permite usar 'cout', 'endl', etc., sin el prefijo 'std::'

int main(){ // La función principal donde empieza la ejecución del programa
	// 1. Declaración e inicialización del arreglo
	int cedula[] = {0,1,2,4,6,7,1,8}; // Un arreglo de enteros llamado 'cedula' con 8 elementos
	                                 // ¡Ojo! Contiene un '1' repetido, que es un buen caso de prueba.
	int i,j,aux; // Declaración de variables auxiliares para los bucles y el almacenamiento temporal

	// 2. Bucle principal del Ordenamiento por Inserción
	// Este bucle 'for' recorre el arreglo desde el segundo elemento (índice 1) hasta el final.
	// La variable 'i' marca el elemento actual que queremos insertar en la parte ya ordenada del arreglo.
	for(i=1;i<8;i++){
		j = i; // 'j' es un índice que nos ayudará a mover los elementos dentro de la parte ordenada.
		       // Inicialmente, 'j' apunta al mismo elemento que 'i'.
		aux = cedula[i]; // Guardamos el valor del elemento actual en 'aux'.
		                 // Este es el valor que intentaremos insertar en su posición correcta.

		// 3. Bucle interno: Desplazamiento e Inserción
		// Este bucle 'while' se encarga de comparar 'aux' (el valor a insertar)
		// con los elementos de la parte ya ordenada (a la izquierda de 'i').
		// Continúa mientras 'j' sea mayor que 0 (para no salirnos del arreglo por la izquierda)
		// Y mientras el elemento anterior ('cedula[j-1]') sea mayor que 'aux'.
		while((j>0) && (cedula[j-1] > aux)){
			cedula[j] = cedula[j-1]; // Si el elemento anterior es mayor, lo movemos una posición a la derecha
			                         // para hacer espacio para 'aux'.
			j--; // Decrementamos 'j' para seguir comparando con el siguiente elemento a la izquierda.
		}
		cedula[j] = aux; // Cuando el bucle 'while' termina, 'j' apunta a la posición correcta
		                 // donde debemos insertar el valor guardado en 'aux'.
	}

	// 4. Mostrar el Arreglo Ordenado (Ascendente)
	cout<<"Orden Ascendente: ";
	for(i=0;i<8;i++){
		cout<<cedula[i]<<" "; // Imprime cada elemento del arreglo
	}

	// 5. Mostrar el Arreglo Ordenado (Descendente)
	cout<<"\nOrden Descendente: "; // Salto de línea antes de mostrar el orden descendente
	// Este bucle recorre el arreglo desde el final hasta el principio para mostrarlo en orden inverso.
	for(i=7;i>=0;i--){
		cout<<cedula[i]<<" ";
	}

	getch(); // Espera una pulsación de tecla antes de cerrar la consola (función de 'conio.h').
	return 0; // Indica que el programa finalizó correctamente.
	system("cls"); // Esta línea no se ejecutará porque 'return 0;' finaliza el programa antes.
	               // 'system("cls")' borraría la pantalla de la consola (específico de Windows).
}

2. ¿Cómo Funciona el Ordenamiento por Inserción? (Traza Manual)

Vamos a tomar el arreglo cedula = {0, 1, 2, 4, 6, 7, 1, 8} y ver cómo se ordena paso a paso:

  • Arreglo Inicial: [0, 1, 2, 4, 6, 7, 1, 8]
  • Parte Ordenada: [0] (el primer elemento siempre se considera ordenado)
  • Parte No Ordenada: [1, 2, 4, 6, 7, 1, 8]

Iteración 1: i = 1 (Elemento cedula[1] = 1)

  • aux = 1
  • j = 1
  • while((j > 0) && (cedula[j-1] > aux))
    • cedula[0] (0) no es mayor que aux (1). La condición es falsa.
  • Inserta aux en cedula[j] (cedula[1]): cedula[1] = 1.
  • Arreglo: [0, 1, 2, 4, 6, 7, 1, 8] (no hubo cambios, 1 ya estaba en su lugar relativo).
  • Parte Ordenada: [0, 1]

Iteración 2: i = 2 (Elemento cedula[2] = 2)

  • aux = 2
  • j = 2
  • while((j > 0) && (cedula[j-1] > aux))
    • cedula[1] (1) no es mayor que aux (2). La condición es falsa.
  • Inserta aux en cedula[j] (cedula[2]): cedula[2] = 2.
  • Arreglo: [0, 1, 2, 4, 6, 7, 1, 8]
  • Parte Ordenada: [0, 1, 2]

Iteración 3: i = 3 (Elemento cedula[3] = 4)

  • ... (similar a las iteraciones anteriores, 4 ya está en su lugar)
  • Arreglo: [0, 1, 2, 4, 6, 7, 1, 8]
  • Parte Ordenada: [0, 1, 2, 4]

Iteración 4: i = 4 (Elemento cedula[4] = 6)

  • ... (similar, 6 ya está en su lugar)
  • Arreglo: [0, 1, 2, 4, 6, 7, 1, 8]
  • Parte Ordenada: [0, 1, 2, 4, 6]

Iteración 5: i = 5 (Elemento cedula[5] = 7)

  • ... (similar, 7 ya está en su lugar)
  • Arreglo: [0, 1, 2, 4, 6, 7, 1, 8]
  • Parte Ordenada: [0, 1, 2, 4, 6, 7]

Iteración 6: i = 6 (¡Elemento cedula[6] = 1!)

  • Este es un paso clave porque 1 es menor que los elementos anteriores.
  • aux = 1
  • j = 6
  • while((j > 0) && (cedula[j-1] > aux))
    • cedula[5] (7) > aux (1): Verdadero. cedula[6] = 7. Arreglo: [0, 1, 2, 4, 6, 7, 7, 8]. j se convierte en 5.
    • cedula[4] (6) > aux (1): Verdadero. cedula[5] = 6. Arreglo: [0, 1, 2, 4, 6, 6, 7, 8]. j se convierte en 4.
    • cedula[3] (4) > aux (1): Verdadero. cedula[4] = 4. Arreglo: [0, 1, 2, 4, 4, 6, 7, 8]. j se convierte en 3.
    • cedula[2] (2) > aux (1): Verdadero. cedula[3] = 2. Arreglo: [0, 1, 2, 2, 4, 6, 7, 8]. j se convierte en 2.
    • cedula[1] (1) > aux (1): Falso. (1 no es mayor que 1). El bucle termina.
  • Inserta aux en cedula[j] (cedula[2]): cedula[2] = 1.
  • Arreglo: [0, 1, 1, 2, 4, 6, 7, 8]
  • Parte Ordenada: [0, 1, 1, 2, 4, 6, 7]

Iteración 7: i = 7 (Elemento cedula[7] = 8)

  • aux = 8
  • j = 7
  • while((j > 0) && (cedula[j-1] > aux))
    • cedula[6] (7) no es mayor que aux (8). La condición es falsa.
  • Inserta aux en cedula[j] (cedula[7]): cedula[7] = 8.
  • Arreglo: [0, 1, 1, 2, 4, 6, 7, 8]
  • Parte Ordenada: [0, 1, 1, 2, 4, 6, 7, 8] (¡Completamente ordenada!)

El bucle for termina.

3. Compilación y Ejecución

Para que puedas ejecutar este código en tu computadora:

  1. Guarda el código: Copia todo el código proporcionado y guárdalo en un archivo llamado, por ejemplo, ordenamiento_insercion.cpp.
  2. Abre una Terminal/Línea de Comandos: Navega hasta el directorio donde guardaste el archivo.
  3. Compila: Si tienes un compilador de C++ (como g++), usa este comando:
    Bash
    g++ ordenamiento_insercion.cpp -o ordenamiento_insercion
    Esto creará un archivo ejecutable (llamado ordenamiento_insercion o ordenamiento_insercion.exe en Windows).
  4. Ejecuta:
    Bash
    ./ordenamiento_insercion
    Verás la salida directamente en tu consola.

4. Salida del Programa

Orden Ascendente: 0 1 1 2 4 6 7 8
Orden Descendente: 8 7 6 4 2 1 1 0

Consideraciones sobre el Código

  • conio.h y getch(): Como se mencionó, conio.h y su función getch() son librerías y funciones que son comunes en entornos de desarrollo antiguos de Windows (como Turbo C++ o Dev-C++). En sistemas operativos Linux/macOS o con compiladores más modernos, getch() puede no estar disponible. Si tienes problemas, puedes simplemente eliminar la línea getch(); y system("cls"); y el include<conio.h>. El programa funcionará igual, aunque la ventana de la consola podría cerrarse inmediatamente.
  • system("cls");: Esta línea también es específica de sistemas Windows y, como está después de return 0;, nunca se ejecuta.

¡Excelente trabajo! Has implementado y entendido el Ordenamiento por Inserción. Este algoritmo es una base sólida para comprender cómo se organizan los datos en la programación. ¿Te gustaría ver cómo se compara con otros métodos de ordenamiento o explorar otro algoritmo?

Ordenamiento por Inserción en C++: Explicación Paso a Paso para Principiantes

¡Hola! En el mundo de la programación, organizar datos es una tarea fundamental. Hoy vamos a explorar uno de los algoritmos de ordenamiento más intuitivos y fáciles de entender: el Ordenamiento por Inserción (Insertion Sort). Imagina que estás organizando una mano de cartas: tomas una carta a la vez y la insertas en el lugar correcto entre las cartas que ya tienes ordenadas. ¡Así funciona el ordenamiento por inserción!

1. ¿Qué es el Ordenamiento por Inserción?

El Ordenamiento por Inserción es un algoritmo de ordenamiento simple que construye la lista final ordenada elemento por elemento, tomando los elementos de la lista de entrada uno a uno y colocándolos en la posición correcta de la parte ya ordenada de la lista.

Es un algoritmo estable (no cambia el orden relativo de elementos con valores iguales) y en el lugar (no necesita espacio adicional significativo). Es muy eficiente para conjuntos de datos pequeños o para listas que ya están casi ordenadas.

La Idea Principal:

  1. Considera que el primer elemento de la lista ya está "ordenado" (es trivialmente una lista ordenada de un solo elemento).
  2. Toma el siguiente elemento de la lista no ordenada.
  3. Compara este elemento con los elementos de la parte ya ordenada de la lista, moviendo los elementos mayores (o menores, dependiendo del orden deseado) una posición hacia adelante para hacer un hueco.
  4. Inserta el elemento en ese hueco.
  5. Repite los pasos 2 a 4 hasta que todos los elementos hayan sido insertados en la parte ordenada.

2. Diagrama de Flujo Conceptual

Para entender mejor la lógica, veamos un diagrama de flujo simplificado.

Fragmento de código
graph TD
    A[Inicio] --> B{Obtener lista de elementos};
    B --> C{Asignar i = 1 (segundo elemento)};
    C --> D{¿i < tamaño de la lista?};
    D -- Sí --> E[Guardar elemento actual (lista[i]) en 'clave'];
    E --> F[Asignar j = i - 1];
    F --> G{¿j >= 0 Y lista[j] > clave?};
    G -- Sí --> H[Mover lista[j] a lista[j+1]];
    H --> I[Decrementar j (j--)];
    I --> G;
    G -- No --> J[Insertar 'clave' en lista[j+1]];
    J --> K[Incrementar i (i++)];
    K --> D;
    D -- No --> L[Fin];

3. Implementación en C++: Paso a Paso

Vamos a escribir el código para ordenar un arreglo de números enteros.

Paso 1: Configuración Básica del Programa

Necesitamos las librerías básicas para entrada/salida.

C++
#include <iostream> // Para cout y endl
#include <vector>   // Para usar std::vector (una alternativa más moderna y flexible a los arrays estáticos)

// Usamos el namespace std para no tener que escribir std::cout, std::endl, etc.
using namespace std;

Paso 2: La Función de Ordenamiento por Inserción

Aquí es donde implementamos la lógica del algoritmo. Crearemos una función que reciba un vector de enteros (que es un arreglo dinámico en C++).

C++
void insertionSort(vector<int>& arr) { // 'arr' se pasa por referencia para modificar el vector original
    int n = arr.size(); // Obtenemos el tamaño del vector

    // El bucle externo recorre el arreglo desde el segundo elemento (índice 1)
    // hasta el final. 'i' marca el límite entre la parte ordenada y no ordenada.
    for (int i = 1; i < n; ++i) {
        // 'clave' es el elemento actual que queremos insertar en la parte ordenada.
        int key = arr[i]; 
        // 'j' es el índice del último elemento de la parte ya ordenada.
        int j = i - 1; 

        // Este bucle interno mueve los elementos de la parte ordenada
        // que son mayores que 'key' una posición hacia adelante
        // para hacer espacio para 'key'.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // Mueve el elemento hacia la derecha
            j = j - 1;           // Retrocede en la parte ordenada
        }
        // Cuando el bucle while termina, hemos encontrado la posición correcta
        // o 'j' se ha vuelto -1 (lo que significa que 'key' es el más pequeño).
        // Insertamos 'key' en su posición correcta.
        arr[j + 1] = key; 
    }
}

Paso 3: Una Función de Ayuda para Mostrar el Arreglo

Es útil tener una función para ver el estado del arreglo antes y después del ordenamiento.

C++
void printArray(const vector<int>& arr) { // 'arr' se pasa por referencia constante porque no la modificamos
    for (int num : arr) { // Bucle 'for-each' para recorrer el vector
        cout << num << " ";
    }
    cout << endl; // Salto de línea al final
}

Paso 4: La Función Principal (main)

Aquí es donde probamos nuestro algoritmo.

C++
int main() {
    // Definimos un vector de enteros desordenado
    vector<int> myVector = {12, 11, 13, 5, 6};

    cout << "Arreglo original: ";
    printArray(myVector); // Mostramos el arreglo antes de ordenar

    insertionSort(myVector); // Llamamos a nuestra función de ordenamiento

    cout << "Arreglo ordenado: ";
    printArray(myVector); // Mostramos el arreglo después de ordenar

    return 0; // Indica que el programa finalizó con éxito
}

4. Compilación y Ejecución

Para compilar y ejecutar este programa:

  1. Guarda el código: Guarda todo el código anterior en un archivo llamado insertion_sort.cpp.
  2. Abre una terminal/línea de comandos: Navega hasta la carpeta donde guardaste el archivo.
  3. Compila: Usa un compilador de C++ (como g++) para compilar:
    Bash
    g++ insertion_sort.cpp -o insertion_sort_ejemplo
    Esto creará un archivo ejecutable llamado insertion_sort_ejemplo (o insertion_sort_ejemplo.exe en Windows).
  4. Ejecuta:
    Bash
    ./insertion_sort_ejemplo

Salida Esperada:

Arreglo original: 12 11 13 5 6 
Arreglo ordenado: 5 6 11 12 13

5. ¿Cómo Funciona Paso a Paso? (Trace Manual)

Vamos a trazar el ejemplo arr = {12, 11, 13, 5, 6} para entender cada iteración.

  • Estado inicial: {12, 11, 13, 5, 6}
    • Parte Ordenada: {12}
    • Parte No Ordenada: {11, 13, 5, 6}

Iteración 1: i = 1 (Elemento arr[1] = 11)

  • key = 11
  • j = 0 (apunta a 12)
  • while (j >= 0 && arr[0] (12) > key (11)) -> true
    • arr[1] = arr[0] (12 se mueve a la posición 1): {12, 12, 13, 5, 6}
    • j = -1
  • while termina.
  • arr[j+1] (que es arr[0]) = key (11): {11, 12, 13, 5, 6}
  • Estado después de Iteración 1: {11, 12, 13, 5, 6}
    • Parte Ordenada: {11, 12}
    • Parte No Ordenada: {13, 5, 6}

Iteración 2: i = 2 (Elemento arr[2] = 13)

  • key = 13
  • j = 1 (apunta a 12)
  • while (j >= 0 && arr[1] (12) > key (13)) -> false (12 no es mayor que 13)
  • while termina.
  • arr[j+1] (que es arr[2]) = key (13): {11, 12, 13, 5, 6} (no hay cambios, ya estaba en su lugar)
  • Estado después de Iteración 2: {11, 12, 13, 5, 6}
    • Parte Ordenada: {11, 12, 13}
    • Parte No Ordenada: {5, 6}

Iteración 3: i = 3 (Elemento arr[3] = 5)

  • key = 5
  • j = 2 (apunta a 13)
  • while (j >= 0 && arr[2] (13) > key (5)) -> true
    • arr[3] = arr[2] (13 se mueve a la posición 3): {11, 12, 13, 13, 6}
    • j = 1
  • while (j >= 0 && arr[1] (12) > key (5)) -> true
    • arr[2] = arr[1] (12 se mueve a la posición 2): {11, 12, 12, 13, 6}
    • j = 0
  • while (j >= 0 && arr[0] (11) > key (5)) -> true
    • arr[1] = arr[0] (11 se mueve a la posición 1): {11, 11, 12, 13, 6}
    • j = -1
  • while termina.
  • arr[j+1] (que es arr[0]) = key (5): {5, 11, 12, 13, 6}
  • Estado después de Iteración 3: {5, 11, 12, 13, 6}
    • Parte Ordenada: {5, 11, 12, 13}
    • Parte No Ordenada: {6}

Iteración 4: i = 4 (Elemento arr[4] = 6)

  • key = 6
  • j = 3 (apunta a 13)
  • while (j >= 0 && arr[3] (13) > key (6)) -> true
    • arr[4] = arr[3] (13 se mueve a la posición 4): {5, 11, 12, 13, 13}
    • j = 2
  • while (j >= 0 && arr[2] (12) > key (6)) -> true
    • arr[3] = arr[2] (12 se mueve a la posición 3): {5, 11, 12, 12, 13}
    • j = 1
  • while (j >= 0 && arr[1] (11) > key (6)) -> true
    • arr[2] = arr[1] (11 se mueve a la posición 2): {5, 11, 11, 12, 13}
    • j = 0
  • while (j >= 0 && arr[0] (5) > key (6)) -> false (5 no es mayor que 6)
  • while termina.
  • arr[j+1] (que es arr[1]) = key (6): {5, 6, 11, 12, 13}
  • Estado después de Iteración 4: {5, 6, 11, 12, 13}
    • Parte Ordenada: {5, 6, 11, 12, 13}
    • Parte No Ordenada: {} (lista completamente ordenada)

El bucle for principal termina porque i ahora es igual a n. El arreglo está completamente ordenado.

6. Cuándo Usar (y Cuándo No Usar) el Ordenamiento por Inserción

Ventajas:

  • Simple de implementar: Su lógica es muy directa.
  • Eficiente para datos pequeños: Para arreglos con menos de 20-30 elementos, su rendimiento es competitivo o incluso superior al de algoritmos más complejos debido a su menor sobrecarga.
  • Eficiente para datos casi ordenados: Si la lista ya está mayormente ordenada, Insertion Sort es muy rápido.
  • Estable: Mantiene el orden relativo de elementos iguales.
  • In-place: Requiere una cantidad mínima de memoria adicional.

Desventajas:

  • Ineficiente para grandes conjuntos de datos: Su complejidad de tiempo en el peor y caso promedio es O(n2), lo que lo hace lento para listas grandes en comparación con algoritmos como Quick Sort o Merge Sort (O(nlogn)).
  • No es ideal para datos inversamente ordenados: Este es su peor caso.

¡Felicidades! Ahora tienes una comprensión sólida del algoritmo de Ordenamiento por Inserción, cómo funciona su lógica y cómo implementarlo en C++. Es un excelente punto de partida para entender algoritmos de ordenamiento más complejos.

Comentarios

Publicar un comentario