Introduction to Bubble Sort and Insertion Sort

Introduction

In our previous lesson, we explored linear and binary search algorithms. A key takeaway was that binary search is incredibly fast, but it only works on sorted data. This raises a crucial question: how do we get data sorted in the first place?

Today, we begin to answer that question by diving into the world of sorting algorithms. Sorting is a fundamental operation in computer science, and understanding how different sorting methods work is essential for your GATE preparation.

Your learning outcome for this lesson is to: Implement and analyze simple sorting algorithms: bubble sort and insertion sort.

We will cover:

• The logic, implementation, and analysis of Bubble Sort.
• The logic, implementation, and analysis of Insertion Sort.
• How to analyze their efficiency (time and space complexity) using Big-O notation for best, average, and worst-case scenarios.
• A comparison of their performance to understand their practical trade-offs.

Let's get started with one of the most well-known sorting algorithms.

1. Bubble Sort: The "Sinking" Stone Approach

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. With each pass through the list, the next largest element "bubbles up" (or sinks) to its correct position at the end of the unsorted portion.

Imagine a series of stones of different weights in water; the heaviest ones will sink to the bottom first. Bubble sort works in a similar way.

To see the mechanics of this process in detail, let's watch a step-by-step walkthrough.

Python Implementation

Now that you've seen how it works conceptually, let's implement it in Python. A common implementation uses two nested loops: the outer loop controls the number of passes, and the inner loop performs the adjacent comparisons and swaps.

For a comprehensive look at the code and its explanation, we'll turn to a detailed article.

Here is the code from the article for your reference:

def bubble_sort(array):
    n = len(array)

    for i in range(n):
        # Create a flag that will allow the function to terminate early
        already_sorted = True

        # The inner loop performs the comparisons. The range shrinks
        # with each pass because the largest elements are already sorted.
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                # Swap the elements
                array[j], array[j + 1] = array[j + 1], array[j]

                # If a swap occurred, the list is not yet sorted
                already_sorted = False

        # If no swaps occurred in a pass, the array is sorted
        if already_sorted:
            break

    return array

# --- Example Usage ---
my_list = [10, 9, 11, 6, 15, 2]
print(f"Original list: {my_list}")

sorted_list = bubble_sort(my_list)
print(f"Sorted list: {sorted_list}")

Analysis of Bubble Sort

Analyzing an algorithm's efficiency is a critical skill for the GATE exam. We need to understand its time and space complexity.

• Time Complexity:
  The two nested loops are the key. The algorithm performs approximately $n(n-1)/2$ comparisons, which, in Big-O notation, simplifies to $O(n^2)$.

  • Worst Case: $O(n^2)$. This occurs when the list is in reverse order.
  • Average Case: $O(n^2)$. For a randomly ordered list.
  • Best Case: $O(n)$. This occurs when the list is already sorted, and we use the already_sorted flag optimization. The algorithm makes a single pass through the list to confirm it's sorted and then terminates.

• Space Complexity:
  Bubble sort only requires a few variables to keep track of indices and a temporary variable for swapping (though Python's tuple-swapping a, b = b, a hides this). It does not create any new data structures proportional to the input size. This makes its space complexity $O(1)$, or constant space. It's an in-place sorting algorithm.

For a more rigorous mathematical derivation of the time complexity, which is highly relevant for your engineering background and GATE prep, please watch the next segment of the Gate Smashers video.

2. Insertion Sort: Sorting Cards in Your Hand

Insertion sort is another simple algorithm that builds the final sorted list one item at a time. It's similar to how many people sort a hand of playing cards. You take one card at a time and insert it into its correct position within the cards you've already sorted.

The algorithm maintains a sorted sublist at the beginning of the array. It takes the first element from the unsorted part and "inserts" it into the correct position in the sorted sublist by shifting larger elements one position to the right.

Python Implementation and Analysis

Like Bubble Sort, Insertion Sort is straightforward to implement and has a quadratic time complexity in the average case. However, as we'll see, it has some performance advantages.

Here is the code from the article for your reference:

def insertion_sort(array):
    # Loop from the second element (index 1) to the end
    for i in range(1, len(array)):
        # The element we want to position correctly
        key_item = array[i]
        
        # Initialize j to the index before the key_item
        j = i - 1

        # Run through the sorted portion (left side) and shift
        # all elements greater than key_item to the right.
        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1
        
        # Insert the key_item in its correct location
        array[j + 1] = key_item
        
    return array

# --- Example Usage ---
my_list = [10, 9, 11, 6, 15, 2]
print(f"Original list: {my_list}")

sorted_list = insertion_sort(my_list)
print(f"Sorted list: {sorted_list}")

Analysis of Insertion Sort

• Time Complexity:

  • Worst Case: $O(n^2)$. Occurs when the array is sorted in reverse order. The inner while loop has to shift every element in the sorted sublist for each new key.
  • Average Case: $O(n^2)$. For a random list.
  • Best Case: $O(n)$. Occurs when the array is already sorted. The inner while loop condition (array[j] > key_item) is immediately false for every element, so only the outer loop runs.

• Space Complexity:
  Like bubble sort, insertion sort is an in-place algorithm that requires only a constant amount of extra memory. Its space complexity is $O(1)$.

Bubble Sort vs. Insertion Sort

Even though both algorithms have an average time complexity of $O(n^2)$, insertion sort generally performs better in practice. Why?

1. Fewer Swaps: Bubble sort performs a swap every time two adjacent elements are out of order. Insertion sort only shifts elements and performs a single insertion for each key item.
2. Adaptive Nature: Insertion sort is highly efficient for data that is already "mostly sorted." If the list is nearly in order, the inner loop rarely runs, and the performance approaches $O(n)$.

The timing experiments in the Real Python article you read clearly demonstrate this practical performance difference.

Conclusion

Congratulations! You have now implemented and analyzed two of the most fundamental sorting algorithms. While they may not be the most efficient for large datasets, they provide an essential foundation for understanding more complex algorithms.

Key Takeaways:

• Bubble Sort works by repeatedly swapping adjacent elements. It's simple to understand but generally inefficient.
  • Time Complexity: $O(n^2)$ on average.
  • Space Complexity: $O(1)$.
• Insertion Sort works by building a sorted sublist and inserting elements into it. It's also simple and is generally more efficient than bubble sort in practice.
  • Time Complexity: $O(n^2)$ on average, but $O(n)$ in the best case, making it adaptive.
  • Space Complexity: $O(1)$.
• Analyzing algorithms in terms of their best, average, and worst-case scenarios is crucial for making informed decisions.

Preview of the Next Lesson:

The $O(n^2)$ complexity of bubble and insertion sort makes them impractical for sorting large lists. For your GATE exam and real-world applications, you'll need faster methods. In the next lesson, we will explore advanced sorting algorithms that use a "divide and conquer" strategy to achieve a much better time complexity. You will implement and analyze merge sort and quick sort, two of the most important and efficient sorting algorithms in computer science.