Insertion Sort in Ascending Order in C++

1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Ascending Order using the Insertion Sort algorithm.

Insertion Sort is an intuitive sorting algorithm based on how one might sort a hand of playing cards. The fundamental principle is to build your sorted array, one item at a time. In the process, every incoming item is repeatedly compared with the items already sorted and then placed in its appropriate position.

2. Program Overview

The C++ program comprises:

1. insertionSort(): The primary function that employs Insertion Sort to sort the array.

2. printArray(): A function to exhibit the array contents.

3. main(): The chief function to initiate the program.

3. Code Program

#include<iostream>
using namespace std;

// Main function to perform insertion sort
void insertionSort(int arr[], int n) {
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // The element to be compared
        j = i - 1;
        
        // Move elements of arr[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Place the key in its correct position
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Driver function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Original array: \n";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array in ascending order: \n";
    printArray(arr, n);
    return 0;
}

Output:

Original array:
64 25 12 22 11 
Sorted array in ascending order: 
11 12 22 25 64 

4. Step By Step Explanation

1. insertionSort(): Each element, starting from the second, is compared to elements before it. If an element (called key in the program) is less than its preceding elements, these elements are shifted to the right until the correct position for the key is found, where it's then placed.

2. printArray(): It's a utility to visualize the array's state. It helps in observing the array before and after sorting.

3. main(): This function sets the ball rolling. It creates a sample array, displays it, calls the insertion sort function, and then showcases the sorted array.

Insertion Sort is beneficial when the array is almost sorted, as it provides adaptive behavior. The running time becomes linear in nearly sorted situations. Nonetheless, its worst-case and average-case scenarios are O(n^2), making it less suitable for extensive lists compared to more advanced algorithms.

Related C++ Programs on Sorting Algorithms

• Bubble Sort in Ascending Order in C++
• Bubble Sort in Descending Order in C++
• Selection Sort in Ascending Order in C++
• Selection Sort in Descending Order in C++
• Insertion Sort in Ascending Order in C++
• Insertion Sort in Descending Order in C++
• Merge Sort in Ascending Order in C++
• Merge Sort in Descending Order in C++
• Quick Sort in Ascending Order in C++
• Quick Sort in Descending Order in C++
• Heap Sort in Ascending Order in C++
• Heap Sort in Descending Order in C++