# Bubble Sort

## Problem Description

Implement bubble sort, a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.

## What is Bubble Sort?

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Larger elements "bubble up" to the end of the array.

## Characteristics

- **Time Complexity**: 
  - Worst case: O(n²)
  - Average case: O(n²)
  - Best case: O(n) with optimization
- **Space Complexity**: O(1) - sorts in place
- **Stability**: Stable (preserves relative order of equal elements)
- **Adaptive**: Can be optimized to detect if array is already sorted

## How It Works

1. Compare adjacent elements
2. Swap them if they're in wrong order
3. After each pass, the largest unsorted element reaches its correct position
4. Repeat until no swaps are needed

## Visual Example
```
Pass 1: [5, 2, 8, 1] → [2, 5, 8, 1] → [2, 5, 1, 8]
Pass 2: [2, 5, 1, 8] → [2, 1, 5, 8]
Pass 3: [2, 1, 5, 8] → [1, 2, 5, 8]
```

## Your Task

Implement the following methods in `BubbleSort.java`:

1. `sort(int[] arr)` - Basic bubble sort
2. `sortOptimized(int[] arr)` - Optimized version with early termination

## Test Cases to Consider

- Already sorted array (best case for optimized version)
- Reverse sorted array (worst case)
- Array with duplicates
- Single element array
- Empty array
- Random unsorted array

## Hints

- Use nested loops: outer loop for passes, inner loop for comparisons
- After each pass, you can reduce the inner loop range by 1
- For optimization: use a flag to detect if any swaps occurred in a pass
- If no swaps in a pass, the array is sorted

## Optimization Strategies

1. **Early termination**: If no swaps in a pass, array is sorted
2. **Reduced range**: After each pass, reduce inner loop by 1
3. **Cocktail sort**: Alternate between forward and backward passes

## Common Pitfalls

- Off-by-one errors in loop bounds
- Not reducing inner loop range (inefficient)
- Swapping incorrectly

## When to Use Bubble Sort

**Use when:**
- Educational purposes (easy to understand)
- Array is nearly sorted (with optimization)
- Small datasets
- Simplicity is more important than efficiency

**Avoid when:**
- Large datasets (use QuickSort, MergeSort, or HeapSort)
- Performance is critical

## Follow-up Questions

1. How would you modify bubble sort to sort in descending order?
2. Can you implement a bidirectional bubble sort (Cocktail sort)?
3. How many swaps does bubble sort make in the worst case?
4. Is bubble sort stable? Why or why not?

## Comparison with Other Sorts

| Algorithm | Time (Avg) | Time (Worst) | Space | Stable |
|-----------|-----------|-------------|-------|--------|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |

## Related Algorithms

- Selection Sort
- Insertion Sort
- Cocktail Shaker Sort