from Debilski's answer:
I’ll adapt your idea a little. We do
have our objects but they don’t differ
in weight, but in speed. So, at the
beginning all objects are aligned at
the starting line and on the starting
shot, they’ll all move with their
respective velocities to the finish.
Clear enough: First object in finish
will emit a signal, saying it is
there. You catch the signal and write
to the results paper who it was
I'd simplify it a step further and say these objects are random positive integers. And we want to sort them in an ascending order as they approach zero, so they have a distance from zero d
which initially is equal to the integer itself.
Assuming the simulation takes place in discrete time steps i.e. frames, in every frame, every object's new distance would be: d = d - v
and an object would get added to the list when its d ≤ 0
. That is one subtraction and one conditional. Two discrete steps for each object, so the calculations seem to be O(n): linear.
The catch is, it is linear for one frame only! It is multiplied by the number of frames f
required to finish. The simulation itself is O(nf): quadratic.
However, if we take the duration of a frame as the argument t
we get the ability to affect the number of frames f
in an inversely proportional manner. We can increase t
to reduce f
but this comes at the cost of accuracy, the more we increase t
, the more the probability that two objects will finish in the same time frame therefore be listed as equivalent, even if they are not. So we get an algorithm with adjustable accuracy (as it is in most finite element simulation contexts)
We can further refine this by turning it into an adaptive+recursive algorithm. In human code it would be:
function: FESort: arguments: OriginalList, Tolerance
define an empty local list: ResultList
while OriginalList has elements
define an empty local list: FinishedList
iterate through OriginalList
decrement the distance of each object by Tolerance
if distance is less than or equal to zero, move object from OriginalList to FinishedList
check the number of elements in FinishedList
when zero
set Tolerance to double Tolerance
when one
append the only element in FinishedList to ResultList
when more
append the result of FESort with FinishedList and half Tolerance to ResultList
return ResultList
I'm wondering if there's any real similar implementation that works for someone.
Interesting subject indeed :)
PS. The pseudocode above is my idea of pseudocode, please feel free to rewrite it in a more legible or conformant way if there is one.