Array Partitioning : Java Program for Hoare Partition

 

Java Program for Hoare Partition

 

public class HoarePartitionExample {

 

    static int partition(int[] arr, int low, int high) {

 

        int pivot = arr[low];

 

        int i = low - 1;

        int j = high + 1;

 

        while (true) {

 

            // Move i from left to right

            do {

                i++;

            } while (arr[i] < pivot);

 

 

            // Move j from right to left

            do {

                j--;

            } while (arr[j] > pivot);

 

 

            // If pointers cross

            if (i >= j) {

                return j;

            }

 

 

            // Swap arr[i] and arr[j]

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

    }

 

 

    public static void main(String[] args) {

 

        int[] arr = {10, 16, 8, 12, 15, 6, 3, 9, 5};

 

        System.out.println("Before Partition:");

 

        for (int value : arr) {

            System.out.print(value + " ");

        }

 

        int partitionIndex = partition(arr, 0, arr.length - 1);

 

        System.out.println("\n\nAfter Partition:");

 

        for (int value : arr) {

            System.out.print(value + " ");

        }

 

        System.out.println("\n\nPartition Index: " + partitionIndex);

    }

}

 

Output

Before Partition:

10 16 8 12 15 6 3 9 5

 

After Partition:

5 3 8 9 6 15 12 16 10

 

Partition Index: 4