Problems solved using partitioning logic of Quicksort
This post will discuss a few problems that can be easily solved in linear time and constant space by modifying the partitioning logic of the Quicksort algorithm.
Problem #1
Given a binary array, sort it in linear time and constant space. The output should print all zeros, followed by all ones.
For example,
Input: { 1, 0, 1, 0, 1, 0, 0, 1 }
Output: { 0, 0, 0, 0, 1, 1, 1, 1 }
The idea is to use 1 as a pivot element and make one pass of the partition process. The resultant array will be sorted. The following C++ program demonstrates it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to sort a binary array in linear time int partition(vector<int> &nums) { int pivot = 1; int j = 0; // each time we encounter a 0, `j` is incremented, and // 0 is placed before the pivot for (int i = 0; i < nums.size(); i++) { if (nums[i] < pivot) { swap(nums[i], nums[j]); j++; } } } int main() { vector<int> nums = { 1, 0, 0, 0, 1, 0, 1, 1 }; partition(nums); // print the rearranged array for (int i: nums) { cout << i << " "; } return 0; } |
Output:
0 0 0 0 1 1 1 1
Problem #2
Given an array of positive and negative integers, segregate them in linear time and constant space. The output should print all negative numbers, followed by all positive numbers.
For example,
Input: [9, -3, 5, -2, -8, -6, 1, 3]
Output: [-3, -2, -8, -6, 5, 9, 1, 3 ]
The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will satisfy the given constraints. This approach is demonstrated below in C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; void partition(vector<int> &nums, int start, int end) { int pIndex = start; // each time we find a negative number, `pIndex` is incremented, // and that element would be placed before the pivot for (int i = start; i <= end; i++) { if (nums[i] < 0) // pivot is 0 { swap(nums[i], nums[pIndex]); pIndex++; } } } int main() { vector<int> nums = { 9, -3, 5, -2, -8, -6, 1, 3 }; int n = nums.size(); partition(nums, 0, n - 1); // print the rearranged array for (int i: nums) { cout << i << " "; } return 0; } |
Output:
-3 -2 -8 -6 5 9 1 3
Problem #3
Given an integer array, rearrange it such that it 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.
For example,
Input: { 9, -3, 5, -2, -8, -6, 1, 3 }
Output: { 5, -2, 9, -6, 1, -8, 3, -3 }
The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will contain all positive integers to the end of the array and all negative integers at the beginning. Then swap alternate negative elements from the next available positive element until the end of the array is reached, or all negative or positive integers are exhausted.
Following is the C++ implementation of the idea:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> using namespace std; // Partitioning routine of Quicksort int partition(vector<int> &nums) { int j = 0; int pivot = 0; // consider 0 as a pivot // each time we find a negative number, `j` is incremented, // and a negative element would be placed before the pivot for (int i = 0; i < nums.size(); i++) { if (nums[i] < pivot) { swap(nums[i], nums[j]); j++; } } // `j` holds the index of the first positive element return j; } // Function to rearrange given array such that it contains positive // and negative numbers at alternate positions int rearrange(vector<int> &nums) { // partition given array such that all positive elements move // to the end of the array int p = partition(nums); // swap alternate negative elements from the next available positive // element till the end of the array is reached, or all negative or // positive elements are exhausted. for (int n = 0; p < nums.size() && n < p; p++, n += 2) { swap(nums[n], nums[p]); } } int main() { vector<int> nums = { 9, -3, 5, -2, -8, -6, 1, 3 }; rearrange(nums); // print the rearranged array for (int i: nums) { cout << setw(3) << i; } return 0; } |
Output:
5 -2 9 -6 1 -8 3 -3
Problem #4
Given an integer array, move all zeros present in it to the end. The solution should maintain the relative order of items in the array.
For example,
Input: { 6, 0, 8, 2, 3, 0, 4, 0, 1 }
Output: { 6, 8, 2, 3, 4, 1, 0, 0, 0 }
The idea is to use 0 as a pivot element and make one pass of the partition process. The partitioning logic will read all elements, and each time we encounter a non-pivot element, swap it with the first occurrence of the pivot.
The implementation can be seen below in C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to move all zeros present in an array to the end void partition(vector<int> &nums) { int j = 0; // each time we encounter a non-zero, `j` is incremented, and // the element is placed before the pivot for (int i = 0; i < nums.size(); i++) { if (nums[i] != 0) // pivot is 0 { swap(nums[i], nums[j]); j++; } } } int main() { vector<int> nums = { 6, 0, 8, 2, 3, 0, 4, 0, 1 }; partition(nums); for (int i: nums) { cout << i << " "; } return 0; } |
Output:
6 8 2 3 4 1 0 0 0
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)