Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach 1( Naive)
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Approach 2(Efficient)
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What exactly is three-way partitioning?
4.2.
Given an algorithm, how do you partition an array?
4.3.
What's the best way to do a three-way quicksort?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Three-way Partitioning of an Array Around a Given Range

Author Palak Mishra
1 upvote

Introduction

You have a large, potentially enormous array of objects in random order. You want to divide the array in half, with the lower half containing objects that match the condition and the upper half containing objects that do not. An array's partitioning is the name for this process.

We are going to discuss an array partitioning problem in this article. 

Also See, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Partition an array around a range [startVal, endVal] so that it is divided into three parts.

  1. All elements with a smaller startval value are prioritized.
  2. Following that are all elements in the range startval to endval.
  3. In the end, all elements with a value greater than endval appear.

Sample Examples

Consider the following array:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

 

two-part structure Quick Sort would choose a value, such as 4, and sort the array so that every element greater than 4 is on one side and every element less than 4 is on the other. As follows:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

 

A three-part structure Quick Sort would divide the array into two partitions based on two values. Let's go with 4 and 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

 

It's merely a minor variation on the standard quicksort.

Approach 1( Naive)

Sorting the array can help with this. However, it will take nlogn time to do so. (where n denotes the array's length).

Algorithm

  1. Initialize the array's elements after declaring an array of size n.
     
  2. Now, initialise the range's lower and upper bounds and save them in the variables low and high, respectively.
     
  3. Sort the array now that it has been partitioned by sorting.
     

Note: The array's order cannot be preserved by this algorithm.

Syntax:

Sort(arrayname, arrayname+sizeofarray) ;

 

Elements are sorted in the order of low to high.

Implementation

#include<bits/stdc++.h>
using namespace std;
int main(){
    int arr[] ={23,5,18,10,20,89 };
    int n =sizeof(arr)/sizeof(int);
    int low=0,high=4;
    sort(arr,arr+n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
   }
    return 0;
}

 

Output

5 10 18 20 23 89

 

Complexity Analysis

Time Complexity: O(n^3), as the array is traversed by three nested loops.

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

Output

2
5
9
12
4
23
56
87

 

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

Previous article
Largest Number Formed From an Array
Next article
Split the array and add the first part to the end
Live masterclass