Bubble Sort

Defining Bubble Sort

Principles of Bubble Sort Algorithm

• Compare the first and second elements in the list.
• If the first element is larger than the second, swap them.
• Move on to the next pair of elements and repeat the process.
• Continue doing this until you've gone through the entire list without having to make any swaps. At this point, the list is sorted.

Effectiveness of Bubble Sort

Working Mechanism of Bubble Sort

First Pass:
( 5 1 4 2 8 ) → ( 1 5 4 2 8 )
( 1 5 4 2 8 ) → ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

Second Pass:
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Third Pass:
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Digging into the Bubble Sort Example

Step-by-step Bubble Sorting Explanation

Consider an unsorted list of five elements: [5, 3, 4, 1, 2].

First pass:
(5, 3, 4, 1, 2) → (3, 5, 4, 1, 2)
(3, 5, 4, 1, 2) → (3, 4, 5, 1, 2)
(3, 4, 5, 1, 2) → (3, 4, 1, 5, 2)
(3, 4, 1, 5, 2) → (3, 4, 1, 2, 5)

Second pass:
(3, 4, 1, 2, 5) → (3, 4, 1, 2, 5)
(3, 4, 1, 2, 5) → (3, 1, 4, 2, 5)
(3, 1, 4, 2, 5) → (3, 1, 2, 4, 5)

Continued passes render the list completely sorted:
(1, 2, 3, 4, 5)

Real-life Scenarios of Bubble Sort Application

Detailed Study of Bubble Sort Time Complexity

Time Complexity in Bubble Sort

Comparisons in the first pass: n-1
Comparisons in the second pass: n-2
Comparisons in the third pass: n-3
...
Comparisons in the last pass: 1

Factors Affecting Bubble Sort’s Time Complexity

• If the input list is already sorted, Bubble Sort's ability to recognise this and optimise its performance comes into play, leading to an \(O(n)\) time complexity.
• For a list sorted in reverse order, Bubble Sort exhibits its worst performance, requiring as many iterations as there are elements, squared – leading to an \(O(n^{2})\) time complexity.
• If the data is arranged in no particular order (randomly), Bubble Sort also shows an \(O(n^{2})\) average case time complexity.

How to Reduce Bubble Sort Time Complexity

def bubbleSortOptimised(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if swapped == False:
            break

Advantages and Disadvantages of Bubble Sort

Upsides of Using Bubble Sort

• Simplicity: Bubble Sort is arguably one of the simplest sorting algorithms to understand and code. Its concept is easy to grasp, and the algorithm can be implemented with just a few lines of code, making it ideal for beginners in computer science and programming.
• Space Efficient: Bubble Sort is an in-place sorting algorithm. It only requires a single additional memory space, hence it has a space complexity of \(O(1)\), lending to its high memory efficiency.
• Detects whether the input is already sorted: With slight an optimisation, Bubble Sort can stop executing if the list is already sorted. This means it has a best-case time complexity of \(O(n)\), where \(n\) is the number of elements in the list, making it efficient for nearly sorted or completely sorted lists.
• Stable Algorithm: Bubble Sort is a stable sorting algorithm. This means it maintains the relative order of equal sort elements in the sorted output, which is a desirable property in many applications.

Limitations of Bubble Sort

• Poor Efficiency on Large Datasets: Bubble Sort's worst-case and average time complexity are both \(O (n^{2})\), where \(n\) is the number of items being sorted. This makes it inefficient for large datasets - the sorting process can become increasingly slow as the size of the list increases.
• Performance: Bubble Sort often requires more iterations than necessary to completely sort a list. Other, more efficient algorithms, such as Quicksort, Mergesort or Heapsort, are preferable for large datasets.
• Lack of Practical Usage: Due to its inefficiency, Bubble Sort isn’t often used in real-world applications, where other algorithms outperform it.

When to Use and Avoid Bubble Sort