What is Insertion Sort Algorithm ? Explained with Example

Insertion Sort

• Insertion sort is a simple algorithm for sorting an array
• Start with the first element of the array – one element by itself is already sorted
• Consider the next element of the array – if smaller than the first, swap them
• Consider the third element – Swap it leftward, until it is in proper order with the first two
  elements
• Continue in this manner with the fourth, fifth, etc. until the whole array is sorted

				
					# Python program for implementation of Insertion Sort 
  
# Function to do insertion sort 
def insertionSort(arr): 
  
    # Traverse through 1 to len(arr) 
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
        j = i-1
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key 
  
  
# Driver code to test above 
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
print ("Sorted array is:") 
for i in range(len(arr)): 
    print ("%d" %arr[i])
				
			

Insertion Sort – Complexity

• Worst case complexity?

        – Array in reverse order

        – Outer loop executes ! − 1 times
        – Inner loop executes 1 + 2 + … ! – 1 = ?

• Best case complexity?

      – Array is sorted or almost sorted
      – Outer loop executes ! −  1 times
      – Inner loop executes few times, or doesn’t execute

Thats It for the Topic! Thanks You Guys For Visiting And Make Sure To Comment!

Source:   https://dsacl3-2019.github.io/slides/dsa3_2019_3_sorts_insert_quick.pdf

Do Visit : An Overview of Java: The Three Object-Oriented Programming Principle – Code-Tech Community (codetech.tech)

Happy Coding Mates 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Shopping Cart