Skip to main content

Featured

Merge Sort in C++

  Merge Sort in C++ Introduction Merge Sort is a popular sorting algorithm that follows the Divide and Conquer approach. It divides an array into smaller subarrays, recursively sorts those subarrays, and finally merges the sorted subarrays to produce a completely sorted array. In this tutorial, we will learn how to implement Merge Sort in C++ . The program divides the array into two halves using the mid index, recursively sorts both halves, and then combines them using the merge() function. Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases. Table of Contents Algorithm C++ Program Input Sample Output Output Explanation Dry Run Flow of Execution Time Complexity Space Complexity Applications Key Points Interview Questions Frequently Asked Questions Keywords Conclusion Algorithm Start the program. Read the size of the array. Read the array elements from the user. Call the mer...
Post a Comment
Read more
Labels

C++ Program to Implement Insertion Sort

 

C++ Program to Implement Insertion Sort

Introduction

In this C++ program, we will learn how to implement Insertion Sort. Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted array one element at a time by comparing each element with the elements before it.

In each pass, the algorithm compares the current element with the previous elements. If the current element is smaller than the previous element, the two elements are swapped. This process continues until the current element reaches its correct position.

Insertion Sort is easy to understand and implement, making it useful for learning the basic concepts of sorting algorithms.

C++ Program


#include<iostream>
using namespace std;

int main()
{
    int num;

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

    int a[num];

    cout << "Enter " << num << " elements in the array: " << endl;

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

    cout << "Before sorting:" << endl;

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

    // Insertion Sort
    for(int i = 1; i < num; i++)
    {
        for(int j = i; j > 0; j--)
        {
            if(a[j] < a[j - 1])
            {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }

    cout << "\nAfter sorting:" << endl;

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

    return 0;
}

Sample Output


Enter the size of the array:
6
Enter 6 elements in the array:
64 25 12 22 11 90

Before sorting:
64 25 12 22 11 90

After sorting:
11 12 22 25 64 90

Explanation

Step 1: Declare Variables

First, we declare an integer variable num to store the size of the array. The array a[num] is used to store the elements entered by the user. 


int num;

The user enters the number of elements, and the array is created based on that size. 


int a[num];

Step 2: Read the Size of the Array

The program asks the user to enter the size of the array. 


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

For example, if the user enters 6, the program will work with six array elements.

Step 3: Read Array Elements

The program uses a for loop to read all the elements into the array. 


cout << "Enter " << num << " elements in the array: " << endl;

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

For example, the input array can be: 


64 25 12 22 11 90

Step 4: Display the Array Before Sorting

Before performing the sorting operation, the program displays the original array. This helps us compare the array before and after sorting. 


cout << "Before sorting:" << endl;

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

For the given input, the output will be: 


Before sorting:
64 25 12 22 11 90

Step 5: Start Insertion Sort

The insertion sort operation starts with the element at index 1. The element at index 0 is considered sorted because a single element is already sorted by itself. 


for(int i = 1; i < num; i++)
{
    ...
}

The variable i represents the current element that needs to be placed in its correct position.

For example: 


64 25 12 22 11 90
↑  ↑
0  1

i = 1

Here, 64 is considered the sorted portion and 25 is the current element that needs to be compared with the previous element.

Step 6: Compare the Current Element

The inner loop moves backward from the current index toward the beginning of the array. It compares the current element with the element immediately before it. 


for(int j = i; j > 0; j--)
{
    if(a[j] < a[j - 1])
    {
        ...
    }
}

The condition: 


a[j] < a[j - 1]

checks whether the current element is smaller than the previous element. If it is smaller, the two elements are swapped.

For example: 


64 25 12 22 11 90

25 < 64
Yes

Since 25 is smaller than 64, they are swapped. 


25 64 12 22 11 90

Step 7: Swap the Elements

When the current element is smaller than the previous element, the program swaps the two elements using a temporary variable. 


int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;

For example, if the array contains: 


64 25 12 22 11 90

The comparison is: 


25 < 64

Therefore, the elements are swapped: 


25 64 12 22 11 90

The current element has now moved one position toward its correct position.

Step 8: Continue Moving Backward

The inner loop continues moving backward as long as the current element is smaller than the previous element. This allows the element to move to its correct position within the sorted portion.

For example, consider: 


25 64 12 22 11 90

When 12 is selected, it is compared with 64. Since 12 is smaller, they are swapped: 


25 12 64 22 11 90

Now 12 is compared with 25: 


12 < 25

Again, they are swapped: 


12 25 64 22 11 90

Therefore, 12 reaches its correct position.

Step 9: Repeat the Process

The outer loop continues with the next element. During every pass, the current element is compared with the elements before it and moved toward its correct position.

For the input: 


64 25 12 22 11 90

The array changes as follows: 


Initial:
64 25 12 22 11 90

Pass 1:
25 64 12 22 11 90

Pass 2:
12 25 64 22 11 90

Pass 3:
12 22 25 64 11 90

Pass 4:
11 12 22 25 64 90

Pass 5:
11 12 22 25 64 90

After all passes, the complete array becomes sorted in ascending order.

Step 10: Display the Sorted Array

Finally, the program displays the sorted array using a for loop. 


cout << "\nAfter sorting:" << endl;

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

The output will be: 


After sorting:
11 12 22 25 64 90

Dry Run

Input


Array = {64, 25, 12, 22, 11, 90}

Insertion Sort Processing

Pass Current Element Comparison Action Array After Pass
1 25 25 < 64 Swap 25 64 12 22 11 90
2 12 12 < 64, 12 < 25 Swap 12 25 64 22 11 90
3 22 22 < 64, 22 < 25 Swap 12 22 25 64 11 90
4 11 11 < 64, 25, 22, 12 Swap 11 12 22 25 64 90
5 90 90 < 64 No swap 11 12 22 25 64 90

Final Sorted Array

Index Value
011
112
222
325
464
590

How Insertion Sort Works

Insertion Sort divides the array into two parts:

  • Sorted portion – Elements that are already arranged in sorted order.
  • Unsorted portion – Elements that still need to be placed in their correct positions.

During every pass, one element from the unsorted portion is selected and compared with the elements in the sorted portion. If necessary, it is moved toward the beginning until it reaches its correct position.

For example: 


64 25 12 22 11 90
↑
Sorted portion

After Pass 1: 


25 64 | 12 22 11 90
       -------------
       Unsorted portion

After Pass 2: 


12 25 64 | 22 11 90
          -----------
          Unsorted portion

After Pass 3: 


12 22 25 64 | 11 90
             --------
             Unsorted portion

After Pass 4: 


11 12 22 25 64 | 90
                ----
                Unsorted portion

After Pass 5: 


11 12 22 25 64 90
------------------
    Sorted Array

Finally, the complete array becomes sorted.

Time Complexity

Case Time Complexity
Best Case O(n²)
Average Case O(n²)
Worst Case O(n²)

Note: The exact code used in this program performs comparisons through the nested loops even when the array is already sorted. Therefore, for this implementation, the best-case time complexity is O(n²).

In the best-case optimized version of Insertion Sort, where the algorithm stops when the current element is already in the correct position, the best-case complexity can be O(n).

Overall Time Complexity of this program: O(n²)

Space Complexity

Insertion Sort performs sorting directly inside the original array. It uses only a few additional variables such as i, j, and temp.

  • Array Storage: O(n)
  • Extra Space: O(1)

Auxiliary Space Complexity: O(1)

Therefore, Insertion Sort is an in-place sorting algorithm.

Key Points

  • Insertion Sort is a simple comparison-based sorting algorithm.
  • It builds the sorted portion of the array one element at a time.
  • The first element is considered sorted.
  • Each new element is compared with the elements before it.
  • The inner loop moves backward through the sorted portion.
  • Elements are swapped when the current element is smaller than the previous element.
  • For this implementation, the time complexity is O(n²) in all cases.
  • Its auxiliary space complexity is O(1).
  • Insertion Sort is an in-place sorting algorithm.
  • It is easy to understand and implement, making it useful for beginners.

Advantages of Insertion Sort

  • Simple and easy to implement.
  • Requires very little extra memory.
  • Works directly on the original array.
  • Efficient for small datasets.
  • Easy to understand because it works similarly to arranging elements one by one.
  • Useful for understanding the fundamentals of sorting algorithms.

Disadvantages of Insertion Sort

  • Its time complexity can be O(n²) for this implementation.
  • It is inefficient for large datasets.
  • The program may perform many swaps when the array is in reverse order.
  • Faster algorithms such as Merge Sort and Quick Sort are generally preferred for large datasets.

Keywords

Insertion Sort in C++, C++ Insertion Sort Program, Insertion Sort Algorithm, Insertion Sort Example, Insertion Sort Implementation in C++, Insertion Sort Dry Run, Insertion Sort Time Complexity, Insertion Sort Space Complexity, Sorting Algorithms in C++, C++ Sorting Programs, Insertion Sort DSA, C++ DSA Programs, Sorting Algorithm in C++, Insertion Sort Interview Questions, C++ Coding Practice.

Conclusion

This program demonstrates how to implement Insertion Sort in C++. The algorithm builds the sorted portion of the array one element at a time by comparing the current element with the elements before it.

When a smaller element is found, the program swaps the elements and continues moving backward until the element reaches its correct position.

Insertion Sort requires only O(1) auxiliary space because it sorts the elements directly within the original array. For the implementation used in this program, the time complexity is O(n²).

Although Insertion Sort is not the best choice for large datasets, it is an important algorithm for understanding the fundamentals of sorting and comparison-based algorithms.

Labels:

Comments

Post a Comment

Popular Posts

🌙