Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing

Insertion Sort vs Selection Sort

In this article, we will discuss insertion sort, Selection sort and the basic differences between these two sorting techniques in detail:

What is Insertion Sort?

Insertion Sort – The insertion sort is one of the simple sorting techniques in which we insert an element of the unsorted array at its correct position in the sorted array.

We can understand the above idea through the given pseudo-code of the Insertion Sort function:

Insertion sort (a[], n)
{
	For j 1 to n-1
	{	
		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
	}
} // Where n is the size of the array

In the above code, we run the for-loop from 1 to n-1 and the while-loop from 0 to j -1, where the value of j depends on the for a loop.

Let us sort an array using the Insertion sort to get the complete idea of it:

Consider an array a[] = {45, 26, 12, 29, 8}. Let us now understand the steps included to sort the given array.

Insertion Sort Vs Selection Sort
  • First Iteration – j = 1, i = 0 to 0, and Key = a[j] = a[1] = 26
    • Here, i > -1 and a[i = 0] = 45 > key = 26. The while-loop condition is satisfied. We execute a[0+1] = a[0] = 45 and i = 0 – 1 = -1. Now the array is like a[] = {45, 45, 12, 29, 8}.
    • Now, i = -1, the while loop condition is not satisfied. We execute a[0+1] = 26. The array is like a[] = {26, 45, 12, 29, 8}.
  • Second Iteration – j = 2, i = 1 to 0, and key = a[j] = 12
    • i = 1 and a[1] = 45 > key = 12. The while Loop condition is satisfied. We execute a[1+1] = a[1] = 45 and i = 1 – 1 = 0. Now the array is like a[] = {26, 45, 45, 29, 8}.
    • i = 0 and a[0] = 26 > key = 12. The while Loop condition is satisfied. We execute a[0+1] = a[0] = 26 and i = 0 – 1 = -1. Now the array is like a[] = {26, 26, 45, 29, 8}.
    • i = -1. We execute the last statement, a[-1 + 0] = a[0] = key = 12. Now, a[] = {12, 26, 25, 29, 8}.
  • Third Iteration – j = 3, i = 2 to 0, and key = a[3] = 29
    • i = 2 and a[2] = 45 > key = 29. The while Loop condition is satisfied. We execute a[2+1] = a[2] = 45 and i = 2 – 1 = 1. Now the array is like a[] = {12, 26, 45, 45, 8}.
    • i = 1 and a[1] = 26 < key = 29. The while loop condition is not satisfied. We execute a[1+1] = key = 29. The array is like a[] = {12, 26, 29, 45, 8}.
  • Fourth Iteration – j = 4, i = 3 to 0, and key = a[4] = 8
    • i = 3 and a[3] = 45 > key = 8. The while Loop condition is satisfied. We execute a[3+1] = a[3] = 45 and i = 3 – 1 = 2. Now the array is like a[] = {12, 26, 29, 45, 45}.
    • i = 2 and a[2] = 29 > key = 8. The while Loop condition is satisfied. We execute a[2+1] = a[2] = 29 and i = 2 – 1 = 1. Now the array is like a[] = {12, 26, 29, 29, 45}.
    • i = 1 and a[1] = 26 > key = 8. The while Loop condition is satisfied. We execute a[1+1] = a[1] = 26 and i = 1 – 1 = 0. Now the array is like a[] = {12, 26, 26, 29, 45}.
    • i = 0 and a[0] = 12 > key = 8. The while Loop condition is satisfied. We execute a[0+1] = a[0] = 12 and i = 0 – 1 = -1. Now the array is like a[] = {12, 12, 26, 29, 45}.
    • i = -1. We execute the last statement, a[-1 + 0] = a[0] = key = 8. Now, a[] = {8, 12, 26, 29, 45}.

      After complete execution of the Fourth Iteration, we get our sorted array. The above steps are also shown in the figure given below:
Insertion Sort Vs Selection Sort

What is Selection Sort?

Selection Sort – In this sorting technique, we select the smallest element and replace it with the first element of the unsorted part of the array. The idea is implemented by considering the whole array as two subarrays, one sorted and another unsorted subarray. Initially, the size of the sorted array is taken to zero, and it increases with each iteration and becomes equal to the size of the array after the complete execution.

The size of the unsorted subarray decreases after each iteration and finally becomes zero after complete execution.

The Pseudo-code of the selection sort function is explained below:

Selection Sort (int a[], int n) 
{
    For i = 0 to n - 2 
    {
        Min_index = i; 
        For j = i+1 to n - 1 
        {
            If (a[j] < a[Min_index]) 
                Min_index = j;
        }
        If i != Min_index
       	      swap(a[i], a[Min_index]); 
    }
} // Where Min_index is the index of the minimum element and n is the size of the array.

We can see in the above pseudo-code that the external for loop runs from 0 to n – 2, and the internal for loop runs from i + 1 to n – 1.

Let us sort an array using the selection sort to get a complete overview of this sorting technique:

Consider an unsorted array a[] = {18, 26, 12, 30, 8} of size = 5. The steps included in sorting the given array using selection sort are given below:

Insertion Sort Vs Selection Sort
  • First Iteration – i = 0, j = 0 + 1 to 5 – 1 = 4. Min_index = i = 0.
    • The internal for loop runs and finds the index of the smallest element of the array and updates the value of Min_index. Here, 8 is the smallest element, after execution of the first for loop, Min_index will become equal to 4.
    • Now, we check the if-condition. Here, i = 0 and Min_index = 4, the condition is satisfied. We swap a[i] = 18 with a[min_index] = 8. The smallest element is at its correct position, a[] = {8, 26, 12, 30, 18}
Insertion Sort Vs Selection Sort
  • Second Iteration – i = 1, j = 2 to 4, Min_index = 1
    • The smallest element in the unsorted subarray is 12 at index = 2. After complete execution of the internal for-loop, Min_index will become equal to 2.
    • We check the if-condition. Here, i = 1 and min_index = 2. The if-conditioned is satisfied. We swap a[i] = 26 and a[Min_index] = 12. The second smallest value reaches to its correct position in the sorted array, a[] = {8, 12, 26, 30, 18}.
Insertion Sort Vs Selection Sort
  • Third Iteration – i = 2, j = 3 to 4, Min_index = 2
    • The smallest value in the unsorted subarray is 28, which is at index = 4. After executing the internal for-loop, the Min_index will become equal to 4.
    • We check the if-condition. Here, i = 2 and min_index = 4. The if-conditioned is satisfied. We swap a[i] = 26 and a[Min_index] = 18. The third smallest value reaches to its correct position in the sorted array, a[] = {8, 12, 18, 30, 26}.
Insertion Sort Vs Selection Sort
  • Fourth Iteration – i = 3, j = 4 to 4, Min_index = 3
    • The smallest value in the unsorted subarray is 26 at index = 4. After executing the internal for-loop. The Min_index will become equal to 4.
    • We check the if-condition. Here, i = 3 and min_index = 4. The if-conditioned is satisfied. We swap a[i] = 30 and a[Min_index] = 26. The fourth smallest value reaches to its correct position and also the largest element reaches to its correct position in the sorted array, a[] = {8, 12, 18, 30, 26}.
Insertion Sort Vs Selection Sort

After complete execution of the program, we get the sorted array as an output.

Difference between Insertion Sort and Selection Sort

Insertion Sort Vs Selection Sort

The main differences between insertion sort and selection sort are listed below in the table:

 Insertion SortSelection Sort
Idea / ApproachThe idea behind this sorting algorithm is that it inserts the first element of the unsorted subarray in the sorted subarray at its correct position.The idea behind this sorting algorithm is that it selects the minimum element from the unsorted array and replaces it with its first element.
Time ComplexitiesWhen we pass a sorted array to the insertion sort function, its time complexity becomes O(n). Its average and worst time complexities are O(n^2).  The best, average and worst-case time complexities are O(n^2). It runs n^2 times for all cases.
Space complexityIn the worst case, its space complexity is T(n) = O(1) as it does not require extra space to sort an array.In the worst case, its space complexity is also T(n) = O(1).
EfficiencyInsertion sort is more efficient than Selection Sort.Less efficient than Insertion Sort.
StabilityIt is a stable sorting algorithm as the order of equal elements remains preserved.It is an unstable sorting algorithm as the order of equal elements remains unpreserved.
SpeedFaster than the selection sort.Slower than the insertion sort.
MethodIt follows the incremental approach.It follows the selection approach.



ADVERTISEMENT
ADVERTISEMENT