Problems solved using partitioning logic of Quicksort

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:

• Depth First Search(DFS)- DSA
• Find the largest & smallest element in Array
• What is Stack in Data?
• Circular Doubly Linked List
• Tree Data Structure & Algorithm
• Difference Between Repeater, DataList and GridView
• Longest Increasing Subsequence
• Diameter of a Binary Tree
• Clone a Singly Linked List
• The Stock Span Problem