Bubble Sort
Problem
Bubble Sort is a simple sorting algorithm that 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 the list is sorted.
Examples:
Example 1:
Input: [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: The algorithm performs multiple passes, swapping adjacent elements until the array is sorted.
Example 2:
Input: [9, 8, 7, 6, 5]
Output: [5, 6, 7, 8, 9]
Explanation: This is the worst-case scenario where every element needs to be swapped.
Solution
Intuition
- Bubble Sort works by repeatedly stepping through the list and comparing adjacent elements.
- If the elements are in the wrong order, they are swapped.
- This process is repeated until no more swaps are needed, which indicates that the list is sorted.
- The algorithm gets its name because smaller elements 'bubble' to the top of the list with each iteration.
Approach
- Start at the beginning of the array.
- Compare the current element with the next element.
- If the current element is greater than the next element, swap them.
- Move to the next element and repeat steps 2-3 until the end of the array.
- After one complete pass, the largest element will be at the end of the array.
- Repeat steps 1-5 for the remaining elements (excluding the already sorted elements at the end).
- Continue until no more swaps are needed.
Complexity Analysis
- Time Complexity: O(n²) in worst and average cases, O(n) in best case (when the array is already sorted)
- Space Complexity: O(1) as it only requires a single additional memory space for the swap operation
Implementation
CPP
Run your code to see output here