Java program for Insertion Sort

In the following examples of Java program for Insertion Sort :

Program :

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 3};
        System.out.println("Before sorting:");
        printArray(arr);
        insertionSort(arr);
        System.out.println("After sorting:");
        printArray(arr);
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Output :

Before sorting:5 2 8 1 3 
After sorting:
1 2 3 5 8

In this program, we first declare an integer array arr and initialize it with the values 5, 2, 8, 1, and 3. We then print the array before sorting using the printArray method.

We then call the insertionSort method and pass the array as an argument. This method performs an insertion sort on the array.

The insertion sort algorithm works by iterating through the array from left to right, and at each iteration, inserting the current element into the correct position in the sorted portion of the array to its left.

We start by assuming that the first element is already sorted, and iterate from the second element to the end of the array. For each element, we compare it with the elements to its left until we find an element that is smaller than it. We then shift all the larger elements to the right by one position and insert the current element into the vacated position.

Finally, we print the array after sorting using the printArray method.