Insertion Sort Algorithm with C++ Code | Sorting Algorithms | Data Structures & Algorithms

In this tutorial we understand the working of insertion sort algorithm in data structures.

Insertion Sort –
  • Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
  • Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
  • Time Complexity: O(n*2)
  • Efficient for (quite) small data sets, much like other quadratic sorting algorithms
  • More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
Working –
    null
  • Step 1 – Pick next element
  • Step 2 – Compare with all elements in the sorted sub-list on the left
  • Step 3 – Shift all the elements in the sorted sub-list that is greater than the
  • value to be sorted
  • Step 4 – Insert the value
  • Step 5 – Repeat until list is sorted
Insertion Sort Algorithm –
  1. declare variables – i, key, j
  2. loop : i = 1 to n – 1 // outer loop
    1. key = a[i] //pick the next element
    2. j = i – j; // decrement j value
    3. loop : (j>=0 && a[j]>key) // inner loop
      1. arr[j+1] = arr[j]
      2. j = j – 1
    4. end loop // outer loop
    5. arr[j+1] = key
  3. end loop // outer loop
C++ Program to Implement Selection Sort –

YouTube video tutorials –

Leave a Reply

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