ISI2012-PCB-A-3

Question

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$.

Answer 1

// 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