Insertion sort is a sorting algorithm which picks a number and place it in a way such that it maintains a sequence. We all have played solitaire in our PCs best way to learn insertion sort is through playing that game. The sequence for the cards is king, queen, jack, 10, 9, 8, 7, 6, 5, 4, 3, 2, ace. So, we pick the cards and place it in a sequence that is how insertion sort works.
ALGORITHM
PSUEDOCODE:
PYTHON CODE:
Let’s take an example of array 10, 9, 7, 6, 8
10, 9, 7, 6, 8
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 9 is smaller than 10, move 10 and insert 9 before 10
9, 10, 7, 6, 8
i = 2. 7 is smaller than 10 and 7 is smaller than 9 therefore move 7 and insert it before 9.
7, 9, 10, 6, 8
i = 3. 6 will move to the beginning and all other elements from 7 to 10 will move one position ahead of their current position.
6, 7, 9, 10, 8
i = 4. 8 will move to position after 7, and elements 9 and 10 will move one position ahead of their current position.
6, 7, 8, 9, 10
Output:
The letter ‘n’ often represents the size of the input to the function. n represents the number of elements in a list. In different scenarios, practitioners care about the worst-case, best-case, or average complexity of a function.
In Time Complexity, time taken to sort a list is directly proportional to number of elements in the list. O(n) is the case when the list is already sorted and have only one iteration in the case as the loop is trivial and elements are already sorted which can be known as best case scenario. O(n2) is the worst case scenario in which the list is not sorted, the time taken to sort a list is proportional to the square of the number of elements in the list.
Space Complexity: O(1)
The use of insertion sort is very limited as it only works for the small list. It is not efficient in handling the large number of list. Insertion sort is preferred when working with the linked list
- Insertion sort works the same way as playing cards.
- You extract the card and repeat the process till all the cards are sorted
