重力排序：这是否可能编程？ [英] Gravity Sort : Is this possible programatically?

问题描述

最近我一直在思考在排序算法中使用面向对象的设计。然而，我无法找到一种恰当的方法来使得这种排序算法在O（n）时间内进行排序更接近。

好的，这是我一直在想的一个星期。我有一组输入数据。我将为每个输入数据分配一个质量（假定输入数据是一种质量和一种类型球体如果我们假设所有物体都是与质量成正比的完美球形物体，则最重的物体首先碰到地面。我将把我所有的输入数据放在与地球相同距离的空间中。我会让他们自由落体。根据引力定律，最重的人首先击中地面。并且他们的命令将给我排序的数据。这在某些方面是有趣的，但在下面我觉得这应该是可能的使用我直到日期学习的OO

真的有可能做一个排序技术使用重力拉动情景或者我是愚蠢/疯狂吗？

编辑：同时抛出所有物体撞到地面，因此我介绍

解决方案

事情是，虽然OOP的想法可能是对现实世界进行建模，这并不意味着在现实世界中需要多长时间以及用计算机模拟它需要多长时间之间有直接的对应关系。

想象一下您的程序所需的实际步骤：

1. 必须为您的数据集中的每个项目构建一个对象。在大多数现代硬件上，这将独自需要迭代，从而使您的策略O（n）最佳。


2. 需要模拟重力的影响，对于每个对象。再次，实现这一点的最明显的直接方法是迭代。


3. 必须捕获每个对象落在编程模型中地球表面的时间并且通过一些实现特定的机制，相应的对象将需要被插入到有序列表中。

考虑到问题进一步引起了额外的并发症。问问自己：你需要多高一点来定位这些对象才能开始？显然足够高，所以最大的一个实际上是即距地球的距离比最大物体的半径更远。但是你怎么知道这是多远？您需要首先确定集合中最大的对象;再次，（可能）需要迭代。此外，人们可能会想到，这种模拟可以是多线程的，以尝试模拟实际下降的对象概念的实时行为;但是当您检测到新的冲突时，您可能会发现自己正试图将一些项目添加到集合中（这显然需要非零时间的操作）。所以这也会造成线程问题。

简而言之，我无法想象如何在没有特殊硬件的情况下简单地使用OOP来正确实现这个想法。也就是说，真的是一个好主意。它提醒我，实际上， Bead Sort - 算法，虽然不一样您的想法，也是一种利用重力物理概念的排序解决方案，毫不奇怪，需要专门的硬件。

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.

解决方案

The thing is, though one of the ideas of OOP may be to model the real world, that doesn't mean there's a direct correspondence between how long something takes in the real world and how long it would take to simulate it with a computer.

Imagine the actual steps required for your procedure:

1. An object has to be constructed for every item in your set of data. On most modern hardware, this alone would require iteration and would therefore make your strategy O(n) at best.
2. The effect of gravity would need to be simulated, for each object. Again, the most obvious, straightforward way to implement this would be to iterate.
3. The time that each object lands on the surface of the "Earth" in your programming model would have to be captured and, via some implementation-specific mechanism, the corresponding object would need to be inserted into an ordered list as a result.

Considering the problem further introduces additional complications. Ask yourself this: how high up do you need to position these objects to start? Obviously high enough so that the largest one actually falls; i.e., farther from the Earth than the radius of the largest object. But how do you know how far that is? You'd need to first determine the largest object in the collection; this, again, would (probably) require iterating. Also, one might imagine that this simulation could be multithreaded to attempt to simulate the real-time behavior of the notion of objects actually falling; but then you will find yourself attempting to add items to a collection (an operation which obviously takes a non-zero amount of time) potentially at the same time that new collisions are being detected. So this will create threading issues as well.

In short, I have trouble imagining how this idea could be properly implemented simply using OOP without special hardware. That said, it really is a good idea. It reminds me, in fact, of Bead Sort--an algorithm which, though not the same as your idea, is also a sorting solution that takes advantage of the very physical concept of gravity and, not surprisingly, requires specialized hardware.

这篇关于重力排序：这是否可能编程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！