Java Array Direct Insertion Sort

In this tutorial, we will demonstrate how to implement the Direct Insertion Sort algorithm in Java using arrays. Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is more efficient than Bubble Sort but less efficient than more advanced algorithms like QuickSort or MergeSort.

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 4, 2};

        insertionSort(arr);

        // Print the sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void insertionSort(int[] array) {
        int n = array.length;

        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;

            // Shift elements of array[0..i-1], that are greater than key, to one position ahead of their current position
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }
}

When you run this code, it will print the sorted array:

1 2 3 4 5

In this example, we defined an insertionSort method that takes an array as input and sorts it using the Direct Insertion Sort algorithm. The outer loop iterates through the array starting from the second element. The inner loop iterates in reverse from the current outer loop index to the beginning of the array, shifting elements to the right if they are greater than the key element (the current element in the outer loop).

Insertion Sort has a worst-case and average-case time complexity of O(n^2), where n is the number of items being sorted. It performs well for small datasets or when the input data is partially sorted. However, for larger datasets, more efficient sorting algorithms like QuickSort or MergeSort should be used.

How to Implement Direct Insertion Sort on Arrays in Java: Here's an implementation of direct insertion sort on arrays in Java:

public class DirectInsertionSort {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        directInsertionSort(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }

    public static void directInsertionSort(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;
        }
    }
}

Java Direct Insertion Sort for Strings: Direct insertion sort can be applied to arrays of strings by comparing string elements.

public static void directInsertionSortStrings(String[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        String 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].compareTo(key) > 0) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Direct Insertion Sort with Java ArrayList: Direct insertion sort can be applied to ArrayList using the add and remove methods.

public static void directInsertionSortArrayList(ArrayList<Integer> list) {
    int n = list.size();
    for (int i = 1; i < n; i++) {
        int key = list.get(i);
        int j = i - 1;

        // Move elements of list[0..i-1] that are greater than key to one position ahead of their current position
        while (j >= 0 && list.get(j) > key) {
            list.add(j + 1, list.get(j));
            list.remove(j);
            j = j - 1;
        }
        list.add(j + 1, key);
        list.remove(i + 1);
    }
}

Java Direct Insertion Sort Descending Order: To sort in descending order, adjust the comparison condition.

while (j >= 0 && arr[j] < key) {
    // Move elements in descending order
    arr[j + 1] = arr[j];
    j = j - 1;
}

Direct Insertion Sort Visualization in Java: Visualization can be done by printing the array at each step.

public static void visualizeDirectInsertionSort(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 = j - 1;
        }
        arr[j + 1] = key;

        // Print the array for visualization
        printArray(arr);
    }
}

public static void printArray(int[] arr) {
    for (int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

Java Direct Insertion Sort Recursive Implementation: Direct insertion sort is typically implemented iteratively. Recursive implementation is less common due to its inefficiency.

public static void recursiveDirectInsertionSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }
    recursiveDirectInsertionSort(arr, n - 1);
    int key = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}