Master Bubble Sort - O(n²) Algorithm

function bubbleSort(arr, optimization = true) {
    /**
     * Bubble Sort with optional early exit optimization
     * Time: O(n²) average/worst, O(n) best with optimization
     * Space: O(1) - in-place sorting
     */
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        let swapped = false;

        // Inner loop: compare adjacent elements
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements using destructuring
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }

        // Early exit optimization
        if (optimization && !swapped) {
            break; // Array is sorted
        }
    }

    return arr;
}

// Usage examples
const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr1)); // [11, 12, 22, 25, 34, 64, 90]

// Best case with optimization
const arr2 = [1, 2, 3, 4, 5];
console.log(bubbleSort(arr2)); // O(n) - already sorted

package main

import "fmt"

// BubbleSort sorts an array using bubble sort algorithm
// Time: O(n²) average/worst, O(n) best with optimization
// Space: O(1) - in-place sorting
func BubbleSort(arr []int, optimization bool) []int {
    n := len(arr)

    for i := 0; i < n-1; i++ {
        swapped := false

        // Inner loop: compare adjacent elements
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                // Swap elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }

        // Early exit optimization
        if optimization && !swapped {
            break // Array is sorted
        }
    }

    return arr
}

func main() {
    // Usage examples
    arr1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println(BubbleSort(arr1, true))
    // Output: [11 12 22 25 34 64 90]

    // Best case with optimization
    arr2 := []int{1, 2, 3, 4, 5}
    fmt.Println(BubbleSort(arr2, true))
    // O(n) - already sorted
}

public class BubbleSort {
    /**
     * Bubble Sort with optional early exit optimization
     * Time: O(n²) average/worst, O(n) best with optimization
     * Space: O(1) - in-place sorting
     */
    public static void bubbleSort(int[] arr, boolean optimization) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

            // Inner loop: compare adjacent elements
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // Early exit optimization
            if (optimization && !swapped) {
                break; // Array is sorted
            }
        }
    }

    public static void main(String[] args) {
        // Usage examples
        int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr1, true);
        System.out.println(Arrays.toString(arr1));
        // Output: [11, 12, 22, 25, 34, 64, 90]

        // Best case with optimization
        int[] arr2 = {1, 2, 3, 4, 5};
        bubbleSort(arr2, true);
        // O(n) - already sorted
    }
}

#include <iostream>
#include <vector>
using namespace std;

/**
 * Bubble Sort with optional early exit optimization
 * Time: O(n²) average/worst, O(n) best with optimization
 * Space: O(1) - in-place sorting
 */
void bubbleSort(vector<int>& arr, bool optimization = true) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;

        // Inner loop: compare adjacent elements
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }

        // Early exit optimization
        if (optimization && !swapped) {
            break; // Array is sorted
        }
    }
}

int main() {
    // Usage examples
    vector<int> arr1 = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr1);

    for (int num : arr1) {
        cout << num << " ";
    }
    // Output: 11 12 22 25 34 64 90

    return 0;
}