Ordenamiento por inserción con matriz dinámica

Introducción

En este laboratorio, aprenderemos cómo implementar el algoritmo de clasificación por inserción utilizando matrices dinámicas en C++. Este algoritmo es un algoritmo de clasificación simple que funciona dividiendo la lista en dos partes, ordenada y no ordenada, y luego insertando cada elemento de la lista no ordenada en la posición correcta de la lista ordenada.

Creando una matriz dinámica

Primero, necesitamos crear una matriz dinámica de enteros con un tamaño determinado por el usuario y llenarla con enteros aleatorios entre 1 y 100.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Enter the size of the array: ";
    cin >> size;

    // create dynamic array
    arr = new int[size];

    // fill array with random integers between 1 and 100
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

Mostrando la matriz no ordenada

A continuación, mostraremos el contenido de la matriz no ordenada al usuario.

    // display unsorted array
    cout << "Matriz no ordenada: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Implementando el algoritmo de clasificación por inserción

Ahora, implementaremos el algoritmo de clasificación por inserción, que ordenará la matriz en orden ascendente.

    // insertion sort
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

Mostrando la matriz ordenada

Mostraremos el contenido de la matriz ordenada al usuario.

    // display sorted array
    cout << "Matriz ordenada: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Liberando memoria

Finalmente, liberaremos la memoria utilizada por la matriz dinámica.

    // free memory
    delete [] arr;

    return 0;
}

Compila y ejecuta el programa

Guarde el archivo como "sort.cpp" en el directorio ~/project.

Compile y ejecute el programa en la terminal:

$ cd ~/project
$ g++ sort.cpp -o sort
$./sort

Resumen

En este laboratorio, aprendimos cómo implementar el algoritmo de clasificación por inserción utilizando matrices dinámicas en C++. Creamos una matriz dinámica con un tamaño determinado por el usuario, la llenamos con enteros aleatorios, implementamos el algoritmo de clasificación por inserción y, finalmente, mostramos la matriz ordenada al usuario. También aprendimos cómo liberar la memoria utilizada por la matriz dinámica.