Insertion Sort

Insertion Sort :

In Insertion sort technique, as the name suggests, insert each element to its proper location. It is simple to implement and efficent on small data set. It is stable, in-place(only requires const amount of extra memory space O(1)) and an online algorithm(i.e. it can sort a list as it recieves).

Worst case:О(n2)

Average Case:О(n2)

Best case:Ω(n)

ALGORITHM:

    • Input Array as a[]
    • for i = 1 to n – 1
      j = i
      while j > 0 and a[j-1] > a[j]
      swap a[j] and a[j-1]
      j = j – 1
      end while
      end for loop
    • PRINT sorted array as a[]

e.g. sort 6,4 2,5


C SOURCE CODE:

Leave a Reply

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