Problems solved using partitioning logic of Quicksort

Posted in

Vinay Khatri
Last updated on August 10, 2024

Problem

What are some of the problems that can be solved using the partition logic of quicksort?

What is Partition Logic

The partition logic of quicksort selects one of the elements as pivot and puts all the elements smaller than it on its left side and all elements greater than it on its right side.

Problem 1:

Given a binary array, sort it in linear time and constant space.

Solution

We can choose 1 as our pivot element and apply partition logic once. This will put all 0s to the left side and all 1s to the right side.

Code

```#include <iostream>
#include <algorithm>
using namespace std;

int partition(int arr[], int n)
{
int pivot = 1;
int j = 0;

for (int i = 0; i < n; i++)
{
if (arr[i] < pivot)
{
swap(arr[i], arr[j]);
j++;
}
}
}

int main()
{
int arr[] = { 0, 1, 0, 1 };
int n = sizeof(arr)/sizeof(arr[0]);

partition(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}

return 0;
}```

Output

`0 0 1 1`

Problem 2:

Given an array of positive and negative integers, segregate them in linear time and constant space. The negative numbers should appear first, followed by positive integers.

Solution

We can choose 0 as our pivot element and apply the partition logic of quicksort.

Code

```#include <iostream>
#include <algorithm>
using namespace std;

void partition(int a[], int start, int end)
{
int pivot = start;

for (int i = start; i <= end; i++)
{
if (a[i] < 0)
{
swap(a[i], a[pivot]);
pivot++;
}
}
}

int main()
{
int a[] = { 1, 2, -4, 6, -5 };
int n = sizeof(a)/sizeof(a[0]);

partition(a, 0, n - 1);

for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}

return 0;
}
```

Output

`-4 -5 1 6 2`

Problem 3:

Given an array of positive integers, place all 0s at the end of the array and maintain the relative order of the elements.

Solution

We can use 0 as our pivot elements and apply partition logic once. The partitioning logic will traverse through all the elements, and each time we encounter a non-pivot element, we swap it with the first occurrence of the pivot element.

Code

```#include <iostream>
#include <algorithm>
using namespace std;

void partition(int arr[], int n)
{
int j = 0;

for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
{
swap(arr[i], arr[j]);
j++;
}
}
}

int main()
{
int arr[] = { 1, 5, 0, 5, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);

partition(arr, n);

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}

return 0;
}```

Output

`1 5 5 4 0 0`

Problem 4

Given an array of integers, rearrange it in a way that contains positive and negative numbers at alternate positions. If the array contains more positive or negative elements, move them to the end of the array.

Solution

We can choose 0 as our pivot element and make one partition pass. The positive elements will be moved to the right side of the array. After this, swap alternative negative elements with the next available positive integer until the array is reached or all positive or negative elements are exhausted.

C++ Code

```#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int partition(int arr[], int n)
{
int j = 0;
int pivot = 0;

for (int i = 0; i < n; i++)
{
if (arr[i] < pivot)
{
swap(arr[i], arr[j]);
j++;
}
}

return j;
}

int solve(int arr[], int m)
{

int p = partition(arr, m);

for (int n = 0; (p < m && n < p); p++, n += 2) {
swap(arr[n], arr[p]);
}
}

int main()
{
int arr[] = { 1, -4, 5, -7, 8 };
int n = sizeof(arr)/sizeof(arr[0]);

solve(arr, n);

for (int i = 0; i < n; i++) {
cout << arr[i]<<" ";
}

return 0;
}
```

Output

`5 -7 1 -4 8`

People are also reading: