Sorting I: Bubble Sort Implementation

Implementation Steps

1. 1

   Basic Implementation

   Implement the outer and inner loops for array traversal

   public void bubbleSort(int[] arr) { // Check for null or empty array if (arr == null || arr.length <= 1) { return; // Already sorted } for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // Compare adjacent elements if (arr[j] > arr[j + 1]) { // Swap them if they are in wrong order int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }

   How Bubble Sort Works:

   1. The outer loop runs for (n-1) passes, where n is the array length.
   2. In each pass, the inner loop compares adjacent elements and swaps them if needed.
   3. After each pass, the largest unsorted element "bubbles up" to its correct position.
   4. The inner loop's range decreases with each pass since the largest elements are already in place.
2. 2

   Optimization

   Add a flag to detect if array is already sorted

   public void optimizedBubbleSort(int[] arr) { // Check for null or empty array if (arr == null || arr.length <= 1) { return; // Already sorted } boolean swapped; for (int i = 0; i < arr.length - 1; i++) { swapped = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // If no swapping occurred, array is sorted if (!swapped) break; } }

   Optimization Benefits:

   • Early Termination: If no swaps occur in a pass, the array is already sorted.
   • Best-case Time Complexity: Improved to O(n) for already sorted arrays.
   • Average Performance: Better in practice for partially sorted arrays.
3. 3

   Algorithm Analysis

   Time Complexity

   • Worst Case: O(n²) - When array is reverse sorted
   • Average Case: O(n²) - For random arrangements
   • Best Case: O(n) - When array is already sorted (optimized version)

   Space Complexity

   • O(1) - Only uses a constant amount of extra space

   When to Use Bubble Sort:

   • Educational purposes to understand sorting concepts
   • Small datasets where simplicity is more important than efficiency
   • Nearly sorted arrays with the optimized version

Visual Example of Bubble Sort

Let's visualize how bubble sort works with the array [5, 3, 8, 4, 2]:

Notice how after each pass, the largest unsorted element "bubbles up" to its correct position (highlighted in green).

Common Bubble Sort Variations

1. Bidirectional Bubble Sort (Cocktail Shaker Sort)

This variation traverses the array in both directions, pushing both the largest and smallest values to their correct positions in a single pass.

2. Recursive Bubble Sort

A recursive implementation of bubble sort:

Exercise 1: Basic Bubble Sort

Implement the basic bubble sort algorithm to sort an array in ascending order.

public void bubbleSort(int[] arr) {
    // Your implementation here
}

Exercise 2: Optimized Implementation

Implement an optimized version of bubble sort that stops when the array is sorted.

public void optimizedBubbleSort(int[] arr) {
    // Your implementation here
    // Add optimization to break when no swaps needed
}

Exercise 3: Descending Order Sort

Modify the bubble sort algorithm to sort in descending order.

public void bubbleSortDescending(int[] arr) {
    // Your implementation here
    // Sort array in descending order
}

Exercise 4: Implement Cocktail Shaker Sort

Implement the cocktail shaker sort (bidirectional bubble sort) algorithm.

public void cocktailShakerSort(int[] arr) {
    // Your implementation here
    // Sort array using cocktail shaker approach
}

Hint: Traverse the array from left to right, then right to left, in each iteration.

Exercise 5: Count Swaps

Modify the bubble sort algorithm to count and return the number of swaps performed.

public int bubbleSortAndCountSwaps(int[] arr) {
    // Your implementation here
    // Return the number of swaps performed
}

Hint: This is useful to measure how "unsorted" an array is.