Insertion Sort Implementation in Java

By
Shivam Gupta
-
9
Insertion Sort Implementation in Java
Advertisement

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:

Java Program – 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}.

  1. Start with the second element (11) and insert it in the correct position in the sorted section: {11, 12, 13, 5, 6}.
  2. Consider the third element (13) and insert it: {11, 12, 13, 5, 6}.
  3. Consider the fourth element (5) and insert it: {5, 11, 12, 13, 6}.
  4. Consider the fifth element (6) and insert it: {5, 6, 11, 12, 13}.

Output:

Output – Insertion Sort
Original Array: [12, 11, 13, 5, 6]
Sorted Array: [5, 6, 11, 12, 13]

Complexity:

ComplexityWorst CaseAverage CaseBest Case
Time ComplexityO(n^2)O(n^2)O(n)
Space ComplexityO(1)O(1)O(1)

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:

RELATED ARTICLESMORE FROM AUTHOR