Bubble sort is a simple sorting algorithm that works by repeatedly iterating through a list of elements,
comparing adjacent elements and swapping them if they are in the wrong order.
How Bubble Sort Works
1. Iteration: The algorithm iterates through the list of elements, comparing each pair of adjacent
elements.
2. Comparison: If a pair of elements is in the wrong order, the algorithm swaps them.
3. Repetition: The algorithm repeats the iteration process until no more swaps are needed, indicating
that the list is sorted.
Example
Suppose we have the following list of numbers: [5, 2, 8, 3, 1]
1. First iteration: Compare 5 and 2, swap because 5 > 2: [2, 5, 8, 3, 1]
2. Continue iteration: Compare 5 and 8, no swap; compare 8 and 3, swap because 8 > 3: [2, 5, 3, 8, 1]
3. Continue iteration: Compare 8 and 1, swap because 8 > 1: [2, 5, 3, 1, 8]
4. Repeat iterations: Continue iterating and swapping until the list is sorted: [1, 2, 3, 5, 8]
Time Complexity
- Best-case: O(n) when the list is already sorted
- Worst-case: O(n^2) when the list is reversed sorted
- Average-case: O(n^2) for random lists
Pros and Cons
- Pros: Simple to implement, easy to understand
- Cons: Not efficient for large datasets, slow performance
When to Use
- Small datasets: Bubble sort can be suitable for small datasets or educational purposes
- Nearly sorted data: Bubble sort can be efficient when the data is nearly sorted
Here's the pseudocode for Bubble Sort:
Bubble Sort Pseudocode
PROCEDURE BubbleSort(arr)
n = LENGTH(arr)
FOR i FROM 0 TO n-1
swapped = FALSE
FOR j FROM 0 TO n-i-1
IF arr[j] > arr[j+1]
SWAP arr[j] AND arr[j+1]
swapped = TRUE
IF NOT swapped
BREAK // Exit loop if no swaps were made
RETURN arr
END PROCEDURE
Explanation
1. Outer loop: Iterates n times, where n is the length of the array.
2. Inner loop: Iterates from the first element to the n-i-1 element.
3. Comparison and swap: If an element is greater than the next element, swap them and set swapped
to TRUE.
4. Early termination: If no swaps are made in an iteration, the array is already sorted, and we can exit
the loop.
This pseudocode provides a basic outline of the Bubble Sort algorithm. Let me know if you have any
questions or if you'd like me to elaborate on any part of the code!
Here's another example of Bubble Sort in pseudocode, with a slightly different implementation:
Bubble Sort Pseudocode (Alternative Implementation)
PROCEDURE BubbleSort(arr)
n = LENGTH(arr)
FOR i FROM 0 TO n-2
FOR j FROM 0 TO n-i-2
IF arr[j] > arr[j+1]
SWAP arr[j] AND arr[j+1]
RETURN arr
END PROCEDURE
Example Walkthrough
Suppose we have the following array: [4, 2, 9, 6, 5, 1]
1. First iteration: Compare 4 and 2, swap because 4 > 2: [2, 4, 9, 6, 5, 1]
2. Continue iteration: Compare 4 and 9, no swap; compare 9 and 6, swap because 9 > 6: [2, 4, 6, 9, 5,
1]
3. Continue iteration: Compare 9 and 5, swap because 9 > 5: [2, 4, 6, 5, 9, 1]
4. Continue iteration: Compare 9 and 1, swap because 9 > 1: [2, 4, 6, 5, 1, 9]
5. Repeat iterations: Continue iterating and swapping until the array is sorted: [1, 2, 4, 5, 6, 9]
