491 views
1 votes
1 votes
Given an array $A = \{a_1, a_2, \dots, a_n\}$ of unsorted distinct integers, write a program in pseudo-code for the following problem: given an integer $u$, arrange the elements of the array $A$ such that all the elements in A which are less than or equal to $u$ are at the beginning of the array, and the elements which are greater than $u$ are at the end of the array. You may use at most 5 extra variables apart from the array $A$.

1 Answer

1 votes
1 votes
// similar to quick_sort() partition algorithm

// here we need to partition the array according
// the give key U such that elements less than U
// are at the beginning and greater ones are at the
// back of the array

// pseudo algorithm
/*
1. i = -1, j=0;
2. move j forward one by one and compare each a[j] with u untill j<n
3. if a[j] <= u then go to step 4 else go to step 2
4. increment i and swap a[i] and a[j] and go to step 2 again
*/

INPUT :

OUTPUT :       

Complexity : Linear

edited by

Related questions

6 votes
6 votes
4 answers
3
1 votes
1 votes
1 answer
4
go_editor asked Jun 2, 2016
672 views
A group of $15$ boys plucked a total of $100$ apples. Prove that two of those boys plucked the same number of apples.