SortAlgorithms.java

import java.util.Scanner;


// The Strategy interface for the sorting algorithms.
interface SortingStrategy {
    // Defines a common method for all concrete sorting strategies.
    /**
     * Sorts the given array in ascending order.
     * @param array The integer array to be sorted.
     */
    void sort(int[] array);
}

/* Selected when the array length is less than 50.
 * Time Complexity: O(N) in the best case (when the array is already sorted), O(N^2) in the worst case (when the array is reverse sorted), and O(N^2) in the average case.
 */
class BubbleSort implements SortingStrategy {
    @Override
    public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // Compare elements and swap if they are in the wrong order.
                if (array[j] > array[j + 1]) {
                    SortAlgorithms.swap(array, j, j + 1);
                }
            }
        }
    }
}

/* Selected when the array is nearly sorted (inversions < n/10).
 * Time Complexity: O(N) in the best case (when the array is already sorted), O(N^2) in the worst case (when the array is reverse sorted), and O(N^2) in the average case.
 */
class InsertionSort implements SortingStrategy {
    @Override
    public void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                // While the left side is greater than the key, shift elements to the right.
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }
}

/* Selected when the array length is less than 10000 and other conditions are not met.
 * Time Complexity: O(N log N) in the best and average cases, and O(N^2) in the worst case (when the array is already sorted or reverse sorted).
 */
class QuickSort implements SortingStrategy {
    @Override
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public void quickSort(int[] arr, int low, int high) {
        if (low < high) { // Base case: if the array has more than one element
            // Partition the array and get the pivot index.
            int p = partition(arr, low, high);
            // Recursively sort elements after partition.
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    public int partition(int[] arr, int low, int high) {
        // Select the last element as pivot.
        int pivot = arr[high];
        int i = low - 1;
        // Rearrange elements based on the pivot.
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                SortAlgorithms.swap(arr, i, j);
            }
        }
        // Place the pivot in its correct position.
        SortAlgorithms.swap(arr, i + 1, high);
        return i + 1;
    }
}

/* Selected when the array length is greater than or equal to 10000.
 * Time Complexity: O(N log N) for all cases (Best, Average, Worst).
 */
class MergeSort implements SortingStrategy {
    @Override
    public void sort(int[] array) {
        // Build a temporary array for merging.
        int[] temp = new int[array.length];
        mergeSort(array, temp, 0, array.length - 1);
    }

    public void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) { // Base case: if the array has more than one element
            // Find the mid to divide the array into two halves.
            int mid = left + (right - left) / 2;
            // Recursively sort the first and second halves.
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);

            // If the largest element in the left half is less than or equal to the smallest element in the right half, skip merging.
            if (arr[mid] <= arr[mid + 1]) {
                return;
            }
            merge(arr, temp, left, mid, right);
        }
    }

    public void merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) { // None of the halves is fully traversed.
            if (arr[i] <= arr[j]) { // Put the smaller element into the temp array.
                temp[k] = arr[i];
                k++;
                i++;
            } else {
                temp[k] = arr[j];
                k++;
                j++;
            }
        }
        // Copy the remaining elements of the left half, if there are any.
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        // Copy the remaining elements of the right half, if there are any.
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        // Copy the sorted subarray into Original array.
        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
}

/* Selected when the difference between max and min values is less than 1000.
 * Time Complexity: O(N + K) where N is the number of elements in the input array and K is the range of the input (max - min).
 */
class CountingSort implements SortingStrategy {
    @Override
    public void sort(int[] array) {
        // Initilize the max and min values to find the range of the input data.
        int max = array[0];
        int min = array[0];
        int n = array.length;

        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        
        int range = max - min + 1;
        int[] count = new int[range];
        int[] sorted = new int[n];
        
        // Use an offset (array[i] - min) to safely handle negative integers.
        for (int i = 0; i < n; i++) {
            count[array[i] - min]++;
        }
        
        // Update the count array to store the cumulative count of each unique object.
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        
        // Build the output array by placing elements in their correct positions.
        for (int i = n - 1; i >= 0; i--) {
            sorted[count[array[i] - min] - 1] = array[i];
            count[array[i] - min]--;
        }
        
        // Copy the sorted elements back into the original array.
        for (int i = 0; i < n; i++) {
            array[i] = sorted[i];
        }
    }
}

// Maintains a reference to a SortingStrategy object and delegates the sorting execution.
class Sorter {
    private SortingStrategy strategy;

    public void setStrategy(SortingStrategy strategy) {
        this.strategy = strategy;
    }

    public void sortArray(int[] array) {
        if (this.strategy != null) {
            this.strategy.sort(array);
        }
    }
}

// Select the appropriate sorting algorithm based on the characteristics of the input data.
class StrategySelector {
    /**
     * Dynamically selects the best sorting strategy based on predefined rules.
     * * @param data The input array to be analyzed.
     * @return An instance of the optimally selected SortingStrategy.
     */
    public static SortingStrategy selectStrategy(int[] data) {
        int n = data.length;

        // Rule 1: Small arrays
        if (n < 50) {
            return new BubbleSort();
        } 
        // Rule 2: Nearly sorted arrays (inversions < n/10)
        else if (isNearlySorted(data)) {
            return new InsertionSort();
        } 
        // Rule 3: Small value range ((max - min) < 1000)
        else if (isSmallRange(data)) {
            return new CountingSort();
        } 
        // Rule 4: Medium arrays
        else if (n < 10000) {
            return new QuickSort();
        } 
        // Rule 5: Large arrays
        else {
            return new MergeSort();
        }
    }

    // Check if the array is nearly sorted by counting inversions.
    public static boolean isNearlySorted(int[] data) {
        int n = data.length;
        if (n <= 1) return true;
        
        int threshold = n / 10;
        int inversions = 0;
        
        // O(n^2)
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (data[i] > data[j]) {
                    inversions++;
                    // Early exit if the threshold is reached or exceeded.
                    if (inversions >= threshold) {
                        return false; 
                    }
                }
            }
        }
        return true;
    }

    // Check if the value range of the array is less than 1000.
    public static boolean isSmallRange(int[] data) {
        int min = data[0];
        int max = data[0];
        
        for (int i = 1; i < data.length; i++) {
            if (data[i] < min) min = data[i];
            if (data[i] > max) max = data[i];
        }
        
        // Cast to long to prevent overflow before subtraction
        long range = (long) max - (long) min;
        return range < 1000;
    }
}

// Reads input from System.in, delegates to the Sorter, and outputs to System.out.
public class SortAlgorithms {
    /**
     * Swaps two elements in the given integer array.
     *
     * @param array The array in which elements will be swapped.
     * @param i     The index of the first element.
     * @param j     The index of the second element.
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Check for true EOF. If there is no input, the program will print "Strategy: BubbleSort" and exit.
        if (scanner.hasNextLine()) {

            // Read the exact input line without trimming whitespace.
            String input = scanner.nextLine(); 
            
            // Split the input string and force the split method to include trailing empty strings. For example, "1,2," becomes ["1", "2", ""].
            String[] strArr = input.split(",", -1); 
            int[] data = new int[strArr.length];
            
            try {
                for (int i = 0; i < strArr.length; i++) {
                    // Parse each string to an integer. If any string is not a valid integer, a NumberFormatException will be thrown.
                    data[i] = Integer.parseInt(strArr[i]);
                }
            } catch (NumberFormatException e) {
                scanner.close();
                // DEFENSIVE PROGRAMMING: 
                // In a standard production environment, we would throw an IllegalArgumentException here.
                // However, to strictly comply with the coursework requirement of a "silent exit" 
                // upon encountering invalid inputs (e.g., spaces, letters, consecutive commas), 
                // we catch the exception and terminate the program gracefully with exit code 0.
                // throw new IllegalArgumentException("Invalid input: Must be 1,2,3,...");
                return;
            }

            // Select the appropriate sorting strategy based on the input data.
            SortingStrategy strategy = StrategySelector.selectStrategy(data);
            
            // Output the exact required format for the selected strategy.
            System.out.println("Strategy: " + strategy.getClass().getSimpleName());

            // Delegate the sorting task to the Context object.
            Sorter sorter = new Sorter();
            sorter.setStrategy(strategy);
            sorter.sortArray(data);

            // Print the sorted elements, one per line.
            for (int num : data) {
                System.out.println(num);
            }
        }
        // EOF
        else {
            System.out.println("Strategy: BubbleSort");
        }
        
        scanner.close();
    }
}