Definition and Approach

Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. This process continues until the entire array is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the array, similar to how bubbles rise in water.

The basic idea is to iterate through the array multiple times, comparing each pair of adjacent elements. During each pass, the largest unsorted element "bubbles up" to its correct posision at the end of the array.

Implementation Example

import java.util.Arrays;

public class SortingAlgorithms {
    public static void bubbleSort(int[] data) {
        int n = data.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    // Swap elements
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no elements were swapped, array is already sorted
            if (!swapped) {
                break;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 40};
        bubbleSort(numbers);
        System.out.println(Arrays.toString(numbers));
    }
}

Algorithm Analysis

• Time Complexity: O(n²) in worst and average cases, O(n) in best case
• Space Complexity: O(1)
• Stability: Stable
• Optimization: Early termination when no swaps occur in a pass

Quick Sort

Definition and Approach

Quick sort is an efficient divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element and partitioning the array around this pivot, such that elements smaller than the pivot are on the left and elements larger are on the right. The process is then recursively applied to the sub-arrays.

Unlike bubble sort where elements move only one position at a time, quick sort can move elements across larger distances in a single operation, making it significantly faster for larger datasets.

Implementation Example

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5};
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

Alternative Partitioning Methods

// Hoare partition scheme
private static int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        
        do {
            j--;
        } while (arr[j] > pivot);
        
        if (i >= j) {
            return j;
        }
        
        swap(arr, i, j);
    }
}

// Three-way partitioning
private static void threeWayQuickSort(int[] arr, int low, int high) {
    if (high <= low) return;
    
    int lt = low;
    int gt = high;
    int pivot = arr[low];
    int i = low;
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt++, i++);
        } else if (arr[i] > pivot) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

Algorithm Anaylsis

• Time Complexity: O(n log n) in average and best cases, O(n²) in worst case
• Space Complexity: O(log n) in average case, O(n) in worst case
• Stability: Not stable (by default implemantation)