Insertion Sorting
One element at a time, the straightforward sorting technique known as "insertion sort" creates a sorted array. In order for it to function, items from an unsorted list must be moved to the appropriate location within a sorted section of the list.
Sorting playing cards in hands is comparable to how an insertion sort operates. We choose an unsorted card after assuming that the initial card in the card game has already been sorted. The chosen unsorted card will be positioned on the right if it is larger than the first card, and on the left otherwise. In a similar manner, every unsorted card is removed and placed precisely where it belongs.
Working of the Insertion Sorting Algorithm
Step 1. Assuming the first element has previously been sorted, begin with the second.
Step 2. Examine this element with relation to the elements in the array's sorted section.
Step 3. To create room for the new element, move larger elements one spot to the right.
Step 4. Place the component in the appropriate location.
Step 5. For every element, repeat.
Example of Insertion Sorting Algorithm
Look at the array [6, 2, 9, 1, 6, 7].
- Begin with 2: Insert 2 after shifting 6 to the right and comparing with 5. [2, 6, 9, 1, 6, 7] is the outcome.
- Next, 9: In position already. [2, 6, 9, 1, 6, 7 is the outcome.
- Next, 1: Insert 1 after shifting 9, 6, and 2 to the right. [1, 2, 6, 9, 6, 7] is the outcome.
- Next, 5: Place following the initial 6. [1, 2, 6, 6, 9, 7] is the outcome.
- Lastly, 6: Insert 7 after shifting 9 to the right. Outcome: [1, 2, 6, 7, 9]
Complexity of the Insertion Sorting Algorithm
Time Complexity:
Best case
O(n), where n is the number of elements in the list, if the list has previously been sorted.
Average case
If the list is arranged randomly, the average case is O(n 2).
Worst case
If the list is in reverse order, the worst-case scenario is O(n 2).
Space Complexity
O(1) is the space complexity.
Advantages of the Insertion Sorting Algorithm
- Straightforward and simple to put into practice.
- Stable algorithm for sorting.
- Effective for lists that are small and almost sorted.
- Because it is an in-place method, it uses less space.
- The amount of swaps is directly correlated with the number of inversions. For instance, it just takes O(n) time and no swapping occurs for a sorted array.
Disadvantages of the Insertion Sorting Algorithm
- Insertion sort is ineffective for large datasets due to its worst-case and average-case time complexity of O(n 2).
- Insertion sort is frequently slower for longer lists than more sophisticated algorithms with better average and worst-case time complexities, such as quicksort, merge sort, or heapsort.
- Although insertion sort is present and requires no extra memory, it might not fully utilize multi-core computers because it is not parallelizable.
