Scribd
Upload
40 views13 pages

Insertion Sort Algorithm Explained

Insertion sort is an algorithm that builds a sorted array by inserting elements into their proper position in each iteration. It iterates from the first element to the last, inserting each element into the sorted portion of the array by comparing it to each element. It is efficient for small data sets but inefficient for large ones due to its quadratic time complexity.

Uploaded by

Gagambi Tubyas
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
40 views13 pages

Insertion Sort Algorithm Explained

Insertion sort is an algorithm that builds a sorted array by inserting elements into their proper position in each iteration. It iterates from the first element to the last, inserting each element into the sorted portion of the array by comparing it to each element. It is efficient for small data sets but inefficient for large ones due to its quadratic time complexity.

Uploaded by

Gagambi Tubyas
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structure and Algorithms

Insertion Sort
What is Insertion Sort?
An element that is to be 'inserted' into this sorted
sub-list must first locates its proper location and
then be inserted there. As a result, the term
"insertion sort" was formed.

Consider you have 10 cards out of a deck of cards


in your hand. And they are sorted, or arranged in
the ascending order of their numbers.
If I give you another card, and ask you to insert the
card in just the right position, so that the cards in
your hand are still sorted. What will you do?
Well, you will have to go through each card from the
starting or the back and find the right position for
the new card, comparing it's value with each card.
Once you find the right position, you will insert the
card there.

Similarly, if more new cards are provided to you, you


can easily repeat the same process and insert the
new cards and keep the cards sorted too.

This is exactly how insertion sort works. It starts


from the index 1(not 0), and each index starting
from index 1 is like a new card, that you have to
place at the right position in the sorted sub-array on
the left.
Following are some of the important
characteristics of Insertion Sort:
[Link] is efficient for smaller data sets, but very
inefficient for larger lists.
[Link] Sort is adaptive, that means it reduces
its total number of steps if a partially sorted array
is provided as input, making it efficient. [Link] is
better than Selection Sort and Bubble Sort
algorithms.
[Link] space complexity is less. Like bubble Sort,
insertion sort also requires a single additional
memory space.
[Link] is a stable sorting technique, as it does not
change the relative order of elements which are
equal.
[Link] is unstable sorting technique, the number
position change the relative order of elements
which are equal.
How Insertion Sort Works?
Following are the steps involved in insertion
sort:
[Link] start by making the second element of the
given array, i.e. element at index 1, the key. The
key element here is the new card that we need
to add to our existing sorted set of cards
(remember the example with cards above).
2. We compare the key element with the element(s)
before it, in this case, element at index 0: • If the
key element is less than the first element,
we insert the key element before the first
element.
• If the key element is greater than the first
element, then we insert it after the first element. 3.
Then, we make the third element of the array as key
and will compare it with elements to its left and
insert it at the right position.
4. And we go on repeating this, until the array is
sorted.
Example 1: Let's consider an array with values {5, 1,
6, 2, 4, 3}
As you can see in the diagram above, after
picking a key, we start iterating over the
elements to the left of the key.
We continue to move towards left if the
elements are greater than the key element and
stop when we find the element which is less
than the key element.
And, insert the key element after the element
which is less than the key element.
Example 2:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last
element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11
before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1]
are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements
from 11 to 13 will move one position ahead of their current
position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11
to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
Example 3:
Given Array: 6 5 3 1 8 7 2 4
i = 1, element = 5
Compare element = 5 with left side values. i.e. 5. condition 6 > 5 --> true. Swap
them.
56318724

now i = 2, element = 3
compare element with its left side values and swap them
6 > 3 --> true --> swap --> 5 3 6 1 8 7 2 4
5 > 3 --> true --> swap --> 3 5 6 1 8 7 2 4

now i = 3, element = 1
compare element(1) with its left side values and sort them.
6 > 1 --> true --> swap --> 3 5 1 6 8 7 2 4
5 > 1 --> true --> swap --> 3 1 5 6 8 7 2 4
3 > 1 --> true --> swap --> 1 3 5 6 8 7 2 4

now i = 4, element = 8
compare element (8) with its left side values and sort them. 6 > 8 --> false
--> no swap. that means all left side values are already sorted.
now i = 5, element = 7
compare element (7) with its left side values and sort them.
8 > 7 --> true --> swap --> 1 3 5 6 7 8 2 4
6 > 7 --> false --> no swap. All left side values are already sorted.

now i = 6, element 2
compare element (2) with its left side values and sort them.
8 > 2 --> true --> swap --> 1 3 5 6 7 2 8 4
7 > 2 --> true --> swap --> 1 3 5 6 2 7 8 4
6 > 2 --> true --> swap --> 1 3 5 2 6 7 8 4
5 > 2 --> true --> swap --> 1 3 2 5 6 7 8 4
3 > 2 --> true --> swap --> 1 2 3 5 6 7 8 4
1 > 2 --> false --> no swap. that means all left side values are
already sorted.
now i = 7, element 4
compare key(4) with its left side values and sort them.
8 > 4 --> true --> swap --> 1 2 3 5 6 7 4 8
7 > 4 --> true --> swap --> 1 2 3 5 6 4 7 8
6 > 4 --> true --> swap --> 1 2 3 5 4 6 7 8
5 > 4 --> true --> swap --> 1 2 3 4 5 6 7 8
3 > 4 --> false --> no swap. that means all left side values
are already sorted.
Reached end of array and stops processing.

Common questions

Powered by AI

Insertion sort determines the proper location for inserting a new element by comparing the new element, referred to as the key, with the elements to its left. It moves towards the left, shifting elements one position to the right if they are greater than the key, and stops when an element less than the key is found. The key is then inserted after this element. This ensures that the elements to the left of the key remain sorted .

Insertion sort begins by considering the second element of the array (index 1) as the key and compares it with the first element. It determines the position of this key relative to the first element and inserts it in the correct place. This process is repeated for each subsequent element until the array is sorted .

Insertion sort is preferred over bubble sort because it generally requires fewer comparisons and swaps, especially when dealing with partially sorted arrays. It is more efficient in terms of reducing the total number of steps when input arrays are partially sorted due to its adaptive nature .

Insertion sort deals with repeated values by maintaining their relative order. While shifting elements to insert a new element, if elements of the same value are encountered, insertion sort keeps them in their original order since no unnecessary swaps are performed when elements are equal, which preserves stability .

Insertion sort performs poorly on large datasets that are completely unsorted. This occurs because each new element must be compared with all previous elements in the worst case, resulting in a quadratic time complexity of O(n^2), inefficiently handling extensive comparisons and shifts .

Insertion sort is considered a stable sorting algorithm because it does not change the relative order of elements with equal keys. When elements are compared and found to be equal, insertion sort does not swap their positions, thus maintaining their original order .

When a key element is greater than all elements to its left in an insertion sort process, no shifting is required, and the key remains in its current position. This indicates that all elements are already sorted relative to the key value up to that point .

Insertion sort handles the insertion of the smallest element by comparing it all the way back to the beginning of the array. As it compares with each element to its left, each is shifted one position to the right until it reaches the start, where the smallest element is then placed in the first position of the sorted sub-array .

Insertion sort is adaptive, meaning that when elements are already sorted or partially sorted, it reduces the number of unnecessary comparisons and swaps. The loop detects when elements are in order, hence fewer operations are required, which makes it more efficient compared to fully unsorted data .

The space complexity of insertion sort is O(1) because it requires a constant amount of additional memory space beyond the original array. Only a single additional storage is needed for swapping elements during the sorting process, similar to bubble sort .

You might also like