Insertion Sort Implementation in Java

Insertion Sort Implementation in Java

Sorting is a fundamental operation in computer science, and Insertion Sort is a simple yet effective algorithm for arranging elements in ascending order. In this blog post, we will explore the implementation of Insertion Sort in Java, understand its logic, and provide examples for clarity.

Insertion Sort Overview

Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one element at a time. It is much less complex than other sorting algorithms like Quick Sort or Merge Sort, making it easy to understand and implement.

Insertion Sort Implementation in Java

Let’s dive into a straightforward Java implementation of Insertion Sort:

public class InsertionSort {

    // Main method to demonstrate Insertion Sort
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};

        System.out.println("Original Array: " + Arrays.toString(array));

        // Call the sort method to perform Insertion Sort
        sort(array);

        System.out.println("Sorted Array: " + Arrays.toString(array));
    }

    // Insertion Sort algorithm with comments for better understanding
    public static void sort(int[] array) {
        int n = array.length;

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

            // Move 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;
        }
    }
}

Understanding the Logic

sort Method:

• The main entry point for the Insertion Sort algorithm.
• Iterates through the array, considering one element at a time and placing it in the correct position within the sorted section.

Sorting Process:

• For each element, it compares it with the elements in the sorted section.
• If the current element is smaller, it shifts the greater elements to make space for the current element.

Example

Consider an example array: {12, 11, 13, 5, 6}.

Output:

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

Complexity:

Key Points:

• Initial Placement: Begins by assuming the first element is sorted and gradually adds one element at a time.
• Comparison Logic: Compares each element with those in the sorted section, determining its correct position.
• Efficient Shifting: Shifts larger elements to make space for the current element during the sorting process.
• Best-Case Advantage: Achieves O(n) time complexity when the array is already sorted, making it efficient for some scenarios.
• In-Place Operation: Uses constant extra memory (O(1)), making it an in-place sorting algorithm.

Conclusion

Insertion Sort might not be the fastest sorting algorithm, especially for large datasets, but its simplicity and efficiency for small datasets make it a valuable tool in certain scenarios. Understanding its logic and implementation in Java provides a solid foundation for sorting algorithms in general.

Latest Posts:

• Find Longest Subarray with Sum Divisible by K
  Title: Find Longest Subarray with Sum Divisible by K In this guide, you’ll learn how to find the longest subarray… Read more: Find Longest Subarray with Sum Divisible by K
• Find Longest Subarray with Equal Zeros and Ones
  Title: Find Longest Subarray with Equal Zeros and Ones In this guide, you’ll learn how to find the length of… Read more: Find Longest Subarray with Equal Zeros and Ones
• Find All Subarrays with a Given Sum
  Title: Find All Subarrays with a Given Sum Given an array of integers and a target sum, the task is… Read more: Find All Subarrays with a Given Sum
• Find All Subarrays with Zero Sum
  Title: Find All Subarrays with Zero Sum In this guide, you’ll learn how to find every contiguous subarray of an… Read more: Find All Subarrays with Zero Sum
• Find Minimum Sum Subarray
  Title: Find Minimum Sum Subarray In this guide, you’ll learn how to find the minimum sum subarray in an array… Read more: Find Minimum Sum Subarray
• Find Maximum Sum Subarray using Kadane’s Algorithm
  Title: Find Maximum Sum Subarray using Kadane’s Algorithm Finding the contiguous subarray with the largest sum is one of the… Read more: Find Maximum Sum Subarray using Kadane’s Algorithm