Dominando el ordenamiento por inserción con matrices dinámicas

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.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/AdvancedConceptsGroup(["Advanced Concepts"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp/BasicsGroup -.-> cpp/operators("Operators") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/AdvancedConceptsGroup -.-> cpp/pointers("Pointers") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/user_input("User Input") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") subgraph Lab Skills cpp/operators -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/arrays -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/for_loop -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/while_loop -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/pointers -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/output -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/user_input -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} cpp/files -.-> lab-96119{{"Ordenamiento por inserción con matriz dinámica"}} end

Crear 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;
    }

Mostrar 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;
    }

Mostrar 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;

Liberar memoria

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

    // free memory
    delete [] arr;

    return 0;
}

Compilar y ejecutar 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.