How Selection Sort Works:

1. Identify Minimum Value: Locate the minimum value within the unsorted portion.
2. Swap Elements: Exchange this minimum value with the first unsorted element.
3. Shift Boundary: Progressively move the boundary towards the end, repeating steps 1 and 2 until completion.

Advantages and Disadvantages of Selection Sort:

Advantages:

• Simple implementation and easy comprehension.
• In-place sorting without additional memory requirements.

Disadvantages:

• Higher time complexity, O(n²), making it unsuitable for large datasets.
• Unstable sorting method which can alter the order of equal elements.

Java Implementation of Selection Sort:

public class ArraySorter {
    public void sortArray(int[] data) {
        if (data == null || data.length == 0) return;
        for (int i = 0; i < data.length - 1; i++) {
            int minPos = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minPos]) minPos = j;
            }
            if (minPos != i) swapElements(data, i, minPos);
        }
    }

    private void swapElements(int[] data, int x, int y) {
        int temp = data[x];
        data[x] = data[y];
        data[y] = temp;
    }

    public static void main(String[] args) {
        ArraySorter sorter = new ArraySorter();
        int[] data = {64, 25, 12, 22, 11};
        sorter.sortArray(data);
        System.out.println("Sorted array: " + java.util.Arrays.toString(data));
    }
}

Interview Questions Related to Selecsion Sort:

Problem 1: Find the Kth Largest Element in an Array

Description: Given an unsorted integer array and an integer k, find the k-th largest element.

public class KthElementFinder {
    public int getKthLargest(int[] values, int k) {
        java.util.Arrays.sort(values);
        return values[values.length - k];
    }

    public static void main(String[] args) {
        KthElementFinder finder = new KthElementFinder();
        int[] values = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = finder.getKthLargest(values, k);
        System.out.println("The 2nd largest element is: " + result);
    }
}

Problem 2: Smallest Subarray Sum

Description: Given an array of integers, identify a contiguous subarray with the minimum sum.

public class MinSubarrayCalculator {
    public int calculateMinSum(int[] nums) {
        int currentMin = Integer.MAX_VALUE, currentSum = 0;
        for (int num : nums) {
            currentSum += num;
            currentMin = Math.min(currentMin, currentSum);
        }
        return currentMin;
    }

    public static void main(String[] args) {
        MinSubarrayCalculator calc = new MinSubarrayCalculator();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = calc.calculateMinSum(nums);
        System.out.println("Minimum subarray sum is: " + result);
    }
}

Problem 3: First Missing Positive Number

Description: Given an unsorted integer array, find the smallest missing positive number.

public class MissingPositiveFinder {
    public int findMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }

    public static void main(String[] args) {
        MissingPositiveFinder finder = new MissingPositiveFinder();
        int[] nums = {1, 2, 0};
        int result = finder.findMissingPositive(nums);
        System.out.println("First missing positive number is: " + result);
    }
}