Insertion Sort Usando Array Dinâmico

Introdução

Neste laboratório, aprenderemos como implementar o algoritmo Insertion Sort usando arrays dinâmicos em C++. Este algoritmo é um algoritmo de ordenação simples que funciona dividindo a lista em duas partes, ordenada e não ordenada, e então inserindo cada elemento da lista não ordenada na lista ordenada na posição correta.

Criando um array dinâmico

Primeiramente, precisamos criar um array dinâmico de inteiros com um tamanho determinado pelo usuário e preenchê-lo com inteiros aleatórios entre 1 e 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;
    }

Exibindo o array não ordenado

Em seguida, exibiremos o conteúdo do array não ordenado para o usuário.

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

Implementando o algoritmo Insertion Sort

Agora, implementaremos o algoritmo Insertion Sort, que irá ordenar o array em ordem crescente.

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

Exibindo o array ordenado

Exibiremos o conteúdo do array ordenado para o usuário.

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

Liberando memória

Finalmente, liberaremos a memória utilizada pelo array dinâmico.

    // free memory
    delete [] arr;

    return 0;
}

Compilar e executar o programa

Salve o arquivo como "sort.cpp" no diretório ~/project.

Compile e execute o programa no terminal:

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

Resumo

Neste laboratório, aprendemos como implementar o algoritmo Insertion Sort usando arrays dinâmicos em C++. Criamos um array dinâmico com um tamanho determinado pelo usuário, preenchemos com inteiros aleatórios, implementamos o algoritmo Insertion Sort e, finalmente, exibimos o array ordenado para o usuário. Também aprendemos como liberar a memória utilizada pelo array dinâmico.