Insertion Sort Algorithm in Java

1. Introduction

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It works by building a sorted section of the array one element at a time. For each position, it checks the value there against the largest value in the sorted section of the array; if larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted section and moves the value to that location. It then shifts all the larger values up to make space.

2. Implementation Steps

1. Start from the second element (consider the first element as sorted).

2. Compare the current element with the previous elements.

3. If the current element is smaller than the previous element, keep comparing with the elements before until you reach an element smaller, or reach the start of the array.

4. Insert the current element in the correct position so that the elements before are smaller than the current element.

5. Repeat the process for each of the elements in the array.

3. Implementation in Java

public class InsertionSort {
    // Insertion Sort 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;
            // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
    // Function to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(arr);
        insertionSort(arr);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output:

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

Explanation:

1. The insertionSort function sorts an array using the Insertion Sort algorithm.

2. The outer loop iterates through the elements starting from the second element, treating each element as a key.

3. The inner loop moves elements of the already sorted section that are greater than the key to one position ahead of their current position.

4. After shifting the greater elements, the current key is placed in its correct position.

5. This process is repeated for each of the elements in the array, gradually building up the sorted section of the array.

6. printArray is a utility function to print the elements of an array.

7. The main function demonstrates the Insertion Sort algorithm on a sample array.