Insertion Sorting

Intuition

Insertion sort builds a sorted array one element at a time by repeatedly picking the next element and inserting it into its correct position within the already sorted part of the array.

Approach

In each iteration, select an element from the unsorted part of the array using an outer loop.
Place this element in its correct position within the sorted part of the array.
Use an inner loop to shift the remaining elements as necessary to accommodate the selected element. This involves swapping elements until the selected element is in its correct position.
Continue this process until the entire array is sorted.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
// Insertion Sort
    vector<int> insertionSort(vector<int>& nums) {
        int n = nums.size();
        // Traverse through the array
        for (int i = 0; i <= n - 1; i++) {
            int j = i;
            // Swap elements till we reach a greater element
            while (j > 0 && nums[j - 1] > nums[j]) {
                swap(nums[j - 1], nums[j]);
                j--;
            }
        }
        return nums;
    }
};

int main() {
    // Create an instance of solution class
    Solution solution;
    
    vector<int> nums = {13, 46, 24, 52, 20, 9};
    
    cout << "Before Using Insertion Sort: " << endl;
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    // Function call for insertion sort
    nums = solution.insertionSort(nums);

    cout << "After Using Insertion Sort: " << endl;
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

import java.util.*;

class Solution {
// Insertion Sort
    public int[] insertionSort(int[] nums) {
        int n = nums.length;
        // Traverse through the array
        for (int i = 1; i < n; i++) {
            int key = nums[i];
            int j = i - 1;

            // Swap elements till we reach greater element
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j = j - 1;
            }
            nums[j + 1] = key;
        }
        return nums;
    }

    public static void main(String[] args) {
        // Create an instance of solution class
        Solution solution = new Solution();

        int[] nums = {13, 46, 24, 52, 20, 9};

        System.out.println("Before Using Insertion Sort: " + Arrays.toString(nums));

        // Function call for insertion sort
        nums = solution.insertionSort(nums);

        System.out.println("After Using Insertion Sort: " + Arrays.toString(nums));
    }
}


class Solution:
    # Insertion Sort
    def insertionSort(self, nums):
        n = len(nums)
        # Traverse through the array
        for i in range(n):
            j = i
            # Swap elements till we reach greater element
            while j > 0 and nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
        return nums

# Main Function
if __name__ == "__main__":
    # Create an instance
    solution = Solution()

    nums = [13, 46, 24, 52, 20, 9]

    print("Before Using Insertion Sort:", nums)

    # Call the insertion_sort function
    sorted_nums = solution.insertion_sort(nums)

    print("After Using Insertion Sort:", sorted_nums)

class Solution {
// Insertion Sort
    insertionSort(nums) {
        let n = nums.length;
        // Traverse through the array
        for (let i = 0; i < n; i++) {
            let j = i;
            // Swap elements till we reach greater element
            while (j > 0 && nums[j - 1] > nums[j]) {
                [nums[j - 1], nums[j]] = [nums[j], nums[j - 1]];
                j--;
            }
        }
        return nums;
    }
}

// Create an instance of solution class
let solution = new Solution();

let nums = [13, 46, 24, 52, 20, 9];

console.log("Before Using Insertion Sort:", nums);

// Function call for insertion sort
nums = solution.insertionSort(nums);

console.log("After Using Insertion Sort:", nums);

Complexity Analysis

Time Complexity: O(N²) for the worst and average cases, where N is the size of the array. This is because the outer loop runs N times, and for each pass, the inner loop runs up to N times as well, resulting in approximately N xN operations, hence O(N²). The best-case time complexity occurs when the array is already sorted, in which case the inner loop doesn't run at all, leading to a time complexity of O(N). Space Complexity: O(1) because Insertion Sort is an in-place sorting algorithm, meaning it sorts the array by modifying the original array without using additional data structures that grow with the size of the input.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code