Norway


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

Download   Run Code

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.

Download   Run Code

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.

Download   Run Code

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.

Download   Run Code

Output:

6 8 2 3 4 1 0 0 0

 
1 Star  - rating on - Problems solved using partitioning logic of quicksort2 Stars  - rating on - Problems solved using partitioning logic of quicksort3 Stars  - rating on - Problems solved using partitioning logic of quicksort4 Stars  - rating on - Problems solved using partitioning logic of quicksort5 Stars  - rating on - Problems solved using partitioning logic of quicksort (2 votes, average: 5.00 out of 5)

- loading - Problems solved using partitioning logic of quicksortLoading…

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 🙂
 



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here