Insertion Sort | DSA in C++ - Software Development PDF Download

Introduction

When it comes to sorting algorithms, Insertion Sort is one of the simplest and easiest to understand. It is a comparison-based sorting algorithm that builds the final sorted array one item at a time. Insertion Sort is particularly useful for small data sets or partially sorted arrays. In this article, we will explore the concept of Insertion Sort, provide a step-by-step explanation of how it works, and present multiple examples and code snippets in C++ to solidify your understanding.

Understanding Insertion Sort

Insertion Sort works by dividing the array into two parts: the sorted part and the unsorted part. Initially, the sorted part contains only the first element of the array, while the rest of the elements are in the unsorted part. The algorithm iterates through the unsorted part, selects an element, and places it in the correct position within the sorted part.

The steps of the Insertion Sort algorithm can be summarized as follows:

• Start with the second element of the array.
• Compare the second element with the elements in the sorted part.
• If the element is smaller, shift the sorted elements to the right.
• Repeat step 3 until the correct position for the element is found.
• Move on to the next unsorted element and repeat steps 2-4.
• Repeat the process until all elements are sorted.

Example 1: Sorting an Array using Insertion Sort
Let's take a look at an example to illustrate the Insertion Sort algorithm:
Consider the following array of integers: [5, 2, 4, 6, 1, 3]

• Step 1: Initially, the first element (5) is considered sorted, and the rest are unsorted.
  Sorted: [5], Unsorted: [2, 4, 6, 1, 3]
• Step 2: The second element (2) is compared with the sorted element (5). Since 2 is smaller than 5, it needs to be inserted before 5.
  Sorted: [2, 5], Unsorted: [4, 6, 1, 3]
• Step 3: The third element (4) is compared with the sorted elements (2, 5). It is placed between 2 and 5.
  Sorted: [2, 4, 5], Unsorted: [6, 1, 3]
• Step 4: The fourth element (6) is greater than all the sorted elements, so it remains at its position.
  Sorted: [2, 4, 5, 6], Unsorted: [1, 3]
• Step 5: The fifth element (1) is compared with the sorted elements (2, 4, 5, 6). It is placed at the beginning of the sorted part.
  Sorted: [1, 2, 4, 5, 6], Unsorted: [3]
• Step 6: The last element (3) is inserted between 2 and 4.
  Sorted: [1, 2, 3, 4, 5, 6], Unsorted: []

The final sorted array is [1, 2, 3, 4, 5, 6].

C++ Implementation of Insertion Sort

Now, let's dive into the C++ code that implements the Insertion Sort algorithm:

#include <iostream>

void insertionSort(int arr[], int size) {

    for (int i = 1; i < size; i++) {

        int key = arr[i];

        int j = i - 1;

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

int main() {

    int arr[] = {5, 2, 4, 6, 1, 3};

    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    std::cout << "Sorted array: ";

    for (int i = 0; i < size; i++) {

        std::cout << arr[i] << " ";

    }

    std::cout << std::endl;

    return 0;

}

Explanation of the Code

• The 'insertionSort' function takes an array ('arr') and its size ('size') as input.
• It iterates from the second element ('i = 1') to the last element of the array.
• For each element, it stores the current element in the 'key' variable and sets j to the previous index ('i - 1').
• It then compares the 'key' with the elements in the sorted part ('arr[0]' to 'arr[j]').
• If an element is greater than the 'key', it shifts the element one position to the right ('arr[j + 1] = arr[j]') and decrements 'j'.
• This process continues until all the elements greater than the 'key' are shifted.
• Finally, the 'key' is placed in the correct position ('arr[j + 1] = key').
• The sorted array is printed using a 'for' loop in the 'main' function.

Output of the Code
The output of the above code will be:

Sorted array: 1 2 3 4 5 6

Sample Problems

Now that you have a good understanding of Insertion Sort, try solving the following problems:

Problem 1: Sort the following array in non-decreasing order using Insertion Sort: [9, 7, 5, 8, 3, 1]

The sorted array will be: [1, 3, 5, 7, 8, 9]

Problem 2: Implement Insertion Sort in reverse order (non-increasing) in C++.

Simply modify the comparison in the while loop to 'arr[j] < key' instead of 'arr[j] > key'.

Problem 3: What is the time complexity of Insertion Sort?

The time complexity of Insertion Sort is O(n^2) in the worst and average cases. However, it has an O(n) best case time complexity when the array is already sorted.

By solving these problems and experimenting with different scenarios, you will reinforce your understanding of Insertion Sort and improve your problem-solving skills.

Conclusion

Insertion Sort is a straightforward sorting algorithm that is easy to understand and implement. It is particularly useful for small or partially sorted arrays. In this article, we explored the concept of Insertion Sort, provided step-by-step explanations, and demonstrated its implementation in C++. By practicing with the provided examples and solving the sample problems, you can gain hands-on experience with Insertion Sort and strengthen your grasp of this fundamental sorting algorithm.