Insertion Sort in C++ (using class , constructor)

C++ • SORTING ALGORITHM

Insertion Sort

ALGORITHM

Insertion Sort

TIME COMPLEXITY

O(n²)

SPACE COMPLEXITY

O(n)

ORDER

Ascending

C++ Implementation

● ● ● insertion_sort.cpp

#include <iostream>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Insertion Sort function
    void insertionSort()
    {
        for(int i = 1; i < n; i++)
        {
            int key = a[i];
            int j = i - 1;

            while(j >= 0 && a[j] > key)
            {
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = key;
        }
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.insertionSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes the input/output library required for cin and cout.

using namespace std;

Allows us to use standard C++ features without writing std:: repeatedly.

class ArraySort

Creates a class named ArraySort containing the array and sorting functions.

int n;

Stores the number of elements in the array.

int a[100];

Declares an integer array capable of storing up to 100 elements.

ArraySort()

This is the class constructor. It runs automatically when the object is created.

n = 0;

Initializes the array length to zero.

void input()

Defines a function that accepts the array length and array elements from the user.

cin >> n;

Reads the length of the array.

cin >> a[i];

Reads each element and stores it inside the array.

void insertionSort()

Defines the function responsible for sorting the array using insertion sort.

int key = a[i];

Stores the current element that needs to be inserted into the sorted portion.

int j = i - 1;

Points to the element immediately before the current element.

while(j >= 0 && a[j] > key)

Checks whether the previous element is larger than the key. If it is, that element must move right.

a[j + 1] = a[j];

Shifts the larger element one position to the right.

j--;

Moves the index one position toward the beginning of the array.

a[j + 1] = key;

Places the key into its correct sorted position.

void output()

Defines the function that displays the sorted array.

ArraySort obj;

Creates an object named obj of the ArraySort class. The constructor runs automatically.

obj.input();

Calls the input function to read the array.

obj.insertionSort();

Calls the insertion sort function to arrange the elements in ascending order.

obj.output();

Calls the output function to display the sorted array.

return 0;

Indicates that the program has completed successfully.

How insertion sort works: It divides the array into a sorted and an unsorted portion. Each new element is picked from the unsorted portion and inserted into its correct position in the sorted portion.