Data Structures (insertion sort in data structures)
Insertion Sort 👉 Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards. 👉 In this algorithm, we insert each element onto its proper place in the sorted array. 👉 This is less efficient than the other sort algorithms like quick sort, merge sort, etc. Technique: 👉 Consider an array A whose elements are to be sorted. Initially, A[0] is the only element on the sorted set. 👉 In pass 1, A[1] is placed at its proper index in the array. 👉 In pass 2, A[2] is placed at its proper index in the array. Likewise, in pass n-1, A[n-1] is placed at its proper index into the array. 👉 To insert an element A[k] to its proper index, we must compare it with all other elements i.e. A[k-1], A[k-2], and so on until we find an element A[j] such that, A[j]<=A[k]. 👉 All the elements from A[k-1] to A[j] need to be shifted and A[k] will ...