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 –
- declare variables – i, key, j
- loop : i = 1 to n – 1 // outer loop
- key = a[i] //pick the next element
- j = i – j; // decrement j value
- loop : (j>=0 && a[j]>key) // inner loop
- arr[j+1] = arr[j]
- j = j – 1
- end loop // outer loop
- arr[j+1] = key
- 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 –