sorting alogithm

HLRosenberger
HLRosenberger used Ask the Experts™
on
Suppose I have n distinct integers.  I want to place these integers in an "array".  However, between each element in the "array" is an inequality sign.   So, the numbers need to be entered in a fashion that satisfies the inequality.   The n distinct integers are in random order.  So, how could I do this?  Would pre-sorting the integers help, and is so how, because the inequalities could be in any order.

Thanks.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Presumably, the array (with the inequalities) is fixed.  You need to analyze that first.

You will typically find several local minima and maxima, and the run lengths between them.

If you do that, and presort the integers, the filling-in algorithm may be come clear.

Author

Commented:
What exactly do you mean by, "You will typically find several local minima and maxima, and the run lengths between them" ?
If you take         a < b < c > d < e > f > g > j

c  and  e   are local maxima.   They are not less than anything.  One of them has to be the absolute maximum.

a   d   and  j  are local minima.  They are not greater than anything.  One of them has to be the absolute minimum.

You have to work several examples by hand to see what's going on.

Author

Commented:
ah, got it.  I'll play around with it.
I would work on a recursive function to arrange the array in every possible order then test the inequalities in each case

Author

Commented:
Thanks
It depends on what the ultimate questions is.
Do you need to find a solution, or find out how many solutions there are?

>> recursive function to arrange the array in every possible order
     For an n-element array, that would take on the order of   n!   operations.

But sorting the integers only takes on the order of   n*log(n)   operations.
And the analysis of the inequalities takes on the order of   n  operations.
>>But sorting the integers only takes on the order of   n*log(n)

but at that point the solution is not yet solved, or is it?  In your simple example you said that there are two local maxima, and that one of these is the absolute maxima, but how to determine which?

I agree that to attempt a solution for a sufficiently large n, something more sophisticated than all combinations is required.
>>But sorting the integers only takes on the order of   n*log(n)

but at that point the solution is not yet solved, or is it?

It is solved.  Once you have analyzed the array and sorted the list of integers, there are a number of O=n strategies to finish.

If you have n integers, then you will have (n-1) inequalities and 2^(n-1) possible array configurations.

Note that the number of maxima and minima are constrained:  every local maxima is
associated with exactly one or two local minima, and vice versa.

     So   Number of Max  =  Number of Min  +/-  1   for all configurations.

     If all the inequalities are the same, there will be one max and one min and only one way
     to fill in the numbers --  the sorted list in order.

     If the direction of the inequalities changes in every position, then every location will be
     either a local max or min.  One strategy to fill in the numbers is to fill in all the max's
     from the high side of the list and the min's from low side.  Order doesn't matter.
     There will be something like  ((n/2)!)^2   possible solutions.

     For the intermediate cases, where there are local max and minima with some runs
     in between, you can fill in the max and minima as before, and then fill in the rest
     top-down or bottom up in a straight forward fashion.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial