Rearranging an array of integers

Question

I need to implement the following in both pseudocode and java.

Input: an array of integers

Output: Rearrange the array to have the following:

1. suppose the first element in the original array has the value x
2. In the new array, suppose that x is in position I, that is data[I]=x. Then, data[j] <= x for all j x for all j>I. This means that all the values to the "left" of x are less than or equal to x and all the values to the "right" are larger than x.
3. An example is as follows: Suppose the array has the elements in this initial order: 4,3,9,2,7,6,5. After applying your algorithm, you should get: 3,2,4,5,9,7,6. That is, the leftmost element, 4, is positioned in the resulting array so that all elements less than 4 (2 and 3) are to its left (in no particular order), and all elements larger than 4 are to its right (in no particular order).

There is no space requirement for the algorithm, only that the problem is solved in O(n) time.

Thus, I am under the impression that a bubble sort is best here.

A swapping algorithm in this case is not the best option and I would like to get some feedback on other methods that can be implemented here.

Thank you!

Answer 1

create an array with space to fit all the elements. If number is < x then place it at the beginning of the array, if number is > x then place it at the end. If number is equal to x then just ignore it and move on. Finally you fill up the remaining spots with the values equal to x.