Master Selection Sort - O(n²) Algorithm

function selectionSort(arr) {
    /**
     * Selection Sort - finds minimum and swaps to correct position
     * Time: O(n²) all cases - no optimization possible
     * Space: O(1) - in-place sorting
     */
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        // Find minimum element in unsorted region
        let minIdx = i;

        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        // Swap minimum with first unsorted element
        if (minIdx !== i) {
            [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
        }
    }

    return arr;
}

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

// Already sorted - still O(n²)
const arr2 = [1, 2, 3, 4, 5];
console.log(selectionSort(arr2)); // No optimization - always n(n-1)/2 comparisons

package main

import "fmt"

// SelectionSort sorts an array using selection sort algorithm
// Time: O(n²) all cases - no optimization possible
// Space: O(1) - in-place sorting
func SelectionSort(arr []int) []int {
    n := len(arr)

    for i := 0; i < n-1; i++ {
        // Find minimum element in unsorted region
        minIdx := i

        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }

        // Swap minimum with first unsorted element
        if minIdx != i {
            arr[i], arr[minIdx] = arr[minIdx], arr[i]
        }
    }

    return arr
}

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

    // Already sorted - still O(n²)
    arr2 := []int{1, 2, 3, 4, 5}
    fmt.Println(SelectionSort(arr2))
    // No optimization - always n(n-1)/2 comparisons
}

public class SelectionSort {
    /**
     * Selection Sort - finds minimum and swaps to correct position
     * Time: O(n²) all cases - no optimization possible
     * Space: O(1) - in-place sorting
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            // Find minimum element in unsorted region
            int minIdx = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            // Swap minimum with first unsorted element
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
            }
        }
    }

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

        // Already sorted - still O(n²)
        int[] arr2 = {1, 2, 3, 4, 5};
        selectionSort(arr2);
        // No optimization - always n(n-1)/2 comparisons
    }
}

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

/**
 * Selection Sort - finds minimum and swaps to correct position
 * Time: O(n²) all cases - no optimization possible
 * Space: O(1) - in-place sorting
 */
void selectionSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        // Find minimum element in unsorted region
        int minIdx = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        // Swap minimum with first unsorted element
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

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

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

    return 0;
}