Gravity Sort : Is this possible programmatically?

Question

I've been thinking recently on using the Object Oriented design in the sorting algorithm. However I was not able to find a proper way to even come closer in making this sorting algorithm that does the sorting in O(n) time.

Ok, here is what I've been thinking for a week. I have a set of input data. I will assign a mass to each of the input data (assume input data a type of Mass and a type of Sphere. If we assume all objects to be perfectly spherical objects with shapes proportional to their mass, the heaviest one touches the ground first.). I will be placing all my input data in the space all at same distance from earth. And I will make them free fall. According to gravitational law, the heaviest one hits the ground first. And the order in which they hit will give me the sorted data. This is funny in some way, but underneath I feel that this should be possible using the OO that I have learnt till date

Is it really possible to make a sorting technique that uses gravitational pull like scenario or am I stupid/crazy?

Edit: Turns out all objects hit the ground at the same time hence I introduced the spherical object concept.

Answer 1

There is actually a quite famous sorting algorithm called Spaghetti sort which is sort of similar to yours. You can check out some of the many analyses of it on the web. e.g. on cstheory.

Answer 2

Analyse : (1) All centers of spheres are aligned at start (2) greater number ==> mass higher ==> radius greater ==> distance to the ground lower (3) in 'vacuum' same acceleration = same speed evolution ==> same distance for the center ==> how greater de radius...how earlier the sphere will hit the ground ==> conceptually OK, good physical technique if when a sphere hit the ground it can send an indentification signal + hit time ... wich will give the sorted list Practically...not a 'good' numeric technique

Answer 3

It should be definitely only you should have proper hardware supported for it. Otherwise this sounds a very cool idea. Hope someone presents an IEEE paper to make this crazy dream visualized.

Answer 4

In a fictious "gravitational computer" this kind of sorting would take O(1) to be solved. But with the real computers like we know it, your lateral thought wouldn't help.

Answer 5

1. I believe it is nice to mention/refer to: What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently? Sorting is O(nlog(n)), why not trying to solve NP-hard problems?
2. By the laws of physics objects fall with proportions to the gravitational constant the mass is negligible.
3. Simulating a physical process can affect the actual time complexity.

Answer 6

Some weeks ago I was thinking about the same thing.

I thought to use Phys2D library to implement it. It may not be practical but just for fun. You could also assign negative weights to the objects to represent negative numbers. With phys2d library you can define the gravity so objects with negative weight will go to the roof and objects with positive weight will fall down .Then arrange all objects in the middle between the floor and roof with the same distance between floor and roof. Suppose you have a resulting array r[] of length=number of objects. Then every time an object touches the roof you add it at the beginning of the array r[0] and increment the counter, next time an object touches the roof you add it at r[1], every time an object reaches the floor you add it at the end of the array r[r.length-1], next time you add it at r[r.length-2]. At the end objects that didn't move(stayed floating in the middle) can be added in the middle of the array(these objects are the 0's).

This is not efficient but can help you implement your idea.