Difference between Insertion Sort and Selection Sort

Insertion sort vs Selection sort Insertion sort and selection sort are the techniques used to sort the data. Majorly insertion sort and selection sort can be differentiated by the method they use to sort the data. The insertion sort inserts the values in a presorted file to sort a set of values. On the other hand, the selection sort finds the minimum number from the list and sort it in some order.

Sorting is a basic operation in which the elements of an array is arranged in some specific order to enhance its searchability. In simple words, the data is sorted so that it could be easily searched.

Content: Insertion Sort Vs Selection Sort

Comparison Chart

Basis for comparison	Insertion Sort	Selection Sort
Basic	The data is sorted by inserting the data into an existing sorted file.	The data is sorted by selecting and placing the consecutive elements in sorted location.
Nature	Stable	Unstable
Process to be followed	Elements are known beforehand while location to place them is searched.	Location is previously known while elements are searched.
Immediate data	Insertion sort is live sorting technique which can deal with immediate data.	It can not deal with immediate data, it needs to be present at the beginning.
Best case complexity	O(n)	O(n`²`)

Definition of Insertion Sort

Insertion sort works by inserting the set of values in the existing sorted file. It constructs the sorted array by inserting a single element at a time. This process continues until whole array is sorted in some order. The primary concept behind insertion sort is to insert each item into its appropriate place in the final list. The insertion sort method saves an effective amount of memory.

Working of the Insertion sort

It uses two sets of arrays where one stores the sorted data and other on unsorted data.
The sorting algorithm works until there are elements in the unsorted set.
Let’s assume there are ‘n’ number elements in the array. Initially, the element with index 0 (LB = 0) exists in the sorted set. Remaining elements are in the unsorted partition of the list.
The first element of the unsorted portion has array index 1 (If LB = 0).
After each iteration, it chooses the first element of the unsorted partition and inserts it into the proper place in the sorted set.

Advantages of Insertion sort

Easily implemented and very efficient when used with small sets of data.
The additional memory space requirement of insertion sort is less (i.e., O(1)).
It is considered to be live sorting technique as the list can be sorted as the new elements are received.
It is faster than other sorting algorithms.

Example :

Definition of Selection Sort

The Selection sort perform sorting by searching for the minimum value number and placing it into the first or last position according to the order (ascending or descending). The process of searching the minimum key and placing it in the proper position is continued until the all the elements are placed at right position.

Working of the Selection Sort

Suppose an array ARR with N elements in the memory.
In the first pass, the smallest key is searched along with its position then the ARR[POS] is swapped with ARR[0]. Therefore, ARR[0] is sorted.
In the second pass, again the position of the smallest value is determined in the subarray of N-1 elements. Interchange the ARR[POS] with ARR[1].
In the pass N-1, the same process is performed to sort the N number of elements.

Example :

Key Differences Between Insertion Sort and Selection Sort

The insertion sort usually performs the insert operation. On the contrary, the selection sort carries out the selection and positioning of the required elements.
Insertion sort is said to be stable while selection sort is not a stable algorithm.
In insertion sort algorithm the elements are previously known. In contrast, the selection sort contains the location beforehand.
Insertion sort is a live sorting technique where the arriving elements are immediately sorted in the list whereas selection sort cannot work well with immediate data.
The insertion sort has the O(n) running time in the best case. As against, the best case run time complexity of selection sort is O(n²).

Complexity of Insertion sort

The best case complexity of insertion sort is O(n) times, i.e. when the array is previously sorted. In the same way, when the array is sorted in reverse order, the first element of the unsorted array is to be compared with each element in the sorted set. So, in the worst case, running time of Insertion sort is quadratic, i.e., O(n²). In average case also it has to make the minimum (k-1)/2 comparisons. Hence, the average case also has quadratic running time O(n²).

Complexity of the Selection Sort

As the working of selection, sort does not depend on the original order of the elements in the array, so there is not much difference between best case and worst case complexity of selection sort.

The selection sort selects the minimum value element, in the selection process all the ‘n’ number of elements are scanned; therefore n-1 comparisons are made in the first pass. Then, the elements are interchanged. Similarly in the second pass also to find the second smallest element we require scanning of rest n-1 elements and the process is continued till the whole array sorted.

Thus, running time complexity of selection sort is O(n²).
= (n-1)+(n-2)+………..+2+1
= n(n-1)/2 = O(n²)

Conclusion

Among both of the sorting algorithm, the insertion sort is fast, efficient, stable while selection sort only works efficiently when the small set of elements is involved or the list is partially previously sorted. The number of comparisons made by selection sort is greater than the movements performed whereas in insertion sort the number of times an element is moved or swapped is greater than the comparisons made.