Insertion Sort vs Bubble Sort

When you’re learning about sorting algorithms, it’s helpful to compare different approaches to understand their strengths and weaknesses. Insertion sort and bubble sort are two simple sorting algorithms that are often taught early on. In this article, we’ll compare insertion sort and bubble sort, highlighting their differences, performance characteristics, and use cases. By the end, you’ll have a clear understanding of when to use each algorithm and why.

What are Insertion Sort and Bubble Sort?

Before we dive into the comparison, let’s briefly recap what these two algorithms do:

• Insertion Sort: This algorithm builds a sorted array one element at a time. It iterates through the array, picking up an element and inserting it into its correct position within the already sorted portion. It’s similar to how you might sort a hand of playing cards.
• Bubble Sort: This algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Elements “bubble” to their correct positions.

If you need a refresher, here’s a helpful link to the insertion sort article: Introduction to Insertion Sort Algorithm and bubble sort algorithm: Introduction to Bubble Sort Algorithm.

Key Differences

Let’s delve deeper into these differences and understand why they matter.

How They Work: A Closer Look

1. Insertion Sort:

   • Imagine you’re sorting a hand of cards. You pick up one card at a time and insert it into its correct position among the cards you’re already holding.
   • Insertion sort works similarly. It divides the array into a sorted and an unsorted region. It picks elements from the unsorted region and places them in the correct spot within the sorted region.
   • This involves shifting elements to make space for the inserted element.
   • For example, consider the list [5, 2, 4, 6, 1, 3]. Insertion sort would proceed as follows:
     • First, consider [5] as sorted sublist and [2, 4, 6, 1, 3] as unsorted sublist.
     • Pick 2 from unsorted list, compare it to 5 and insert to create the sorted sublist [2, 5] and the unsorted list becomes [4, 6, 1, 3].
     • Pick 4 from unsorted list, compare it to 5 and then 2 and insert to create the sorted sublist [2, 4, 5] and the unsorted list becomes [6, 1, 3].
     • Pick 6 from unsorted list, compare it to 5, 4 and then 2 and insert to create the sorted sublist [2, 4, 5, 6] and the unsorted list becomes [1, 3].
     • Pick 1 from unsorted list, compare it to 6, 5, 4, 2 insert to create the sorted sublist [1, 2, 4, 5, 6] and the unsorted list becomes [3].
     • Pick 3 from unsorted list, compare it to 6, 5, 4 and then 2, 1 and insert to create the sorted sublist [1, 2, 3, 4, 5, 6] and the unsorted list becomes empty [].

2. Bubble Sort:

   • Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they’re in the wrong order.
   • Heavier elements “bubble” to the end of the list with each pass.
   • The process is repeated until no more swaps are needed, indicating that the list is sorted.
   • For example, consider the list [5, 1, 4, 2, 8]. Bubble sort would work like this:
     • First Pass: Compares (5,1), swaps them: [1, 5, 4, 2, 8], compares (5,4), swaps them: [1, 4, 5, 2, 8], compares (5,2), swaps them: [1, 4, 2, 5, 8], compares (5,8), no swap: [1, 4, 2, 5, 8].
     • Second Pass: Compares (1,4), no swap: [1, 4, 2, 5, 8], compares (4,2), swaps them: [1, 2, 4, 5, 8], compares (4,5), no swap: [1, 2, 4, 5, 8], compares (5,8), no swap: [1, 2, 4, 5, 8].
     • Third Pass: Compares (1,2), no swap: [1, 2, 4, 5, 8], compares (2,4), no swap: [1, 2, 4, 5, 8], compares (4,5), no swap: [1, 2, 4, 5, 8], compares (5,8), no swap: [1, 2, 4, 5, 8].

Performance Characteristics

Both insertion sort and bubble sort have similar time complexities for best, average, and worst case scenarios. However, there are important practical differences in their performance:

• Number of Operations: While both algorithms have O(n^2) complexity, insertion sort typically performs fewer actual operations:

  • Insertion sort moves elements only as far as necessary
  • Bubble sort always performs adjacent swaps, potentially requiring multiple swaps to move an element to its final position
  • For example, to move an element from position 10 to position 1:
    • Insertion sort would shift elements once and insert
    • Bubble sort would need 9 separate swaps

• Adaptiveness: Both algorithms are adaptive, but insertion sort adapts better to partially sorted data:

  • Insertion sort immediately benefits from any existing order in the array
  • For example, consider a partially sorted array [4,1,2,3], insertion sort requires only one complete pass through the array in total. Whereas bubble sort requires two iterations over the entire array.

This is why in practice, even though both algorithms have the same theoretical time complexity, insertion sort usually performs significantly better than bubble sort, especially on partially sorted data or when elements are close to their final positions.

When to Use Which

• Insertion Sort:
  • Use insertion sort when you have a small dataset or when you expect the data to be nearly sorted.
  • It’s also a good choice when memory usage is a concern, as it’s an in-place algorithm.
  • Suitable for using it as an online algorithm, meaning it can sort the list as it receives it.
• Bubble Sort:
  • Bubble sort is mainly useful for educational purposes due to its simplicity.
  • Avoid using bubble sort in real-world applications unless simplicity is the absolute top priority and performance is not a concern.

Key Takeaways

• Insertion sort builds a sorted array by inserting elements into their correct positions.
• Bubble sort repeatedly compares and swaps adjacent elements.
• Both have a time complexity of O(n^2) in the average and worst cases.
• Insertion sort and bubble sort, both are adaptive and perform better on partially sorted data.
• However in most practical scenarios, insertion sort is a better choice than bubble sort. This is because insertion sort typically requires fewer comparisons and swaps, especially on nearly sorted data. Even though both have the same worst-case time complexity, the constant factors involved often make insertion sort faster in practice.

What’s Next?

Now that you understand the differences between insertion sort and bubble sort, you might want to explore:

• Insertion Sort vs Selection Sort
• Insertion Sort Algorithm: Time and Space Complexity
• Other Sorting Algorithms