Selection Sort

Definition

A comparison-based sorting algorithm that divides the array into sorted and unsorted regions, repeatedly selecting the minimum element from unsorted and placing it at the end of the sorted region.

Key Insight: After i iterations, first i elements are in their final sorted position.

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

Basic Selection Sort

public void selectionSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        // Find minimum in unsorted region [i, n-1]
        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;
        }
    }
}

Optimized: Find Min and Max Together

// Reduces passes by finding both min and max
public void selectionSortOptimized(int[] arr) {
    int left = 0;
    int right = arr.length - 1;

    while (left < right) {
        int minIdx = left;
        int maxIdx = left;

        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIdx]) minIdx = i;
            if (arr[i] > arr[maxIdx]) maxIdx = i;
        }

        // Swap minimum to left
        swap(arr, left, minIdx);

        // If max was at left, it moved to minIdx
        if (maxIdx == left) maxIdx = minIdx;

        // Swap maximum to right
        swap(arr, right, maxIdx);

        left++;
        right--;
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Stable Selection Sort

// Uses shifting instead of swapping to maintain stability
public void stableSelectionSort(int[] arr) {
    int n = arr.length;

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

        // Shift elements right instead of swapping
        int min = arr[minIdx];
        while (minIdx > i) {
            arr[minIdx] = arr[minIdx - 1];
            minIdx--;
        }
        arr[i] = min;
    }
}

Descending Order

public void selectionSortDescending(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        int maxIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[maxIdx]) {
                maxIdx = j;
            }
        }

        if (maxIdx != i) {
            int temp = arr[i];
            arr[i] = arr[maxIdx];
            arr[maxIdx] = temp;
        }
    }
}

Recursive Selection Sort

public void selectionSortRecursive(int[] arr, int start) {
    if (start >= arr.length - 1) return;

    int minIdx = start;
    for (int i = start + 1; i < arr.length; i++) {
        if (arr[i] < arr[minIdx]) {
            minIdx = i;
        }
    }

    if (minIdx != start) {
        int temp = arr[start];
        arr[start] = arr[minIdx];
        arr[minIdx] = temp;
    }

    selectionSortRecursive(arr, start + 1);
}

Generic Selection Sort

public <T extends Comparable<T>> void selectionSort(T[] arr) {
    int n = arr.length;

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

        if (minIdx != i) {
            T temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

---

Step-by-Step Example

---

Variations

Partial Selection Sort (Find k smallest)

// Sort only first k elements
// Time: O(k × n) instead of O(n²)
public void partialSelectionSort(int[] arr, int k) {
    int n = arr.length;
    k = Math.min(k, n);

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

        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

Selection Sort for Linked List

public ListNode selectionSort(ListNode head) {
    if (head == null) return null;

    ListNode sorted = null;
    ListNode current = head;

    while (current != null) {
        // Find minimum in remaining list
        ListNode min = current;
        ListNode prev = current;
        ListNode minPrev = null;

        while (prev.next != null) {
            if (prev.next.val < min.val) {
                min = prev.next;
                minPrev = prev;
            }
            prev = prev.next;
        }

        // Remove min from current list
        if (min == current) {
            current = current.next;
        } else {
            minPrev.next = min.next;
        }

        // Add min to sorted list
        min.next = sorted;
        sorted = min;
    }

    return sorted;
}

---

Why Selection Sort is Unstable

---

Tips & Tricks

---