Mastering Insertion Sort with Dynamic Arrays

Introduction

In this lab, we will learn how to implement the Insertion Sort algorithm using dynamic arrays in C++. This algorithm is a simple sorting algorithm that works by dividing the list into two parts, sorted and unsorted, and then inserting each element of the unsorted list into the sorted list in the right position.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/SyntaxandStyleGroup(["`Syntax and Style`"]) cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/AdvancedConceptsGroup(["`Advanced Concepts`"]) cpp(("`C++`")) -.-> cpp/FunctionsGroup(["`Functions`"]) cpp/SyntaxandStyleGroup -.-> cpp/comments("`Comments`") cpp/BasicsGroup -.-> cpp/variables("`Variables`") cpp/BasicsGroup -.-> cpp/data_types("`Data Types`") cpp/BasicsGroup -.-> cpp/operators("`Operators`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/AdvancedConceptsGroup -.-> cpp/pointers("`Pointers`") cpp/FunctionsGroup -.-> cpp/function_parameters("`Function Parameters`") subgraph Lab Skills cpp/comments -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/variables -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/data_types -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/operators -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/while_loop -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/for_loop -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/pointers -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} cpp/function_parameters -.-> lab-96119{{"`Insertion Sort Using Dynamic Array`"}} end

Creating a dynamic array

First, we need to create a dynamic array of integers with a size determined by the user, and fill it with random integers between 1 and 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;
    }

Displaying the unsorted array

Next, we will display the contents of the unsorted array to the user.

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

Implementing the Insertion Sort algorithm

Now, we will implement the Insertion Sort algorithm, which will sort the array in ascending order.

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

Displaying the sorted array

We will display the contents of the sorted array to the user.

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

Freeing memory

Finally, we will free the memory used by the dynamic array.

    // free memory
    delete [] arr;

    return 0;
}

Compile and run the program

Save the file as "sort.cpp" in the ~/project directory.

Compile and run the program in the terminal:

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

Summary

In this lab, we learned how to implement the Insertion Sort algorithm using dynamic arrays in C++. We created a dynamic array with a size determined by the user, filled it with random integers, implemented the Insertion Sort algorithm, and finally displayed the sorted array to the user. We also learned how to free the memory used by the dynamic array.

Insertion Sort Using Dynamic Array