DSA Insertion Sort

Welcome to TheCodingCollege.com, where coding and programming concepts come to life! In this article, we explore Insertion Sort, one of the fundamental sorting algorithms in Data Structures and Algorithms (DSA).

What is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm that builds the sorted array one element at a time by picking an element from the unsorted portion and inserting it into the correct position in the sorted portion.

This algorithm mimics the way you might sort playing cards in your hand: by picking cards one by one and arranging them in the correct order.

How Does Insertion Sort Work?

The array is conceptually divided into two parts:

1. Sorted portion: Starts with one element.
2. Unsorted portion: Remaining elements of the array.

The algorithm iteratively picks an element from the unsorted portion and places it in its correct position within the sorted portion.

Steps in Insertion Sort

1. Start from the second element (index 1) since the first element is already “sorted.”
2. Compare the current element with the elements in the sorted portion.
3. Shift all elements in the sorted portion greater than the current element one position to the right.
4. Insert the current element into its correct position.
5. Repeat until all elements are sorted.

Example of Insertion Sort

Let’s sort the array [12, 11, 13, 5, 6].

Initial Array: [12, 11, 13, 5, 6]

Pass 1:

• Current element: 11
• Compare 11 with 12 (shift 12 right).
• Insert 11 before 12.
• Array: [11, 12, 13, 5, 6].

Pass 2:

• Current element: 13
• Compare 13 with 12 (no shifts needed).
• Array remains [11, 12, 13, 5, 6].

Pass 3:

• Current element: 5
• Compare 5 with 13, 12, and 11 (shift all three right).
• Insert 5 at the beginning.
• Array: [5, 11, 12, 13, 6].

Pass 4:

• Current element: 6
• Compare 6 with 13, 12, and 11 (shift all three right).
• Insert 6 after 5.
• Array: [5, 6, 11, 12, 13].

Sorted Array: [5, 6, 11, 12, 13].

Insertion Sort Code Implementation

Python Code:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage
array = [12, 11, 13, 5, 6]
insertion_sort(array)
print("Sorted Array:", array)

Output:

Sorted Array: [5, 6, 11, 12, 13]

Java Code:

class InsertionSort {
    static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Shift elements of the sorted portion that are greater than key
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.print("Sorted Array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Time Complexity of Insertion Sort

Space Complexity: O(1)O(1) (In-place sorting).

Advantages and Disadvantages of Insertion Sort

Advantages

1. Efficient for small datasets.
2. Stable sorting algorithm (preserves the order of duplicate elements).
3. In-place sorting with no extra memory usage.

Disadvantages

1. Inefficient for large datasets due to O(n2)O(n^2) time complexity.
2. Requires more comparisons and shifts than necessary for already sorted arrays.

Applications of Insertion Sort

1. Small Datasets: Works well for small or nearly sorted datasets.
2. Real-Time Sorting: Ideal for scenarios where new data is continuously added, and the array needs to stay sorted.

Comparison with Other Sorting Algorithms

Conclusion

Insertion Sort is a simple and intuitive algorithm for sorting small or partially sorted datasets. While not efficient for large arrays, it serves as a foundation for understanding more complex sorting techniques.

Explore more sorting algorithms and coding tutorials on TheCodingCollege.com and start mastering DSA today!