Understand Insertion Sort Problem

Problem Name: Insertion Sort
Problem Description:

Problem: Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It is particularly efficient for small or nearly sorted datasets.

How It Works

  1. Initialization
    Assume the first element of the array is already sorted.
  2. Iteration
    Starting from the second element, pick the current element (key) and compare it with the elements in the sorted portion (to its left).
  3. Shifting Elements
    Shift all elements in the sorted section that are greater than the key one position to the right.
  4. Insertion
    Insert the key into its correct position in the sorted section.
  5. Repeat
    Repeat the process for each element until the entire array is sorted.

Pseudocode

for i = 1 to length(array) - 1:
    key = array[i]
    j = i - 1

    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1

    array[j + 1] = key

Time Complexity

  • Best Case: O(n) when the array is already sorted.
  • Average/Worst Case: O(n²) due to the nested loop in the worst scenario.
Category:
  • Searching & Sorting
  • Arrays
Programming Language:
  • Java
Reference Link:

https://drawtocode.vercel.app/problems/insertion-sort

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
INPUT: int [] arr = {4,3,2,1};
OUTPUT: arr = {1,2,3,4}
public static void main(String[] args){
        int[] arr = { 64, 25, 12, 22, 11 };
        System.out.print("Original array: ");
        printArray(arr);
        insertionSort(arr);
        System.out.print("Sorted array: ");
        printArray(arr);
} // Function End
Helper Function:
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
 int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}//Loop End
arr[j + 1] = key;
}//Loop End
}//function end
Utility Functions and Global variables:
    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
}//Loop End
System.out.println();
} // Function End
Privacy Policy | About