Scribd
Upload
15 views3 pages

Bubble Sort Guide

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, allowing the largest element to 'bubble up' to its correct position. It is a stable and in-place algorithm with a best-case time complexity of O(n) and a worst-case of O(n²). While easy to implement and efficient for nearly-sorted data, it is slow for large datasets compared to more advanced sorting algorithms.

Uploaded by

Yuvajit Boruah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views3 pages

Bubble Sort Guide

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, allowing the largest element to 'bubble up' to its correct position. It is a stable and in-place algorithm with a best-case time complexity of O(n) and a worst-case of O(n²). While easy to implement and efficient for nearly-sorted data, it is slow for large datasets compared to more advanced sorting algorithms.

Uploaded by

Yuvajit Boruah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Bubble Sort Algorithm

Bubble Sort is the simplest sorting algorithm that works by repeatedly


swapping adjacent elements if they are in the wrong order. It is called "bubble"
sort because with each iteration, the largest element "bubbles up" to its correct
position at the end of the list.

Key Characteristic: It is a stable sorting algorithm (maintains relative


order of equal elements) and an in-place algorithm (requires no extra
storage).

1. How It Works

Given an array of n elements:

1. Start at the beginning of the array.


2. Compare the current element with the next one.
3. If the current element is greater than the next, swap them.
4. Move to the next pair and repeat until the end of the array.
5. After the first pass, the largest element is at the end.
6. Repeat the process for the remaining n-1 elements.

2. Implementation (Python)

def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
swapped = False
# Last i elements are already in place
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

Bubble Sort Algorithm Guide Page 1


swapped = True

# If no two elements were swapped by inner loop, then break


if not swapped:
break

3. Complexity Analysis

Time
Case Reasoning
Complexity

Occurs when array is already sorted


Best Case O(n)
(with optimization).

Average Case O(n2) Typical nested loop behavior.

Occurs when array is sorted in reverse


Worst Case O(n2)
order.

Space Constant extra space used for


O(1)
Complexity swapping.

4. Optimization: The 'Swapped' Flag

In the standard version, Bubble Sort always runs $O(n^2)$ time even if the
array is sorted. To fix this, we use a boolean flag. If no two elements were
swapped during a pass, it means the array is already sorted, and we can
terminate the algorithm early.

Bubble Sort Algorithm Guide Page 2


5. Pros and Cons

Pros:

• Extremely simple to understand and implement.


• No extra memory required (In-place).
• Performs great on nearly-sorted data (when optimized).

Cons:

• Very slow for large datasets compared to QuickSort or MergeSort ($O(n


\log n)$).
• Requires many swaps, which can be computationally expensive.

Bubble Sort Algorithm Guide Page 3

You might also like