sorting alogithm
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.
Thanks.
ASKER
What exactly do you mean by, "You will typically find several local minima and maxima, and the run lengths between them" ?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
ASKER
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.
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 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.
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.
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.