Insertion Sort Algorithm
Overview : Insertion Sort Algorithm
- Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).
What is Insertion sort
- In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted portion until all the elements are sorted in the list.
- Insertion Sort Algorithm sorts array by shifting elements one by one and inserting the right element.
- It is better than Selection Sort and Bubble Sort algorithms
Steps to Insertion Sort Algorithm
Step 1: Assume that first element in the list is in sorted portion of the list and remaining all elements are in unsorted portion.
Step 2: Consider first element from the unsorted list and insert that element into the sorted list in order specified.
Step 3: Repeat the above process until all the elements from the unsorted list are moved into the sorted list.
Complexity of the Insertion Sort Algorithm
To sort a unsorted list with ‘n’ number of elements we need to make (1+2+3+……+n-1) = (n (n-1))/2 number of comparisons in the worst case. If the list already sorted, then it requires ‘n’ number of comparisons.
Worst Case : O(n2)
Best Case : Ω(n)
Average Case : Θ(n2)
