Three-Way Partition Problem in Java
A variant of the traditional partition problem in computer science and algorithms is the Three-Way Partition Problem in Java. Dividing a set of items into two subsets to get the sum of their weights or values as close as possible is known as the partition problem. The concept is extended by the Three-Way Partition Problem, which splits it into three subsets.
The objective of the Three-Way Partition Problem is to partition an array of elements into three segments according to a given criterion. Typically, we work with an array of elements. Three parts which have been included are :
1. Elements below a designated threshold (pivot).
2. Pivot elements, which have the designated value.
3. Components that exceed the designated threshold (pivot).
Example 1:
Input: Array: [4, 3, 5, 2, 1, 6], Pivot: 3
Output: [2, 1, 3, 4, 5, 6]
Example 2:
Input: Array: [9, 5, 7, 4, 5, 3, 8], Pivot: 5
Output: [4, 3, 5, 5, 7, 9, 8]
Approach: Dutch National Flag Algorithm
The Three-Way Partition Problem can be effectively solved using the Dutch National Flag algorithm. The goal is to navigate the array with three-pointers—low, mid, and high. For elements that are less than, equal to, and greater than the pivot, respectively, these pointers indicate their current positions.
Here is the implementation of the Dutch national flag approach:
FileName: DutchNationalFlag.java
public class DutchNationalFlag {
public static void threeWayPartition(int[] arr, int lowValue, int highValue) {
int n = arr.length;
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
// If the current element is less than the lowValue, swap it with the element at the low pointer
if (arr[mid] < lowValue) {
swap(arr, low, mid);
low++;
mid++;
}
// If the current element is within the range of lowValue and highValue, move the mid pointer
else if (arr[mid] >= lowValue && arr[mid] <= highValue) {
mid++;
}
// If the current element is greater than the highValue, swap it with the element at the high pointer
else {
swap(arr, mid, high);
high--;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String args[]) {
int[] arr = {1, 9, 5, 4, 2, 7, 3, 8, 6};
int lowValue = 4;
int highValue = 7;
System.out.println("Original array:");
printArray(arr);
threeWayPartition(arr, lowValue, highValue);
System.out.println("Array after three-way partitioning:");
printArray(arr);
}
}
Output:
Original array:
1 9 5 4 2 7 3 8 6
Array after three-way partitioning:
1 2 3 4 6 7 5 8 9
Complexity analysis: The Dutch National Flag algorithm processes every element in the array in a single pass, giving it an O(n) time complexity. Since the algorithm only needs a fixed number of pointers to partition, it operates in constant space, or O(1). The method effectively solves the Three-Way Partition Problem through in-place sorting.
Approach: Quick Sort
The QuickSort algorithm sorts an array using a divide-and-conquer technique. By adding a three-way partitioning scheme during QuickSort's partition step, it can be modified to effectively solve the Three-Way Partition Problem. When an array contains duplicate elements, this method aids in performance optimization.
Here is the implementation of the Quick Sort approach:
FileName: QuickSortThreeWayPartition.java
public class QuickSortThreeWayPartition {
public static void quickSort(int[] arr, int low, int high) {
// If the low index is less than the high index, continue partitioning
if (low < high) {
// Perform three-way partitioning and recursively call QuickSort on the partitions
int[] pivotIndices = threeWayPartition(arr, low, high);
quickSort(arr, low, pivotIndices[0] - 1);
quickSort(arr, pivotIndices[1] + 1, high);
}
}
private static int[] threeWayPartition(int[] arr, int low, int high) {
int pivot = arr[low];
int lowIndex = low;
int highIndex = high;
int i = low + 1;
while (i <= highIndex) {
// Compare the current element with the pivot and perform swaps accordingly
if (arr[i] < pivot) {
swap(arr, i, lowIndex);
i++;
lowIndex++;
} else if (arr[i] > pivot) {
swap(arr, i, highIndex);
highIndex--;
} else {
i++;
}
}
return new int[]{lowIndex, highIndex};
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String args[]) {
int[] arr = {1, 9, 5, 4, 2, 7, 3, 8, 6};
int low = 0;
int high = arr.length - 1;
System.out.println("Original array:");
printArray(arr);
// Perform QuickSort using three-way partitioning
quickSort(arr, low, high);
System.out.println("Array after three-way partitioning using QuickSort:");
printArray(arr);
}
}
Output:
Original array:
1 9 5 4 2 7 3 8 6
Array after three-way partitioning using QuickSort:
1 2 3 4 5 6 7 8 9
Complexity analysis: The average-case time complexity and space complexity of the QuickSort method with three-way partitioning for the Three-Way Partition Problem are O(n log n) and O(log n), respectively. Its performance is especially effective in the presence of duplicate elements because it decreases QuickSort's worst-case behavior and provides faster than average time complexity in such circumstances.