INSERTION SORT
Insertion sort works similar
to the sorting of playing cards in hands. It is assumed that the first card is
already sorted in the card game, and then we select an unsorted card. If the
selected unsorted card is greater than the first card, it will be placed at the
right side; otherwise, it will be placed at the left side. Similarly, all
unsorted cards are taken and put in their exact place.
This is an in-place
comparison-based sorting algorithm. Here, a sub-list is maintained which is
always sorted. For example, the lower part of an array is maintained to be
sorted. An element which is to be inserted in this sorted sub-list, has to find
its appropriate place and then it has to be inserted there. Hence the name, insertion sort.
The array is searched sequentially
and unsorted items are moved and inserted into the sorted sub-list (in the same
array). This algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2),
where n is the number of items.
Insertion sort has
various advantages such as –
o Simple
implementation
o Efficient
for small data sets
o Adaptive,
i.e., it is appropriate for data sets that are already substantially sorted.
Now, let's see the
algorithm of insertion sort.
ALGORITHM
The simple steps of
achieving the insertion sort are listed as follows -
Step 1
− If it is the first element, it is already sorted. return 1;
Step 2
− Pick next element
Step 3
− Compare with all elements in the sorted sub-list
Step 4
− Shift all the elements in the sorted sub-list that is greater than the value
to be sorted
Step 5
− Insert the value
Step 6
− Repeat until list is sorted
WORKING OF INSERTION SORT ALGORITHM
Now, let's see the
working of the insertion sort Algorithm.
To understand the working of the insertion sort algorithm, let's take an unsorted array. It will be easier to understand the insertion sort via an example.
INSERTION SORT
COMPLEXITY
Now, let's see the time
complexity of insertion sort in best case, average case, and in worst case. We
will also see the space complexity of insertion sort.
1.
Time Complexity
|
Case |
Time
Complexity |
|
Best Case |
O(n) |
|
Average Case |
O(n2) |
|
Worst Case |
O(n2) |
o Best
Case Complexity - It occurs when there is no sorting
required, i.e. the array is already sorted. The best-case time complexity of
insertion sort is O(n).
o Average
Case Complexity - It occurs when the array elements
are in jumbled order that is not properly ascending and not properly
descending. The average case time complexity of insertion sort is O(n2).
o Worst
Case Complexity - It occurs when the array elements
are required to be sorted in reverse order. That means suppose you have to sort
the array elements in ascending order, but its elements are in descending
order. The worst-case time complexity of insertion sort is O(n2).
2.
Space Complexity
|
Space
Complexity |
O(1) |
|
Stable |
YES |
o The space complexity of insertion sort is O(1). It is because, in insertion sort, an extra variable is required for swapping.