Understanding Insertion Sort Algorithm (with Examples in Java)

Insertion sort is an iterative sorting algorithm. It builds a sorted subarray one element at a time by inserting each unsorted element into its correct position within the sorted subarray. Think of sorting a hand of playing cards – you start with one sorted card, then insert each subsequent card into its proper place among the already sorted cards.

How Insertion Sort Works

Let's illustrate with an example array we want to sort in ascending order:

First Iteration:

We consider the first element already sorted. The algorithm begins with the second element.

Comparing 2 with 8, since 2 < 8, we shift 8 to the right and insert 2 to its left.

Second Iteration:

We compare 6 with the sorted subarray (2, 8). 6 < 8, so 8 shifts right. Then, since 6 > 2, 6 is placed to the right of 2.

This process continues until the entire array is sorted.

Implementation in Java

<code class="language-java">import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(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;
        }
    }
}</code>

The code iterates, taking each element as a key. It then compares the key with elements in the sorted portion, shifting larger elements to the right until the correct position for the key is found.

For example, in the second iteration (i=2):

The key is 6. The while loop shifts elements until the correct position is found:

Finally, 6 is inserted:

Output:

Unsorted array: [8, 2, 6, 4, 9, 1] Sorted array: [1, 2, 4, 6, 8, 9]

Complexity Analysis

• Time Complexity:
  • Best Case (O(n)): Already sorted array.
  • Average Case (O(n²)): Randomly arranged elements.
  • Worst Case (O(n²)): Reverse-sorted array.
• Space Complexity: O(1) (In-place algorithm)

Conclusion

Insertion sort's quadratic time complexity makes it inefficient for large datasets. However, it's a simple algorithm and performs well on small datasets or nearly sorted data.

The above is the detailed content of Understanding Insertion Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!