Insertion Sort In Java

Insertion sort is a simple sorting algorithm that works by repeatedly inserting elements from an unsorted portion of the list into their correct positions within a sorted portion of the list. It is an in-place algorithm, meaning it doesn't require additional memory space to perform the sorting.

Here's a step-by-step explanation of how the insertion sort algorithm works:

1. Start with an unsorted list of elements.

2. Divide the list into two portions: a sorted portion on the left and an unsorted portion on the right. Initially, the sorted portion contains only the first element of the list.

3. Take the first element from the unsorted portion and insert it into the correct position within the sorted portion.

4. Compare the element with the elements in the sorted portion, moving from right to left, until you find the correct position to insert it. Shift the elements in the sorted portion to the right to make space for the insertion.

5. Repeat steps 3 and 4 for the remaining elements in the unsorted portion, each time inserting an element into its correct position within the sorted portion.

6. Continue this process until the entire list is sorted, i.e., the unsorted portion becomes empty.

Here's an example to illustrate the insertion sort algorithm:

Let's say we have an unsorted list: [5, 3, 8, 2, 1]

1. Initial state:

   • Sorted portion: [5]

   • Unsorted portion: [3, 8, 2, 1]

2. Inserting 3:

   • Compare 3 with 5. Since 3 is smaller, shift 5 to the right.

   • Insert 3 in the correct position within the sorted portion.

   • Updated sorted portion: [3, 5]

   • Updated unsorted portion: [8, 2, 1]

3. Inserting 8:

   • Compare 8 with 5. Since 8 is greater, no shifting is needed.

   • 8 is already in its correct position within the sorted portion.

   • Updated sorted portion: [3, 5, 8]

   • Updated unsorted portion: [2, 1]

4. Inserting 2:

   • Compare 2 with 8. Since 2 is smaller, shift 8 to the right.

   • Compare 2 with 5. Since 2 is smaller, shift 5 to the right.

   • Compare 2 with 3. Since 2 is smaller, shift 3 to the right.

   • Insert 2 in the correct position within the sorted portion.

   • Updated sorted portion: [2, 3, 5, 8]

   • Updated unsorted portion: [1]

5. Inserting 1:

   • Compare 1 with 8. Since 1 is smaller, shift 8 to the right.

   • Compare 1 with 5. Since 1 is smaller, shift 5 to the right.

   • Compare 1 with 3. Since 1 is smaller, shift 3 to the right.

   • Compare 1 with 2. Since 1 is smaller, shift 2 to the right.

   • Insert 1 in the correct position within the sorted portion.

   • Updated sorted portion: [1, 2, 3, 5, 8]

   • Updated unsorted portion: []

The final sorted list is [1, 2, 3, 5, 8].

Insertion sort has a time complexity of O(n^2) in the worst case, but it performs efficiently for small lists or partially sorted lists. It also has the advantage of sorting the list in place without requiring additional

import java.util.Arrays;
public class Sort {
    public static void main(String[] args) {
        int arr[] = {4,3,5,2,5,3,2,5,5,4,2,2,4,5,1,7,9,7,5,1};
        insertionSort(arr);
        printArray(arr);
    }
    public static int[] insertionSort(int[] arr) {
        System.out.println("Sort.insertionSort() : n^2");
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int sortedIndex = i-1;

            while(sortedIndex >= 0 && current < arr[sortedIndex]){
                arr[sortedIndex+1]=arr[sortedIndex];
                sortedIndex--;
            }
            arr[sortedIndex+1]=current;
        }
        return arr;
    }
    public static void printArray(int[] outputArr) {
        System.out.println(Arrays.toString(outputArr));        
    }
}

OUTPUT:

Sort.insertionSort() : n^2

[1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 7, 7, 9]