What is Insertion Sort?

Scribblers Den

3 weeks ago

Introduction

As we know, sorting algorithms are crucial in organizing and manipulating data efficiently. Of all these sorting algorithms one algorithm is known for its simplicity and effectiveness is nothing but the Insertion sort algorithm. In this blog article, we will explore all about selection sorting.

What is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one item at a time. In this sorting algorithm, we divide the array into two parts:
1. Sorted Subarray
2. Unsorted Subarray
This Algorithm is the most simple algorithm to sort an array. Initially, the sorted subarray contains only the first element then we pick 1st element from the unsorted subarray. Put it into temp. And then compare that temp value with the sorted array. If a temp value is greater than the last element of the sorted array then just move that shell into the sorted array and if it’s smaller than the last element then move that element to the next place and compare with the second last element. Do this process until and unless you find the right place for the temp value.

How Does Insertion Sort Work?

To learn the process of insertion sorting, we are taking a given example: A[] = {5 , 3 , 7 , 10 , 34 , 9 , 1}.

Step 1:

In insertion sort, we sort from left to right. So the most left element(0th element) is considered a sorted element. and after that, all elements will be considered into an unsorted array. Please check Fig. 1.

Step 2:

Now, to compare the unsorted element with the sorted element insert the first element of the unsorted array into the temp variable then that shell will be empty. And now, compare it with the most last element sorted array.

Tip:
1. To Pick an element from the unsorted array for sorting we start from left to right.
2. To compare the temp value with a sorted array we start from right to left.

Step 3:

Here, two conditions come into the picture. First, if the Temp value is greater than last element of the sorted array then just move that element into a sorted array as it is. Or if the Temp value is less than the last element of sorted array. Then shift right to that last element where the Temp value was stored.

Step 4:

Store the temp value in the sorted array.

Step 5:

Now in the second iteration, we have 2 elements in a sorted array. and 3rd one(7) is in temp. Now perform step number 2 and 3. So, 7 is greater than 5 then we will just move 7 into the sorted array. Please check FIg. 2 for more clarity.

Step 6:

Now, 10 will be into temp variable. and we will perform step number 2 and 3 again. Likewise, we are going to perform steps 2 and 3 until and unless we get a sorted array. Please check FIg. 2 and Fig. 3 for more clarity.

Implementation of Insertion Sort:

Implementing insertion sort requires knowledge of basic programming concepts such as recursion and arrays.

Here’s the algorithm in pseudocode:

InsertionSort(array)
    for i = 1 to length(array) - 1
        currentElement = array[i]
        j = i - 1
        while j >= 0 and array[j] > currentElement
            array[j + 1] = array[j]
            j = j - 1
        end while
        array[j + 1] = currentElement
    end for
end function

Best Practices for Using Insertion Sort

To make the most of Insertion Sort and optimize its performance, consider the following best practices:

Know the Data:
Understand the characteristics of your data before selecting Insertion Sort. It excels in scenarios like small input sizes or partially sorted arrays.
Benchmark and Compare:
Analyze the expected input size and compare the performance of Insertion Sort with other sorting algorithms. Choose the most appropriate algorithm based on your specific requirements.
Consider Optimization Techniques:
Apply optimization techniques such as early termination or adaptive variations of Insertion Sort to enhance its efficiency for particular cases.
Combine with Other Algorithms:
Insertion Sort can be used as a preliminary step in conjunction with more advanced sorting algorithms. For example, using Insertion Sort to partially sort the array before applying a more efficient algorithm can yield better results.

Conclusion

Insertion Sort is a fundamental sorting algorithm that offers simplicity, ease of implementation, and effectiveness for small input sizes or partially sorted arrays. While it may not be the optimal choice for large datasets, it has its unique applications and can be combined with other algorithms to improve overall sorting performance.

Follow Us on
https://www.linkedin.com/company/scribblers-den/
https://www.facebook.com/scribblersden.blogs

Thank You