C++ Coding Test Course, Insertion Sort

Hello! In this post, I will discuss Insertion Sort, which is one of the algorithms frequently asked in coding tests using C++. Insertion Sort is a very intuitive sorting algorithm that works by inserting new data into a sorted array. So, shall we get started?

Problem Description

You have an array containing given integers. Output the result of sorting this array in ascending order using Insertion Sort.

Input Format

The first line contains the size of the array N. (1 ≤ N ≤ 1000)

The second line contains N integers separated by spaces. (Each integer is -1000 ≤ x ≤ 1000)

Output Format

Output the sorted array in one line. Each element is separated by a space.

Example

        Input:
        5
        3 2 1 5 4
  
        Output:
        1 2 3 4 5

Algorithm Explanation

Insertion Sort works by inserting new values into a sorted array. The algorithm proceeds in the following steps:

  1. The first element is considered to be sorted.
  2. Starting from the second element, find the position to insert it in the sorted array.
  3. Shift the elements of the array to the right one step to find the position for the new element.
  4. When the correct position is found, insert the new element.
  5. Repeat this process for all elements in the array.

C++ Code Implementation

Now let’s implement the above algorithm in C++. The code is as follows:

        
        #include <iostream>
        #include <vector>

        using namespace std;

        void insertionSort(vector<int>& arr) {
            int n = arr.size();
            for (int i = 1; i < n; i++) {
                int key = arr[i];
                int j = i - 1;

                // Move elements greater than key one position ahead
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key; // Insert the key at the correct position
            }
        }

        int main() {
            int N;
            cin >> N;
            vector<int> arr(N);

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

            insertionSort(arr);

            for (int i = 0; i < N; i++) {
                cout << arr[i];
                if (i < N - 1) cout << " "; // To avoid adding a space after the last element
            }

            return 0;
        }

Code Explanation

The above code is an implementation of the Insertion Sort algorithm in C++. Let’s take a look at the main parts:

  • Including Header Files: Includes <iostream> and <vector> to handle input/output and to use dynamic arrays.
  • insertionSort Function: This function sorts the array. It sets the key for each element and finds its position to insert in the sorted array.
  • Main Function: Takes the size of the array as input, reads the array, calls the insertionSort function to sort it, and finally outputs the sorted result.

Time Complexity Analysis

The time complexity of Insertion Sort is as follows:

  • Worst Case: O(n^2) (when the array is in reverse order)
  • Average Case: O(n^2)
  • Best Case: O(n) (when the array is already sorted)

Due to this time complexity, Insertion Sort is efficient for small arrays but performs poorly on larger arrays.

Advantages and Disadvantages

Advantages

  • Easy to implement and understand
  • Very efficient for small data sets
  • It is a stable sort (the order of equal elements is preserved)

Disadvantages

  • Not efficient for large input sizes due to O(n^2) time complexity
  • Can be inefficient in terms of memory usage since it directly modifies the array

Additional Examples to Enhance Understanding

Let’s visualize the operation of Insertion Sort through additional examples. Below is an example demonstrating the process of Insertion Sort.

Example

        Input:
        6
        4 3 5 1 2 6
  
        Process:
        Initial array: 4 3 5 1 2 6
        Step 1: [4] [3] 5 1 2 6 → 3 4 5 1 2 6
        Step 2: 3 4 [5] [1] 2 6 → 3 4 5 1 2 6
        Step 3: 3 4 5 [1] [2] 6 → 1 3 4 5 2 6
        Step 4: 1 3 4 5 [2] 6 → 1 2 3 4 5 6
        Step 5: 1 2 3 4 5 [6] → 1 2 3 4 5 6

Conclusion

Today we learned about Insertion Sort using C++. Remember that Insertion Sort is a simple yet useful algorithm, effective for small data sets. In the next post, we will cover a more complex sorting algorithm called Quick Sort. If you have any questions or comments, please leave them below. Thank you!

References