OddEvenTranspositionSort.java

import java.util.*;

public class OddEvenTranspositionSort {

    static class Process {
        int id;
        int value;
        Integer buffer = null;

        Process(int id, int value) {
            this.id = id;
            this.value = value;
        }

        void send(Process neighbor) {
            neighbor.buffer = this.value;
        }

        int receive() {
            return this.buffer;
        }

        void compute(boolean isLeft, Process neighbor) {
            if (buffer != null) {
                if (isLeft && buffer > this.value) {
                    int temp = this.value;
                    this.value = buffer;
                    neighbor.value = temp;
                } else if (!isLeft && buffer < this.value) {
                    int temp = this.value;
                    this.value = buffer;
                    neighbor.value = temp;
                }
            }
            this.buffer = null;
        }
    }

    static void oddEvenSort(int[] arr) {
        int n = arr.length;
        Process[] processes = new Process[n];

        for (int i = 0; i < n; i++) {
            processes[i] = new Process(i, arr[i]);
        }

        System.out.println("Initial State:");
        printState(processes);

        for (int step = 1; step <= n; step++) {
            System.out.println("Step " + step + (step % 2 == 1 ? " (Odd Phase):" : " (Even Phase):"));

            if (step % 2 == 1) {
                for (int i = 0; i + 1 < n; i += 2) {
                    processes[i].send(processes[i + 1]);
                }
                for (int i = 0; i + 1 < n; i += 2) {
                    processes[i + 1].compute(true, processes[i]);
                }
            } else {
                for (int i = 1; i + 1 < n; i += 2) {
                    processes[i].send(processes[i + 1]);
                }
                for (int i = 1; i + 1 < n; i += 2) {
                    processes[i + 1].compute(true, processes[i]);
                }
            }

            printState(processes);
        }

        System.out.println("Final Sorted Sequence:");
        for (Process p : processes) {
            System.out.print(p.value + " ");
        }
        System.out.println();
    }

    static void printState(Process[] processes) {
        for (Process p : processes) {
            System.out.print(p.value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of elements:");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        long startTime = System.currentTimeMillis();
        oddEvenSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("Execution time: " + (endTime - startTime) + " ms");

        sc.close();
    }
}