Program of Insertion Sort Java

Java

// Java program for implementation of Insertion Sort 
class InsertionSort { 
    // Function to sort array using insertion sort 
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; ++i) { 
            int key = arr[i]; 
            int j = i - 1; 
  
            // Move elements of arr[0..i-1], that are 
            // greater than key, to one position ahead 
            // of their current position 
            while (j >= 0 && arr[j] > key) { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = key; 
        } 
    } 
  
    // A utility function to print array of size n 
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n; ++i) 
            System.out.print(arr[i] + " "); 
  
        System.out.println(); 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        int arr[] = { 12, 11, 13, 5, 6 }; 
  
        InsertionSort ob = new InsertionSort(); 
        ob.sort(arr); 
  
        printArray(arr); 
    } 
}

Output

5 6 11 12 13

The complexity of the above method

Time Complexity: O(N^2)
Auxiliary Space: O(1)

Java Program for Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. In this article, we will write the program on Insertion Sort in Java.

Program of Insertion Sort Java

Java

The complexity of the above method

Java Program for Insertion Sort

Similar Reads

Contact Us