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 Bubble Sort

In this article, we will see the major differences between Insertion Sort and Bubble Sort. Before that, let’s have a quick overview of what these sorting algorithms are and what’s the idea behind them.

What is Insertion Sort?

Insertion Sort – In Insertion sort, we select all elements of the unsorted array and place them at their correct position in the sorted array. After each iteration, the sorted array’s size increases and the unsorted array's size decreases. The pseudo-code of the insertion sort function is given below:

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

The for-loop runs from 1 to n-1 and the while-loop runs from i = j-1 to 0. After complete execution of the internal while-loop, the element at the jth index is placed at its correct position in the sorted array.

Let’s understand the above idea through an example-

Consider an unsorted array a[] = {25, 10, 12, 18, 6}. Let’s apply insertion sort on it:

Insertion Sort Vs Bubble Sort
  • First Iteration – j = 1, i = 0 to 0, and Key = a[j] = a[1] = 10
    • Here, i is greater than -1 and a[i = 0] = 25 > key = 10. The condition of while loop is satisfied, we place 25 at index 1, and decrement i by 1.
Insertion Sort Vs Bubble Sort
  • Now, i is equal to -1, hence the condition is not satisfied. We execute the last statement. a[i + 1] = a[-1 + 1] = a[0] = Key = 10. Now, the array will be like as shown in figure.
Insertion Sort Vs Bubble Sort
  • Second Iteration – j = 2, i = 1 to 0, and Key = a[2] = 12.
    • Here, i = 1, a[i] = 25 > Key, the while-condition is satisfied. We execute a[1+1] = a[1] = 25 and i = 1-1 = 0.
Insertion Sort Vs Bubble Sort
  • Now, i = 0 and a[0] = 10 < key = 12. The while condition is not satisfied. We execute the last statement, a[i+1] = a[0+1] = 12.
Insertion Sort Vs Bubble Sort
  • Third Iteration – j = 3, i = 2 to 0, and Key = a[3] = 18
    • Here, i = 2, a[i] = 25 > Key = 18. The while condition is satisfied. We execute a[2+1] = a[2] = 25 and i = 2 - 1 = 1
Insertion Sort Vs Bubble Sort
  • Now, i = 1, a[i] = 12 < Key = 18. The while condition is not satisfied. We execute the last statement, a[i + 1] = a[1 + 1] = 18.
Insertion Sort Vs Bubble Sort
  • Fourth Iteration – j = 4, i = 3 to 0, and Key = a[4] = 6.
    • Here, i = 3, a[i] = 25 > Key = 6. The while condition is satisfied. We execute a[3 + 1] = a[3] = 25 and i = 3 - 1 = 2.
Insertion Sort Vs Bubble Sort
  • Now, i = 2, a[i] = 18 > Key = 6. The while condition is satisfied. We execute a[2 + 1] = a[2] = 18 and i = 2 - 1 = 1.
Insertion Sort Vs Bubble Sort
  • Now, i = 1, a[i] = 12 > Key = 6. The while condition is satisfied. We execute a[1 + 1] = a[1] = 12 and i = 1 - 1 = 0.
Insertion Sort Vs Bubble Sort
  • Now, i = 0, a[i] = 10 > Key = 6. The while condition is satisfied. We execute a[0 + 1] = a[0] = 10 and i = 0 - 1 = -1.
Insertion Sort Vs Bubble Sort
  • Now, i is equal to -1, hence the condition is not satisfied. We execute the last statement. a[i + 1] = a[-1 + 1] = a[0] = Key = 6. Now, the array will be like as shown in figure.
Insertion Sort Vs Bubble Sort

After complete execution of the 4th iteration, we get our sorted array.

What is Bubble Sort?

Bubble Sort – In bubble sort, it continuously compares two adjacent elements and swaps them if they are not in the right order on each iteration. On each pass, it places the largest value at the end of the unsorted array. The pseudo-code of the bubble sort function is given below:

Bubble Sort (int a[], int n)
{
	For i =1 to n-1
	{
		for j = 0 to n - i – 1
		{
			If a[j] > a[j + 1]
				swap (a[j], a[j + 1])
		}
	}
} // Where n is the size of the array

We can clearly see in the above pseudo-code that the external for loop starts from 1 and ends at n - 1, and the internal for-loop starts from 0 and ends at n - i - 1.

Let’s understand the above idea through an example:

Consider an unsorted array a[5] = {25, 10, 12, 18, 6}. Let’s sort this array using bubble sort.

Insertion Sort Vs Bubble Sort
  • First Iteration – i = 1, j 0 to n – 1 – 1 = 3.
    • j = 0. Here, a[0] = 25 and a[1] = 10 and 25 > 10, If-condition is satisfied, we swap these values.
Insertion Sort Vs Bubble Sort
  • j = 1. Here, a[1] = 25 and a[2] = 12 and 25 > 12, If-condition is satisfied, we swap these values.
Insertion Sort Vs Bubble Sort
  • j = 2. Here, a[2] = 25 and a[3] = 18 and 25 > 18, If-condition is satisfied, we swap these values:
Insertion Sort Vs Bubble Sort
  • j = 3. Here, a[3] = 25 and a[4] = 6 and 25 > 16, If-condition is satisfied, we swap these values:
Insertion Sort Vs Bubble Sort
  • Second Iteration – i = 2, j = 0 to 2
    • j = 0. Here, a[0] = 10 and a[1] = 12 and 10 < 12, If-condition is not satisfied, no swapping occurs:
Insertion Sort Vs Bubble Sort
  • j = 1. Here, a[1] = 12 and a[2] = 18 and 12 < 18, If-condition is not satisfied, no swapping occurs:
Insertion Sort Vs Bubble Sort
  • j = 2. Here, a[2] = 18 and a[3] = 6 and 18 > 6, If-condition is satisfied, we swap these values:
Insertion Sort Vs Bubble Sort
  • Third Iteration – i = 3, j 0 to 1
    • j = 0. Here, a[0] = 10 and a[1] = 12 and 10 < 12, If-condition is not satisfied, no swapping occurs:
Insertion Sort Vs Bubble Sort
  • j = 1. Here, a[1] = 12 and a[2] = 6 and 12 > 6, If-condition is satisfied, we swap these values:
Insertion Sort Vs Bubble Sort
  • Fourth Iteration – i = 4, j 0 to 0
    • j = 0. Here, a[0] = 10 and a[1] = 6 and 10 > 6, If-condition is satisfied, we swap these values.
Insertion Sort Vs Bubble Sort

After complete execution of the external for loop, we get a sorted array.

Differences between Insertion Sort and Bubble Sort:

The main differences between these two sorting techniques are listed below in the table:

Insertion Sort Vs Bubble Sort

Insertion Sort

Bubble Sort

Idea/

Approach

The idea is to insert an element of the unsorted array at its correct position in the sorted array.

The idea is to compare every place and place them in the right order.

Time Complexity

Best

Average

Worst

Best

Average

Worst

T(n) = O(n)

T(n) = O(n^2)

T(n) = O(n^2)

T(n) = O(n)

T(n) = O(n^2)

T(n) = O(n^2)

Space Complexity

Worst Case: T(n) = O(1)

Worst Case: T(n) = O(1)

Efficiency

More efficient than the Bubble Sort.

Less Efficient than the Insertion Sort

Speed

Faster than the Bubble Sort as less comparison and swapping occur.

Slower than the Insertion sort as more comparisons and swapping occur.

Stability

Stable – Element’s orders remain preserved

Stable – Element’s Orders remain preserved

Method

The insertion method is used to sort an array.

The comparison method is used to sort an array.



ADVERTISEMENT
ADVERTISEMENT