Insertion Sort | Insertion sort algorithm | insertion sort time complexity

                                                               Sorting in JAVA

Insertion Sort

Insertion sort is a simple and efficient sorting algorithm used to sort small or partially sorted arrays. It works by comparing each element in the array to the ones before it and inserting it into its correct position. In this blog post, we will discuss how insertion sort works, its advantages, disadvantages, and its implementation in code.

How does insertion sort work?

Insertion sort starts by comparing the second element in the array to the first element. If the second element is smaller than the first, they swap positions. The algorithm then compares the third element to the first two and inserts it into its correct position. The process continues until all the elements in the array are sorted.

Advantages of insertion sort:-

One of the primary advantages of insertion sort is that it is a simple algorithm to implement. It is also very efficient for small arrays and partially sorted arrays. Additionally, it does not require any extra space as it sorts the array in place.

Disadvantages of insertion sort:-

One of the main disadvantages of insertion sort is that it is not efficient for large arrays. It has a time complexity of O(n^2), which means that the time it takes to sort an array grows exponentially with the size of the array. Additionally, it is not suitable for sorting arrays with a large number of duplicates as it takes longer to sort arrays with repeated elements.

Implementing insertion sort in code:-

The implementation of insertion sort in code is relatively simple. Here is a sample implementation in Python:

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

            j -= 1 
arr[j + 1] = key 
return arr

In this implementation, we first loop through the array starting from the second element. We then assign the second element to a variable called key. We then compare the key to the previous elements in the array and move them one position to the right until we find the correct position for the key. We then insert the key into its correct position.

Here's an implementation of insertion sort in Java:

Idea: Take an element from the unsorted array, place it in its corresponding position in the sorted part, and shift the elements accordingly. 

Time Complexity: O(N2) 

Code

import java.util.*;

 

class Sorting {

   public static void printArray(int arr[]) {

       for(int i=0; i<arr.length; i++) {

           System.out.print(arr[i]+" ");

       }

       System.out.println();

   }

 

   public static void main(String args[]) {

       int arr[] = {7, 8, 1, 3, 2};

 

       //insertion sort

       for(int i=1; i<arr.length; i++) {

           int current = arr[i];

           int j = i - 1;

               while(j >= 0 && arr[j] > current) {

                   //Keep swapping

                   arr[j+1] = arr[j];

                   j--;

               }

           arr[j+1] = current;

       }

       printArray(arr);

   }

}

Here's an implementation of insertion sort in C++:

cpp
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
 key = arr[i]; 
 j = i - 1; 
while (j >= 0 && arr[j] > key) { 
 arr[j + 1] = arr[j];
 j = j - 1; 
 }
 arr[j + 1] = key; 
 } 
}

Here's an implementation of insertion sort in C:

c
void insertionSort(int arr[], int n) {
int i, key, j; 
for (i = 1; i < n; i++) {
 key = arr[i];
 j = i - 1; 
while (j >= 0 && arr[j] > key) { 
 arr[j + 1] = arr[j];
     j = j - 1;
 } 
      arr[j + 1] = key;
 } 
}

The C++ and C implementations are virtually identical since the syntax for both languages is quite similar. The only difference between the two is the function signature, which includes the return type in C++ and doesn't include it in C.

Conclusion:-

Insertion sort is a simple and efficient sorting algorithm that is ideal for small and partially sorted arrays. Although it is not suitable for large arrays, its ease of implementation and lack of extra space requirements make it an attractive option for small arrays.

Others related blog:-

• Selection Sort Algorithm | Sorting in JAVA

• Selection Sort Algorithm | Sorting in JAVA

• Bit Manipulation (Lecture 14)| bit manipulation operation

• OBJECT ORIENTED PROGRAMMING SYSTEMS JAVA| oops concepts with real time examples 

• Package in Java| what is the case used for a package in java| creating packages in java 

• Polymorphism in java | polymorphism genetics 

• Inheritance | types of inheritance | inheritance in python

 

        Amazon Link:-      

1. My Laptop

1. Phone

1. Earbud

1. Earphone