Bubble Sort Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: Array, Sorting
Problem Statement
Implement the bubble sort algorithm to sort an array of integers in ascending order. 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.
Examples
Example 1:
Input: arr = [64, 34, 25, 12, 22, 11, 90]
Output: [11, 12, 22, 25, 34, 64, 90]
Explanation: After applying bubble sort, the array is sorted in ascending order.
Example 2:
Input: arr = [5, 2, 4, 6, 1, 3]
Output: [1, 2, 3, 4, 5, 6]
Explanation: The array is sorted from smallest to largest.
Example 3:
Input: arr = [1]
Output: [1]
Explanation: Single element array is already sorted.
Example 4:
Input: arr = [3, 3, 3, 3]
Output: [3, 3, 3, 3]
Explanation: Array with duplicate elements remains the same after sorting.
Intuition
Bubble sort works by repeatedly stepping through the list and swapping adjacent elements if they are in the wrong order. The algorithm gets its name because smaller elements "bubble" to the top of the list.
Key insights:
1. After each pass, the largest unsorted element "bubbles up" to its correct position
2. We need n-1 passes to sort n elements
3. In each pass, we compare adjacent elements and swap if necessary
4. We can optimize by stopping early if no swaps occur in a pass
Approach
Approach 1: Standard Bubble Sort
1. Use two nested loops
2. Outer loop runs n-1 times (n-1 passes)
3. Inner loop compares adjacent elements and swaps if needed
4. After each pass, the largest element is in its correct position
Approach 2: Optimized Bubble Sort
1. Add a flag to track if any swap occurred
2. If no swap occurs in a pass, the array is sorted
3. This optimization helps for partially sorted arrays
Approach 3: Two-Way Bubble Sort (Cocktail Sort)
1. Sort in both directions (left to right and right to left)
2. This can be more efficient for some cases
Dry Run
Let's trace through Example 1: arr = [64, 34, 25, 12, 22, 11, 90]
Pass 1:
- Compare 64, 34: 64 > 34, swap → [34, 64, 25, 12, 22, 11, 90]
- Compare 64, 25: 64 > 25, swap → [34, 25, 64, 12, 22, 11, 90]
- Compare 64, 12: 64 > 12, swap → [34, 25, 12, 64, 22, 11, 90]
- Compare 64, 22: 64 > 22, swap → [34, 25, 12, 22, 64, 11, 90]
- Compare 64, 11: 64 > 11, swap → [34, 25, 12, 22, 11, 64, 90]
- Compare 64, 90: 64 < 90, no swap → [34, 25, 12, 22, 11, 64, 90]
- After Pass 1: [34, 25, 12, 22, 11, 64, 90] (90 is in correct position)
Pass 2:
- Continue comparing and swapping...
- After Pass 2: [25, 12, 22, 11, 34, 64, 90] (64 is in correct position)
Continue until sorted:
- Final result: [11, 12, 22, 25, 34, 64, 90]
Key Insights
1. Stable Sort: Bubble sort is a stable sorting algorithm
2. In-place: No extra space required (O(1) space complexity)
3. Adaptive: Can be optimized to stop early if array is sorted
4. Simple: Easy to understand and implement
5. Inefficient: O(n²) time complexity makes it slow for large arrays
Edge Cases
1. Empty array: Return empty array
2. Single element: Return the element as is
3. Already sorted: Should work correctly
4. Reverse sorted: Worst case scenario
5. Duplicate elements: Should handle correctly
Time and Space Complexity
- Time Complexity: O(n²) in worst and average case, O(n) in best case (if optimized)
- Space Complexity: O(1) - in-place sorting algorithm