Insertion Sort in Java: A Simple and Efficient Algorithm

Introduction

In this blog, we will learn how insertion sort works. Insertion sort is a straightforward sorting algorithm that builds the final sorted array one element at a time. It's efficient for small data sets and is often used as part of more complex sorting algorithms.

Working of Insertion Sort

using System;

class Program
{
    static void Main(string[] args)
    {
        // Prompt the user to enter a number
        Console.WriteLine("Enter the first number:");
        string input1 = Console.ReadLine();
        double number1;

        // Try to parse the input to a double
        if (double.TryParse(input1, out number1))
        {
            // Prompt the user to enter another number
            Console.WriteLine("Enter the second number:");
            string input2 = Console.ReadLine();
            double number2;

            // Try to parse the input to a double
            if (double.TryParse(input2, out number2))
            {
                // Perform a simple addition
                double result = number1 + number2;

                // Display the result
                Console.WriteLine($"The sum of {number1} and {number2} is {result}.");
            }
            else
            {
                Console.WriteLine("Invalid input for the second number.");
            }
        }
        else
        {
            Console.WriteLine("Invalid input for the first number.");
        }
    }
}

1. Start with the second element of the array.
2. Compare it with the previous elements.
3. If it's smaller, shift the larger elements right.
4. Insert the element in its correct position.
5. Repeat for all elements.

   import java.util.Arrays;
   public class InsertionSortExample {
       public static void insertionSort(int[] arr) {
           int n = arr.length;
           for (int i = 1; i < n; 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;
           }
       }
       public static void main(String[] args) {
           int[] arr = {64, 34, 25, 12, 22, 11, 90};
           insertionSort(arr);
           System.out.println(Arrays.toString(arr));
       }
   }

   Java

   Copy

Flow Diagram of the above example

Time Complexity

• Best Case: O(n) when the array is already sorted.
• Average and Worst Case: O(n^2).

Space Complexity

O(1) as it sorts in place.

Advantages

• Simple implementation
• Efficient for small data sets
• Adaptive (efficient for partially sorted arrays).

Disadvantages

Inefficient for large data sets.

Summary

Insertion sort shines in scenarios where the data is nearly sorted or when sorting small arrays. Its simplicity makes it a good choice for educational purposes and as a building block for more complex algorithms.