CareerCup

O(NlogN) algo.

-> Write your partition function with pivot as x( x may not be present in the array)

-> Partition function returns index k such that all elements in [0,k] are less than 'x' and all elements in range [k+1, N-1] are greater than 'x' .

->Now sort [0,k] range in ascending and [k+1, N-1] in descending order using Quick Sort or some other O(NlogN) algo.

1:Mark the element 'x' as key element and take it to one of the two corners of an array.
2:Arrange elements in such fashion that elements to its left are smaller than the key element and right are greater or vice-versa (requires atmost n comparisons).
3:Have 2 BST 1 for elements smaller than key element and other for elements greator than or equal to key element.
4:Have inorder traversal for ascending order.
5:And put elements into stack first by having inorder traversal and then pop out for descending order.

Sort the array using quick sort in descending order
Find the index of key element in the array
Reverse the array from key elements' index + 1 element to the last element to get the ascending order

Question doesn't asks you to have array as "all less elements followed by greater elements". It may be mix as well but order for less and greater elements has to be maintained among themselves.

Quick sort and then take i+1 to n elements and reverse them. Here i is the index for the given element.

as no's can be mixed in either way....hence
algo :
for (i=0 to n)
check x to a[i] : if a[i]>=x then find max (a[i])
else find min(a[i])

end