Searching and Sorting (Insertion Sort- Python/C++)

Why Searching and Sorting?

Searching is used to find an item in a list. Sorting is used to order a list. The advantages of searching are that it is fast and can be done on any type of data. The disadvantages of searching are that it can be slow if the list is large, and it can be difficult to find an item if the list is not well organized. The advantages of sorting are that it is easy to find an item in a well-ordered list, and it is easy to add or remove items from a sorted list. The disadvantages of sorting are that it can be slow if the list is large, and it can be difficult to maintain the order of a sorted list.

There are many reasons why searching and sorting are important in programming. Searching allows you to find a specific piece of data in a large set, while sorting organizes data in a way that makes it easier to find and use. Searching and sorting are essential to many applications, such as databases, eCommerce sites, and social networks. Without these algorithms, it would be very difficult to find the data you are looking for or to make sense of large data sets.

There are many different types of searching and sorting algorithms, each with its own advantages and disadvantages. Some of the most popular algorithms include:-

• Linear search: This is the most basic type of search algorithm. It simply searches through a list of items one by one until it finds the desired item.
• Binary search: This is a more efficient type of search algorithm that only searches through half of the list at a time.
• Bubble sort: This is a simple sorting algorithm that works by repeatedly swapping adjacent items if they are in the wrong order.
• Selection sort: This sorting algorithm works by finding the smallest item in the list and placing it at the start, then finding the second smallest item and placing it second, and so on.
• Insertion sort: This sorting algorithm works by starting at the beginning of the list and inserting each new item into its correct position.

We’ll take a look at the insertion sort incoming portion.

Insertion Sort

Insertion sort is a sorting algorithm that works by inserting each element of an array into its correct position in an already sorted array.

The steps can be visualized as:-

Insertion sort flow

For example, given the array [3,1,4,2], insertion sort would produce the array [1,2,3,4].

Pseudocode for insertion sort:

Pseudocode for Insertion Sort

Implementation of insertion sort in python:-

Python implementation of Insertion sort

Let's look at the space and time complexity:-

• Space complexity — O(1)
• Best case time complexity — O(n)
• Average case time complexity — O(n²)
• Worst-case time complexity — O(n²)

When to use insertion sort and when not to use insertion sort?

Insertion sort is a fast, in-place sorting algorithm that is relatively easy to implement. However, it is not as efficient as other sorting algorithms, such as quicksort or heapsort. Insertion sort is a good choice when the data is nearly sorted, or when the sort is being performed on a small data set. It is not a good choice for large data sets, because the running time is quadratic O(n²).

C++ implementation of insertion sort is given below:-

CPP implementation

Thanks for reading !!!!!!!!

Please feel free to reach out in case of any queries.

Aman Jaiswal - Machine Learning Engineer - CRMNEXT | LinkedIn