AlternateTimeOptimalSorting.java

import java.util.Scanner;

public class AlternateTimeOptimalSorting {

    static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

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

    static int minimum(int a, int b) {
        return a < b ? a : b;
    }

    static int maximum(int a, int b) {
        return a > b ? a : b;
    }

    static int send(int[] arr, int index) {
        return arr[index];
    }

    static void receive(int[] arr, int index, int value) {
        arr[index] = value;
    }

    static void compute(int[] arr, int n, int center) {
        if (center - 1 < 0) {
            int receivedRight = send(arr, center + 1);
            if (arr[center] > receivedRight) {
                swap(arr, center, center + 1);
            }
        } else if (center + 1 >= n) {
            int receivedLeft = send(arr, center - 1);
            if (arr[center] < receivedLeft) {
                swap(arr, center, center - 1);
            }
        }
        else {
            int left = send(arr, center - 1);
            int right = send(arr, center + 1);
            int current = send(arr, center);

            int minValue = minimum(current, minimum(left, right));
            int maxValue = maximum(current, maximum(left, right));
            int midValue = current + left + right - minValue - maxValue;

            receive(arr, center - 1, minValue);
            receive(arr, center + 1, maxValue);
            receive(arr, center, midValue);
        }
    }

    static void alternateTimeOptimalSorting(int[] arr, int n) {
        for (int i = 1; i < n; i++) {
            int remainder = (i + 1) % 3;
            int j;
            if (remainder == 0) {
                j = 2;
            } else if (remainder == 1) {
                j = 0;
            } else {
                j = 1;
            }

            while (j < n) {
                compute(arr, n, j);
                j += 3;
            }

            System.out.println("Step " + i + ":");
            printArray(arr);
        }
    }

    public static void main(String[] args) {
        // Input
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of elements in your sequence:");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter your sequence:");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        long startTime = System.currentTimeMillis();
        alternateTimeOptimalSorting(arr, n);

        System.out.println("By alternate time optimal sorting method, the sorted sequence is:");
        printArray(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("Execution time: " + (endTime - startTime) + " ms");

        sc.close();
    }
}