In this post, we will discuss few problems that can easily in linear 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.

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.

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.

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 will read all elements and each time we encounter a non-pivot element, that element is swapped with the first occurrence of pivot.

Output:

6 8 2 3 4 1 0 0 0

(2 votes, average: 5.00 out of 5)