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 –
#include < iostream >
  using namespace std;

void insertionSort(int arr[]) {
  int key;
  int j = 0;
  for (int i = 1; i < 5; i++) {
    key = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }

}

int main() {
  int myarray[5];
  cout << "Enter 5 integers in any order" << endl;
  for (int i = 0; i < 5; i++) {
    cin >> myarray[i];
  }

  cout << "Before Sorting: " << endl;
  for (int i = 0; i < 5; i++) {
    cout << myarray[i] << " ";
  }

  insertionSort(myarray);

  cout << endl << "After Sorting: " << endl;
  for (int i = 0; i < 5; i++) {
    cout << myarray[i] << " ";
  }

  return 0;
}

YouTube video tutorials –

Leave a Reply

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