Java Program to sort an array using Insertion Sort

Program

import java.util.Scanner;
class InsertionSort {
    public static void main(String[] args) {
        InsertionSort sort = new InsertionSort();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array:\t");
        int count = sc.nextInt();
        int[] arr = new int[count];
        System.out.println("Enter elements");
        for (int i = 0; i < arr.length; i++)
            arr[i] = sc.nextInt();
        sort.insertionSort(arr);
    }
    void insertionSort(int arr[]) {
        int i, j, temp;
        for (i = 0; i < arr.length; i++) {
            temp = arr[i];
            j = i - 1;
            while ((j >= 0) && (arr[j] > temp)) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = temp;
        }
        System.out.println("Sorted Elements:");
        for (i = 0; i < arr.length; i++)
            System.out.print(arr[i] + "\t");
        System.out.println();
    }
}

This Java program demonstrates how to sort an array using the Insertion Sort algorithm.

1. Input from User:

   • The program prompts the user to input the size of the array (count) and the elements of the array.
   • A Scanner object (sc) takes user input.

2. Insertion Sort Method:

   • The method insertionSort() implements the Insertion Sort algorithm:
     • It iterates through the array, starting from the second element.
     • For each element, it compares it with the elements before it and shifts larger elements one position to the right to create space for the current element (temp).
     • The current element is then inserted into its correct position in the sorted portion of the array.

3. Key Variables:

   • temp: Stores the current element being inserted.
   • j: Tracks the position in the sorted portion of the array where the current element (temp) is compared and shifted.

4. Sorting Logic:

   • The outer loop iterates through the array, picking one element (temp) at a time.
   • The inner while loop shifts larger elements to the right until the correct position for temp is found.
   • Once the correct position is identified, temp is inserted.

5. Output:

   • After sorting, the program prints the sorted array elements.

### Key Points:
- **Time Complexity**: 
  - Best case (already sorted): \(O(n)\)
  - Worst case (reverse sorted): \(O(n^2)\)
- **Space Complexity**: \(O(1)\) (in-place sorting).
- This method works well for small or nearly sorted arrays.

**Output**
```shell
Enter the size of the array:
6
Enter elements
32
68
78
12
-3
98
Sorted Elements:
-3      12      32      68      78      98