In this post, we will discuss few problems that can easily solved in linear time and constant space by modifying partitioning logic of quicksort algorithm.

Problem #1. Given an binary array, sort it in linear time and constant space. Output should print contain all zeroes 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 pivot element and make one pass of partition process. The resultant array will be sorted.

#include <iostream> #include <algorithm> using namespace std;
// Function to sort binary array in linear time int partition(int A[], int n) { 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 < n; i++) { if (A[i] < pivot) { swap(A[i], A[j]); j++; } } }
int main() { int A[] = { 1, 0, 0, 0, 1, 0, 1, 1 }; int n = sizeof(A)/sizeof(A[0]);
partition(A, n);
// print the rearranged array for (int i = 0 ; i < n; i++) cout << A[i] << ” “;
return 0; } |

`Output: `

0 0 0 0 1 1 1 1

Problem #2. Given an array consisting of positive and negative integers, segregate them in linear time and constant space. Output should print contain 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 pivot element and make one pass of partition process. The resultant array will satisfy the given constraints.

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 |
#include <iostream> #include <algorithm> using namespace std;
void partition(int a[], 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 (a[i] < 0) // pivot is 0 { swap(a[i], a[pIndex]); pIndex++; } } }
int main() { int a[] = { 9, –3, 5, –2, –8, –6, 1, 3 }; int n = sizeof(a)/sizeof(a[0]);
partition(a, 0, n – 1);
// print the rearranged array for (int i = 0 ; i < n; i++) cout << a[i] << ” “;
return 0; } |

`Output:`

-3 -2 -8 -6 5 9 1 3

Problem #3. Given an array of integers, rearrange the array such that it contains positive and negative numbers at alternate positions. If array contains more positive or negative elements, they should be moved to 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 pivot element and make one pass of partition process. The resultant array will contain all positive integers at the end of the array and all negative integers in the beginning. Then we swap alternate negative element from next available positive element till end of array is reached or all negative or positive integers are exhausted.

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 <algorithm> #include <iomanip> using namespace std;
// Partitioning routine of quicksort int partition(int A[], int n) { int j = 0; int pivot = 0; // consider 0 as pivot
// each time we find a negative number, j is incremented // and negative element would be placed before the pivot for (int i = 0; i < n; i++) { if (A[i] < pivot) { swap(A[i], A[j]); j++; } }
// j holds index of first positive element return j; }
// Function to rearrange given array such that it contains positive // and negative numbers at alternate positions int rearrange(int A[], int size) { // partition given array such that all positive elements move // to end of the array int p = partition(A, size);
// swap alternate negative element from next available positive // element till end of array is reached or all negative or // positive elements are exhausted. for (int n = 0; (p < size && n < p); p++, n += 2) { swap(A[n], A[p]); } }
int main() { int A[] = { 9, –3, 5, –2, –8, –6, 1, 3 }; int n = sizeof(A)/sizeof(A[0]);
rearrange(A, n);
// print the rearranged array for (int i = 0 ; i < n; i++) { cout << setw(3) << A[i]; }
return 0; } |

`Output:`

5 -2 9 -6 1 -8 3 -3

Problem #4. Given an array of integers, move all zeros present in the array 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 partition process. The partitioning logic will read all elements and each time we encounter a non-pivot element, that element is swapped with the first occurrence of pivot.

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 |
#include <iostream> #include <algorithm> using namespace std;
// Function to move all zeros present in the array to the end void partition(int A[], int n) { 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 < n; i++) { if (A[i] != 0) // pivot is 0 { swap(A[i], A[j]); j++; } } }
int main() { int A[] = { 6, 0, 8, 2, 3, 0, 4, 0, 1 }; int n = sizeof(A) / sizeof(A[0]);
partition(A, n);
for (int i = 0 ; i < n; i++) cout << A[i] << ” “;
return 0; } |

`Output:`

6 8 2 3 4 1 0 0 0

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.