Thursday, 27 April 2017

Implementation of Insertion Sort in Python

Insertion sort, This algorithm repeatedly adds new element to the sorted result. In this algorithm we take first element as the sorted sub-array. Then we take second element and puts it into the first sorted sub-array at its correct position (i.e we do shifting if necessary). Then we take third element and put it into first sorted sub-array and repeat the same till all the elements are inserted into the sorted sub-array. Personally saying, I like this algorithm more than quicksort especially if less number of elements are in unsorted manner or if I have to insert an additional element during sorting the process because this algorithm can simply put that new element at its correct position rather than sorting the whole array again. This algorithm take maximum time when all the elements of array are in reverse order.

Time Complexity: O(n^2)

Algorithm:


Algorithm:
 
step 1:    do for i=1 to n
step 2:         set:  key=arr[i]
step 3:         set:  j=i-1
step 4:         doWhile arr[j]>key and j>=0:
step 5:                  set:  arr[j+1]=arr[j]
step 6:                  set:  j=j-1
step 7:         EndWhile
step 8:         set:  arr[j+1]=key


Example:

Let      a[] = { 24, 12, 4, 9, 6 }

Pass 1, i=1:  { 12, 24, 4, 9, 6}
Pass 2, i=2:  { 4, 12, 24, 9, 6}
Pass 3, i=3:  { 4, 9, 12, 24, 6}
Pass 4, i=4:  { 4, 6, 9, 12, 24}


PROGRAM:

def insertion_sort(listing):
 for i in range(1,len(listing)):
  key=listing[i]
  j=i-1
  while j>=0 and listing[j]>key:
   listing[j+1]=listing[j]
   j=j-1
  listing[j+1]=key
 return listing
print("Enter the elements of the list:\n\n")
listing=list(map(int, raw_input().split()))
listing=insertion_sort(listing)
print("\nThe list after sorting is:\n\n")
for i in range(0,len(listing)):
 print listing[i],


OUTPUT:

 


EmoticonEmoticon