How to Use Insertion Sort Using Python?

Introduction to Insertion Sort

 

Insertion sort is a comparison sort in which the sorted array is built one entry at a time, this algorithm is one of the fastest sorting algorithms for smaller input, the reason it works faster for smaller input but crashes while facing larger size input will be discussed in this blog.

 

Insertion sort is a comparison-based sorting algorithm with In-place capability, which means there is no extra memory space required for the execution of the insertion sort algorithm, this algorithm is used primarily to sort smaller input size data in ascending or descending order. 

 

(Must read: Linear Search And Binary Search Using Python)

 

Insertion Sort Example

 

Let us take an example in order to understand the working of insertion sort

---

---

Initially, we have an array of 6 elements, in order to implement the insertion sort, we shall take two variables, i and j, now j is the index of the second element whereas i is the index of one element before j the index.

---

---

Making a temporary variable key to store the value of the jth element temporarily, now we shall compare the value of ‘i’ to the ‘key’. If the value of the element at ith index is greater than key, then place the value of the ith element at the index ‘i+1’, i.e the next index.

---

---

Now decrement ‘i’ by one, i.e i-1, if we do this, the ith index will become less than zero, and we don’t want that, therefore we will put the condition that the above swapping should work only if the value of i is greater than 0, otherwise A[i+1] = key

---

---

With this method, we have sorted the first two elements, now we will increment the value of j till the total length of an array so that all the elements get sorted the way the first two elements are sorted. 

---

---

Now, with each iteration on j, we will sort one more element and will eventually sort the whole list of arrays which also means that we need to have a for loop for j that works from j=1 to the length of the whole array to sort each and every element in the list.

 

(Also read: Scrapy Tutorial for Web Scraping With Python)

 

Insertion Sort's Advantages

 

Insertion sort provides several advantages-:

 

1. It is efficient for small data sets.

 

2. It is adaptive or in other words for data that is already substantially sorted. The complexity is Ө(n + d), where d is the number of inversions.

 

3. More efficient in practice than most other simple quadratic.

 

4. Insertion sort is considered to be stable, i.e it does not change the relative order of elements with equal keys.

 

5. Insertion sort is an In-place sorting algorithm, i.e requires only a constant amount o(1) of additional memory space.

 

6. It can sort a list as it receives it.

 

(Suggested blog: Dynamic Programming And DAC: Python Implementation and Examples)

 

Insertion Sort Python implementation

---

A= [9,5,3,10,7,29,2,12]

def Isort(A):

    

    for j in range(1,len(A)):

        key = A[j]

        i = j-1

        while i>-1 and A[i]>key:

            A[i+1]=A[i]

            i=i-1

            

        A[i+1] = key

Indexes in python start from ‘0’, therefore j will be at the ‘1’ index initially, and if the value is less than 0, the whole loop should break, this is what one must keep in mind while analyzing the code.

 

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already sorted list until no input element remains. Sorting is typically done in place. The resulting array after K iteration has the property where the k+1 entries are sorted. 

 

In each iteration, the remaining first remaining entry of the input is removed, inserted into the result at the correct position, with each element greater than X copied to the right as it is compared against X.

 

Time Complexity of Insertion Sort

 

• The best case input is an array that is already sorted. In this case, the insertion sort takes a linear running time Ө(n).

 

• The worst case of insertion sort input is an array sorted in the reverse order. In this case, every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time o(n2).

 

• The average case of insertion sort is also quadratic, which makes insertion sort impractical for sorting large arrays, however, insertion sort is one of the fastest algorithms for very small arrays and even faster than the quick sort.

 

(Top reading: What is a Restricted Boltzmann Machine?)

 

 

Comparison of Sorting Algorithms

 

Some important observations about sorting algorithms-:

 

1. Insertion sort takes Ө(n2) time in the worst case. It is a fast in-place sorting algorithm for small input sizes.

 

2. Merge sort has a better asymptotic running time Ө(nlogn) time, but it does not operate in place.

 

3. Heapsort, sorts ‘n’ numbers in place in Ө(nlogn) time, it uses a data structure called a heap, with which we can also implement a priority queue.

 

4. Quick sort also sorts ‘n’ numbers in place, but its worst-case running time is Ө(n2), its average case is Ө(nlogn). The constant factor in quick sort’s running time is small, this algorithm works better for large input arrays.

 

5. Insertion sort, merge sort, heap sort, and quick sort are all comparison-based sorting algorithms; they determine the sorted order of input by comparing elements.

 

6. We can beat the lower bound of Ω(nlogn) if we can gather information about the sorted order of the input by means other than comparing elements.

 

7. The counting sort algorithm assumes that the input numbers are in the set {1,2,....n}. By using array indexing as a tool for determining relative order, counting sort can sort n numbers in Ө(k + n) time. Thus counting sort runs in time that is linear in the size of the input array.

 

8. Radix sort can be used to extend the range of counting sort. If there are ‘n’ integers to sort, each integer has ‘d’ digits, and each digit in the set {1,2,,....k], then radix sort can sort the numbers in Ө(d(n+k)) time. Where ‘d’ is constant, therefore, radix sorts suns in linear time.

 

9. Bucket sort requires knowledge of the probabilistic distribution of numbers in the input array.

 

 

Conclusion

 

In this blog we learned about the insertion sort in detail, from example to the implementation of insertion sort using python, later on, we learned about the performance of insertion sort in terms of its complexity, all the cases, best, worst, and an average case of insertion sort is discussed. The last section of the blog was determined towards a fair comparison between various sorting algorithms.