Nishant Kumar
Cosmic Techie

Cosmic Techie

Insertion Sort

Nishant Kumar's photo
Nishant Kumar
·Jan 21, 2022·

1 min read

Insertion Sort

Subscribe to my newsletter and never miss my upcoming articles

Insertion Sort is a simple sorting algorithm. It is like picking up an element from the list and inserting it to its rightful index as per intended order of the elements in the list. Initially, the first element is considered to be at its right place and as we go through the elements of the list, the sorting takes place by comparing the elements.

Illustration:

Insertionsort.gif

for all elements in list,step=from step=0 to step=length(list)-1
    first element is sorted,when step=0
    key=list[step],the element to be extracted to insert at the right index
    j=step-1
    while j>=0 and key < value at index j
        list[j+1]=list[j]
        j=j-1
    list[j+1]=key

Time Complexity:

  • Worst Case: O(n2)
  • Average Case: O(n2)
  • Best Case: O(n) Space Complexity: O(1)

    Program for insertion sort:

    def insertionSort(data):
    
      for step in range(0, len(data)):
          key = data[step]
          j = step - 1
    
          while j >= 0 and key < data[j]:   # Change key<data[j] to key>data[j] for descending order.        
              data[j + 1] = data[j]
              j = j - 1
    
          data[j + 1] = key
          print("step",step," -- ",data)
    inp=input("Enter the data: ").split()
    data=[]
    for i in inp:
      data.append(int(i))
    insertionSort(data)
    print('Sorted list in Ascending Order:')
    print(data)
    

Output:

insertionsort.png

 
Share this