Insertion Sort in Java

Insertion sort is an algorithm for sorting elements in an array. It is a comparison-based sorting algorithm in which elements are compared to their previous elements and then inserted into the appropriate position within the array. In this article, we will discuss the insertion sort algorithm in detail and explore its time and space complexities. We will also go through Java code examples that show how insertion sort works in practice.

How Insertion Sort Works

Insertion sort works by looping through an array and comparing each element to the element before it. If the element before it is larger, the algorithm swaps the two elements. This process continues until the element is in the correct position within the array.

The algorithm can be broken down into the following steps:

1. Start with an unsorted array of elements.
2. Set a marker for the current index of the array.
3. Compare the element at the current index to the element before it.
4. If the element before it is larger, swap the two elements.
5. Move the marker to the next element in the array.
6. Repeat steps 3-5 until the marker reaches the end of the array.

Insertion Sort Time Complexity

The time complexity of insertion sort is O(n^2) in the worst case, and O(n) in the best case. This means that the algorithm takes a quadratic amount of time in the worst case and a linear amount of time in the best case.

The time complexity for access, search, insertion, and deletion are all O(n), meaning it takes a linear amount of time to access, search, insert, and delete an element from the array.

Insertion Sort Space Complexity

The space complexity of insertion sort is O(1), meaning that it takes a constant amount of space to sort an array of elements. This is because the algorithm does not require any additional memory to store data.

Java Code for Insertion Sort

Now that we have discussed how insertion sort works and its time and space complexities, let’s see how it works in practice. We will go through a Java code example that implements the insertion sort algorithm.

First, we will define a method called insertionSort() that takes an array of integers as a parameter and returns a sorted array. This method will contain the implementation of the insertion sort algorithm.

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

In the code above, we loop through the array and compare each element to the element before it. If the element before it is larger, we swap the two elements. We then move the marker to the next element in the array and repeat the process.

Conclusion

In this article, we discussed the insertion sort algorithm in detail. We explored how insertion sort works and its time and space complexities. We also went through a Java code example that implements the algorithm. Insertion sort is an efficient sorting algorithm that is easy to implement.

Exercises

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

public static String[] insertionSort(String[] array) {
    for (int i = 1; i < array.length; i++) {
        String currentElement = array[i];
        int j = i - 1;
        while (j >= 0 && array[j].compareTo(currentElement) > 0) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = currentElement;
    }
    return array;
}

public static char[] insertionSort(char[] array) {
    for (int i = 1; i < array.length; i++) {
        char currentElement = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > currentElement) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = currentElement;
    }
    return array;
}

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

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