The classic algorithmic technique used in array manipulation and sorting problems where a pivot element is involved is 3-way partitioning. The main objective is to reorder the array such that it is divided into three distinct parts based on a specified pivot value:
- Elements less than the pivot: The array elements are at the beginning of the array.
- Elements equal to the pivot: The groups of these are located in the middle.
- Elements greater than the pivot: They are placed near the end of the array.
When we want to find the array with duplicate values, this method works faster with additional iterations. We use it in many algorithms, like the QuickSort or Dutch National Flag problem, where sorting and rearrangement are required by comparing or according to a pivot or specific criteria.
Use Cases
Three-way partitioning addresses a common limitation in traditional two-way partitioning techniques, which split the array only into two parts: the elements lesser than and greater than the pivot. Two-way partitioning on arrays with a large number of elements equal to the pivot may require unnecessary comparisons and swaps, which makes the overall partitioning inefficient. The approach of three-way partitioning explicitly handling the pivot elements minimizes these redundant operations and improves performance.
This technique is particularly beneficial in problems where:
- The array contains many duplicate elements that are being processed only once from the perspective of performance.
- As an example, we want to sort elements based on three categories: sort the array of 0s, 1s, 2s etc.
- To solve this problem, linear time complexity (O(n)) and minimum space complexity (O(1) additional space) are required.
Key Concepts:
The three-way partitioning algorithm uses three-pointers, low, mid, and high, to efficiently segment an array in a single pass. This technique divides the array into three segments relative to a pivot element: less than, equal to, or greater than the pivot. Low tracks the boundary of the less-than-pivot region, mid scans the current element being tested, and high marks the greater-than-pivot boundary.
The algorithm is single-pass and runs in O(n) time and O(1) space, which serves it well for in-place rearrangement. It solves the Dutch National Flag problem, optimized versions of QuickSort, and excels when the arrays contain duplicates. Overall, three-way partitioning is a powerful tool for array manipulation and provides a very versatile means for systematic, straightforward sorting in many applications.
Approach-1: Brute Force Approach
A brute force approach is an obvious way to three-way partition, i.e., multiple passes through the array to classify elements based on a pivot. Its additional space requirement and ease of implementation make this method easy to implement but not efficient.
The final thing is to concatenate the three segments into a new array. The brute force approach ensures proper partitioning but carries the huge disadvantage of requiring extra memory (O(n) space complexity), and a necessity of several passes (O(n) time complexity).
Example:
Let us take an example to illustrate the Three-way partitioning around an element in C++ using brute force approach.
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
//Function to print the array
void printArray(const vector<int>& arr, const string& message) {
cout << message << ": ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
//Function to get user input for the array
vector<int> getUserInput() {
vector<int> arr;
string input;
cout << "Enter the elements of the array (space-separated integers): ";
getline(cin, input);
stringstream ss(input);
int num;
// Read integers from the input string
while (ss >> num) {
arr.push_back(num);
}
return arr;
}
//Function to get pivot input from the user
int getPivot() {
int pivot;
cout << "Enter the pivot element: ";
cin >> pivot;
return pivot;
}
// Brute force function to partition the array
vector<int> threeWayPartitionBruteForce(const vector<int>& arr, int pivot) {
vector<int> lessThanPivot;
vector<int> equalToPivot;
vector<int> greaterThanPivot;
// First pass: Collect elements less than the pivot
for (int num : arr) {
if (num < pivot) {
lessThanPivot.push_back(num);
}
}
// Second pass: Collect elements equal to the pivot
for (int num : arr) {
if (num == pivot) {
equalToPivot.push_back(num);
}
}
// Third pass: Collect elements greater than the pivot
for (int num : arr) {
if (num > pivot) {
greaterThanPivot.push_back(num);
}
}
// Print intermediate results
printArray(lessThanPivot, "Elements less than pivot");
printArray(equalToPivot, "Elements equal to pivot");
printArray(greaterThanPivot, "Elements greater than pivot");
// Concatenate all three parts
vector<int> result;
// Add less than pivot elements
for (int num : lessThanPivot) {
result.push_back(num);
}
// Add equal to pivot elements
for (int num : equalToPivot) {
result.push_back(num);
}
// Add greater than pivot elements
for (int num : greaterThanPivot) {
result.push_back(num);
}
return result;
}
// Function to validate the input array
bool validateArray(const vector<int>& arr) {
if (arr.empty()) {
cout << "Error: The array is empty. Please provide valid input." << endl;
return false;
}
return true;
}
//Function to validate the pivot value
bool validatePivot(int pivot, const vector<int>& arr) {
bool found = false;
for (int num : arr) {
if (num == pivot) {
found = true;
break;
}
}
if (!found) {
cout << "Warning: The pivot element is not present in the array." << endl;
}
return true;
}
// Main Function
int main() {
cout << "Three-Way Partitioning (Brute Force Approach)" << endl;
// Get user input for the array
vector<int> arr = getUserInput();
// Validate the input array
if (!validateArray(arr)) {
return 1; // Exit if the array is invalid
}
// Get the pivot value from the user
int pivot = getPivot();
// Validate the pivot value
validatePivot(pivot, arr);
// Print the original array
printArray(arr, "Original array");
// Perform three-way partitioning using brute force approach
vector<int> partitionedArray = threeWayPartitionBruteForce(arr, pivot);
// Print the partitioned array
printArray(partitionedArray, "Partitioned array");
cout << "Partitioning Complete " << endl;
return 0;
}
Output:
Three-Way Partitioning (Brute Force Approach)
Enter the elements of the array (space-separated integers): 2 3 7 45 6 23 43 68 94 57
Enter the pivot element: 43
Original array: 2 3 7 45 6 23 43 68 94 57
Elements less than pivot: 2 3 7 6 23
Elements equal to pivot: 43
Elements greater than pivot: 45 68 94 57
Partitioned array: 2 3 7 6 23 43 45 68 94 57
Partitioning Complete
Explanation:
Input Handling:
- The function calls to read the elements of the array is done by the function getUserInput. The getline function grabs the whole input as a string, and then a stringstream parses the string into individual integers. These integers are added to a vector array that is used to store the array elements.
- The first part, the getPivot function asks the user to input a pivot element, which is the reference value around that the partitioning will take place.
Validation:
- Before proceeding, the validateArray function checks if the array is empty. In case the array is empty, the program issues an error message and stops (early) the whole program when trying to work with invalid input.
- The validatePivot function ensures that the pivot element is also present in the array. If it is not found, it issues a warning and continues to run, giving flexibility in handling edge cases where the pivot is not present.
Partitioning Logic:
The main part of the algorithm is the threeWayPartitionBruteForce function . It performs the actual partitioning by iterating over the array three times:
- First pass: The pivot is the vector into which it collects all the elements less than the pivot.
- Second pass: In the second pass, parties collect all elements equal to the pivot into equalToPivot
- Third pass: All elements greater than the pivot form greaterThanPivot function.
- After collecting the elements into the three separate vectors, these vectors are concatenated in the order Pivot Operations: The lessThanPivot, equalToPivot, and greaterThanPivot. The pivot element surrounds a new array with its elements properly partitioned around the pivot.
- The program prints the three segments of the partitioned array. It tells us how the array was rearranged into elements less than, equal to, and greater than the pivot.
- Finally, the printed-out partitioned array is complete.
- The idea is to reorder the array so that all elements less than the pivot come in front, all elements equal to the pivot come next, and all elements greater than that come next. The above process involves collecting elements in different groups into three separate passes through the array.
- The brute force approach is simple to understand and implement. Nevertheless, the above approach is not the most efficient, particularly for large datasets, because of space overhead requirements and multiple linear sittings on the array.
Complexity Analysis:
Time Complexity:
The number of operations performed on the array during the partitioning process drives the time complexity:
- First pass: The first pass in which we fetch elements less than the pivot. Time complexity: O(n), where n is the number of elements of our array.
- Second pass: Again, the elements on the right of the array are traversed to collect elements that are equal to the pivot. It also takes O(n) time.
- Third pass: The pivot is used to make the appearance of a pivot in the array, which is traversed once more to gather elements greater than the pivot. It again takes O(n) time.
Since all three passes are independent, the total time complexity is the sum of these individual passes:
- The complexity of Total Time Complexity will be O(n) + O(n) + O(n) = O(3n) = O(n).
- It means that the brute force approach's number of comparisons (time complexity) is O(n), where n is an array index. Big O ignores the constant factor of 3.
Space Complexity:
The space complexity is determined by the additional space used to store the partitioned segments:
- We create three separate vectors to store less than, equal to, and greater than elements than the pivot. The worst case for each vector is to store up to n elements, which makes its total space proportional to the size of the array.
- Therefore, it is space of O(n) because three new vectors get created and their space consumption scales with respect to the size of the input.
Approach-2: Two-Pass In-Place Partitioning
Two-pass partitioning with in-place swaps is another method of three-way partitioning around a pivot. Although slower than the Dutch National Flag algorithm in runtime, this method is faster than brute force in terms of space because it uses only a constant amount of extra space.
This approach operates in two passes over the array:
- First Pass: The first pass moves all elements smaller than the pivot to the left side of the array and all the elements greater than the pivot to the right side. It does this in place, but it doesn't handle the elements equal to the pivot.
- Second Pass: Elements equal to the pivot will be taken care of in the second pass so that they are placed between smaller and larger elements.
- First pass: Sort the array according to the pivot, then partition the array into two parts: elements less than the pivot and elements greater than or equal to the pivot.
Steps:
Avoid using two or more pointers to access the array elements. Compare the pivot element with the array elements and swap it with the elements to the left side of the array if it is less than they are.
- Second pass: After the first pass, we can still have elements in the first array that are more than the pivot on the left side and elements in the second array that are less than the pivot on the right side. In this pass, we move all equal elements to the middle.
- Final Arrangement: After both passes, the array is partitioned by elements less than the pivot on the left, equal elements in the middle, and greater elements on the right.
Example:
Let us take an example to illustrate the Three-way partitioning around an element in C++ using two-pass in-place partitioning approach.
#include <iostream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;
//Function to print the array
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
//Function to get input from the user and convert it into a vector of integers
vector<int> getUserInput() {
string input;
vector<int> arr;
//Loop until we get a valid array input
while (true) {
cout << "Enter elements of the array (space-separated): ";
getline(cin, input);
// Check if the input is empty (only spaces or no input)
if (input.empty()) {
cout << "Error: The array cannot be empty. Please enter valid elements." << endl;
continue; // Ask the user to try again
}
// Use stringstream to extract integers from the input string
stringstream ss(input);
int num;
bool validInput = false;
// Try extracting integers from the input string
while (ss >> num) {
arr.push_back(num);
validInput = true;
}
// If no valid numbers were entered
if (!validInput) {
cout << "Error: No valid integers entered. Please enter valid elements." << endl;
continue; // Ask the user to try again
}
// If valid integers were found, break out of the Loop
break;
}
return arr;
}
//Function to validate the pivot (check if pivot exists in the array)
bool validatePivot(const vector<int>& arr, int pivot) {
for (int elem : arr) {
if (elem == pivot) {
return true;
}
}
return false;
}
//Function to get the pivot from the user
int getPivot(const vector<int>& arr) {
int pivot;
cout << "Enter the pivot element: ";
cin >> pivot;
// Check if a pivot exists in the array
if (!validatePivot(arr, pivot)) {
cout << "Warning: Pivot element is not in the array!" << endl;
}
return pivot;
}
//Function for two-pass partitioning around the pivot
void twoPassPartition(vector<int>& arr, int pivot) {
int n = arr.size();
// First pass: Move elements less than pivot to the left side and elements greater to the right
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (arr[j] < pivot) {
// Swap arr[i] and arr[j], increment i and j
swap(arr[i], arr[j]);
i++;
j++;
} else if (arr[j] == pivot) {
// No action needed, just increment j
j++;
} else {
// Swap arr[j] and arr[k], decrement k
swap(arr[j], arr[k]);
k--;
}
}
// Second pass: Check if the pivot needs to be handled specifically (optional step)
// This ensures that the partitioning is maintained with the pivot placed correctly
// but it's not strictly needed if the array is partitioned correctly in the first pass.
}
// Main Function to drive the logic
int main() {
// Step 1: Get array input from the user
vector<int> arr = getUserInput();
// Step 2: Ensure the array is not empty
if (arr.empty()) {
cout << "Error: The array cannot be empty." << endl;
return 1; // Exit the program if the array is empty
}
// Step 3: Get a pivot from the user
int pivot = getPivot(arr);
// Step 4: Perform two-pass partitioning around the pivot
twoPassPartition(arr, pivot);
// Step 5: Output the partitioned array
cout << "Partitioned array: ";
printArray(arr);
return 0;
}
Output:
Enter elements of the array (space-separated): 12 32 84 64 56 89 23 42
Enter the pivot element: 23
Partitioned array: 12 23 64 56 89 84 42 32
Explanation:
Input Handling:
Here, the user input is prompted to be a space-separated list of integers. It validates the input on nonempty and valid integers. It asks the user for good data if the data entered is invalid.
Pivot Validation:
Finally, the program collects the array and asks the user to input a pivot element. It first checks if the pivot is in the array. It goes ahead if the pivot isn't found, and it warns us.
Partitioning Logic:
The array is partitioned in two passes:
- The first pass through the elements would move elements less than the pivot to the left, elements equal to the pivot to the middle, and elements greater than the pivot to the right.
- The second pass only makes sure the pivocpp tutorials are in between the smaller and larger values.
Now, partition down to give the pivot elements between elements smaller and larger than the pivot, and then print the array.
Complexity Analysis:
Time Complexity:
- Input Parsing: This program loops through input and then turns it into integers via a stringstream. The time complexity of this is O(n) in terms of the number of elements in the array.
- Pivot Validation: Picking the pivot takes O(1) time, but it is checked in O(n) time whether it exists in the array.
- Partitioning: The partitioning algorithm takes O (n) time because it performs two sequential scans in the two-pass partitioning step.
- Therefore, the algorithm's total time complexity is O(n).
Space Complexity:
- In fact, the program uses another array to store the input integers, and it takes O(n) space.
- As such, it needs no additional space beyond this, which makes it O(n).