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 seeking an array containing duplicate values, this approach proves more efficient with increased iterations. It finds application in numerous algorithms such as QuickSort or the Dutch National Flag problem, where sorting and reorganizing are necessary based on comparisons or specific criteria like a pivot.
Use Cases
Three-way partitioning is a technique that overcomes a drawback present in conventional two-way partitioning methods. The latter divides the array into only two sections: those smaller and larger than the pivot. When dealing with arrays containing numerous elements equal to the pivot, two-way partitioning can lead to redundant comparisons and swaps, resulting in suboptimal partitioning efficiency. In contrast, three-way partitioning explicitly manages the pivot elements, reducing unnecessary operations and enhancing the overall performance of the partitioning process.
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-partition algorithm employs three pointers, specifically low, mid, and high, to effectively divide an array in one go. This method categorizes the array into three parts based on a pivot element: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. Low indicates the end of the section with elements less than the pivot, mid examines the current element under evaluation, and high denotes the end of the section with elements greater than the pivot.
The algorithm operates in a single pass and has a time complexity of O(n) and a space complexity of O(1), making it suitable for rearranging elements in-place. It effectively addresses challenges like the Dutch National Flag problem, enhances the efficiency of QuickSort, and performs exceptionally well with arrays that have duplicate elements. In general, the three-way partitioning technique is a robust method for manipulating arrays, offering a flexible approach for orderly and systematic sorting in various scenarios.
Approach-1: Brute Force Approach
A straightforward method involves performing multiple iterations through the array to categorize elements according to a pivot, thus achieving a three-way partition. Despite its simplicity in implementation and minimal space usage, this approach is not considered efficient.
The last step involves combining the three sections into a fresh array. The brute force method guarantees correct segmentation but comes with the significant drawback of needing additional memory (O(n) space complexity) and multiple iterations (O(n) time complexity).
Example:
Let's consider a scenario to demonstrate the Three-way partitioning around an element in C++ using a brute-force method.
#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 Processing:
- Executing the getUserInput function is responsible for retrieving the array elements. By utilizing the getline function, the complete input is captured as a string, which is then dissected into separate integers through a stringstream. These integers are subsequently appended to a vector array designated for storing the array elements.
- In the initial segment, the getPivot function prompts the user to enter a pivotal element, serving as the benchmark value for the partitioning process.
Validation:
- Prior to moving forward, the validateArray function verifies the non-emptiness of the array. Should the array be empty, an error message is displayed, leading to an early termination of the program to prevent processing invalid input.
- To guarantee the presence of the pivot element within the array, the validatePivot function is employed. If the pivot element is not identified, a warning is generated, allowing the program to proceed and offering adaptability in scenarios where the pivot is absent.
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 each of the three passes operates separately, the cumulative time complexity is the amalgamation of these distinct passes:
- The overall time complexity is calculated as O(n) + O(n) + O(n) = O(3n) = O(n).
- This implies that the number of comparisons (time complexity) in the brute force strategy is O(n), where n signifies an index within an array. In Big O notation, the constant factor of 3 is disregarded.
Space Complexity:
The amount of space required is calculated based on the extra storage needed for the divided sections:
- To achieve this, we establish three distinct vectors to hold elements smaller than, equal to, and greater than the pivot value. In the most unfavorable scenario, each vector may need to accommodate all n elements, leading to a cumulative space complexity directly related to the array's magnitude.
- As a result, the space complexity is O(n) due to the creation of three additional vectors, each expanding in proportion to the input size.
Approach-2: Two-Pass In-Place Partitioning
Two-step partitioning with on-the-spot exchanges is an alternative technique for organizing elements around a pivot in three segments. Despite being less efficient than the Dutch National Flag algorithm in terms of execution time, this approach outperforms a straightforward method in space efficiency by utilizing a fixed, minimal amount of additional memory.
This method involves two iterations through the array:
- Initial Pass: During the initial pass, all elements that are smaller than the pivot are shifted to the left side of the array, while those larger than the pivot are shifted to the right side. This process is performed directly on the array, but it does not address elements that are equal to the pivot.
- Subsequent Pass: The second pass handles elements that are equal to the pivot, ensuring they are positioned between the smaller and larger elements.
- Initially, arrange the array based on the pivot value, followed by dividing the array into two segments: one containing values smaller than the pivot and the other with values equal to or larger than the pivot.
Steps:
Avoid the utilization of multiple pointers for array element access. Evaluate the pivot element against the array elements and interchange it with the elements situated on the left side of the array if they are smaller than it.
- Second iteration: Following the initial iteration, there might still be elements in the first array that exceed the pivot positioned on the left side, and elements in the second array that are inferior to the pivot positioned on the right side. During this iteration, we relocate all identical elements to the center.
- Final Configuration: Post both iterations, the array is segregated with elements inferior to the pivot on the left, identical elements in the middle, and superior elements on the right.
Example:
Let's consider a scenario to demonstrate the Three-way partitioning around an element in C++ by employing a two-pass in-place partitioning technique.
#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 program prompts the user to enter a series of integers separated by spaces. It validates the input to ensure that the integers are both non-empty and valid. If the input is found to be invalid, the program prompts the user to enter valid data.
Pivot Validation:
Finally, the software gathers the array and prompts the user to enter a pivot element. Initially, it verifies the presence of the pivot within the array. If the pivot is not located, the program proceeds and provides a warning message.
Partitioning Logic:
The array undergoes partitioning in two stages:
During the initial pass, elements are rearranged such that those smaller than the pivot are shifted to the left, those equal to the pivot are placed in the middle, and those larger than the pivot are positioned to the right.
In the subsequent pass, the main objective is to ensure that the pivot element is situated amidst values smaller and larger than itself.
Now, divide the array into sections containing elements that are smaller and larger than the pivot element, and then display the resulting 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:
- To clarify, the software employs a separate array to hold the provided integers, resulting in a space complexity of O(n).
- Therefore, it does not require any extra space apart from this, maintaining a space complexity of O(n).
