Three-way Partitioning of an Array Around a Given Range

Approach 2(Efficient)

One technique to solve the problem is to traverse the array and swap items so that those less than l are swapped to the left and those greater than h are swapped to the right. We use the following algorithm to accomplish this:

Algorithm

1. Set the first and last members of the array to begin and end, accordingly.
    
2. Using the counter variable i loop through the array until i is greater than the end.

• If the value at the ith position is greater than h, swap the ith position element with the end position element and decrease the end.
   
• If the value at the ith location is less than l, swap the ith element with the begin element, and then increase begin and i.
   
• Otherwise, increase the counter variable I if the value at the ith place is between l and h.
   
• The resulting array is partitioned into three parts.

Implementation

#include<iostream>
using namespace std;
void threewaypartitioning(int arr[], int n, int l, int h)
{
  int begin = 0, end = n-1; 
  for(int i = 0; i <= end; i++)
  {
    if(arr[i] < l)
    {
      swap(arr[i], arr[begin]);
      begin++;  
    }
    else if(arr[i] > h)
    {
      swap(arr[i], arr[end]);
      i--;
      end--;
    }
  }
}


int main()
{
  int arr[] = {2,5,87,56,12,4,9,23,76,1, 45};
  int n = 8;
  threewaypartitioning(arr, n, 15, 30);
  for(int i = 0; i < n; i++)
    cout<<arr[i]<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

2
5
9
12
4
23
56
87

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: O (N), here ‘n’ is the number of elements of the array.

Auxiliary Space: O (1), as we are not using any extra space.
 

Frequently Asked Questions

What exactly is three-way partitioning?

The three-way quick sort divides the array into three parts. The first part is smaller than the pivot, the second part is equal to the pivot, and the third part is larger. It's a linear-time partitioning method. This partition is similar to the problem with the Dutch National Flag.

Given an algorithm, how do you partition an array?

Partitioning is the most crucial process in quickSort (). Given an array and a pivot element x, the goal of partitions is to place x in the correct position in the sorted array, with all smaller elements (less than x) placed before x and all larger elements (greater than x) set after x. All of this should be completed linearly.

What's the best way to do a three-way quicksort?

The basic quicksort techniques are finding an element as the pivot, partitioning the array around the pivot, and then recurring for sub-arrays on the left and right of the pivot. The three-way quicksort is similar to the two-way quicksort, but it has three sections. The array arr[1 to n] is split into three sections.
 

Conclusion

When considering this problem, sorting the given array comes to mind as an immediate answer. A sorted array will be partitioned into elements less than l, between l and h, and greater than h. This necessitates a more efficient method that does not require sorting of the items in each partition. You must understand Three-Way Partitioning after reading this article.

We hope that this article has helped you enhance your knowledge regarding the subject of Array and 3-way partitioning.

You can also practice some relevant problems at Coding Ninjas Studio such as:

1. Find the Number Occurring Odd Number of Times
2. Find the minimum element in a sorted and Rotated Array
3. Sort a Rotated Sorted Array
4. Find the minimum element in a sorted and Rotated Array
5. Aggressive Cows

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!