DSA-lab5(b)-Insertion_Sort

import java.util.Scanner;

/**
 * InsertionSort Program
 * ---------------------
 * This program sorts an array using Insertion Sort algorithm.
 * 
 * Time Complexity:
 * - Best Case: O(n)
 * - Worst Case: O(n^2)
 */
public class InsertionSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Taking input from user
        System.out.print("Enter number of elements: ");
        int n = sc.nextInt();

        int[] arr = new int[n];

        System.out.println("Enter elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // storing input values
        }

        // Calling insertion sort function
        insertionSort(arr);

        // Displaying sorted array
        System.out.println("Sorted array (Insertion Sort):");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        sc.close(); // closing scanner
    }

    /**
     * Insertion Sort Algorithm
     * Builds sorted array one element at a time
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Traverse from second element to end
        for (int i = 1; i < n; i++) {

            int key = arr[i]; // element to be inserted
            int j = i - 1;

            // Shift elements greater than key to right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Place key at correct position
            arr[j + 1] = key;
        }
    }
}