重力排序：这是可能的编程方式?[关闭]

Question

我一直在想，最近上的使用面向对象设计的，在排序的算法。但是我没能找到一个适当的方式，甚至更加接近于作出这种排序的算法，不排序在O(n)的时间。

好，这是什么我一直在思考一个星期。我一定输入数据。我会分配一个质的每一个输入数据(假设的数据输入一个类型的 Mass 和一个类型的 Sphere.如果我们假定所有对象是完全球形对象的形状，比他们的质量，最重的一个接触地面的第一个。).我将把我所有的输入数据中的空间都在相同的距离地球。我会让他们自由下落。根据重力的法律，最重的一个撞击地面的第一个。和他们打给我的排序的数据。这是有趣的一些方式，但下面我觉得这个应该尽可能使用OO，我学到的日期

真的是这可能使分类的技术，使用引力等方案或我愚蠢/疯了吗？

编辑： 事实证明，所有物体撞击地面在同一时间，因此我介绍的球形象的概念。

Answer 1

事实是，虽然一个 想法 的面向对象可以是模型的真正的世界，这并不意味着没有直接对应关系如何，只要的东西需要在现实世界和多久它会采取行模拟计算机。

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

1. 一个目必须构成为每一个项目，在你的数据集。在最现代化的硬件，这就需要次迭代，因此将让你的策略O(n)在 最好的.
2. 重力的作用将需要进行模拟，对于每个物体。再次，最明显、直接的方式来实现这将是迭代。
3. 每个目的地表面上的"地球"在你的编程模型将有被捕获并通过一些执行特定机制，对应对象的需要插入一个有序列作为一个结果。

考虑到该问题还引入了额外的并发症。问问你自己这样的：有多高你需要的位置这些目的开始？很显然足够高，以便最大的一个实际上 瀑布;即，远离地球的半径最大的对象。但是你怎么知道那是什么？你会需要首先确定最大的目的在收集；这又会(可能)需要重复.此外，人们可能想象这个模拟可能是多线程，以试图以模拟现实时的行为这一概念的对象 实际上 下降;但是然后你会发现自己试图添加项目的收集(操作这显然需要一个非零的时间量)可能同时，新的冲突正在检测。因此，这将创造线的问题。

总之，我无法想象如何这一想法能够得到适当实施，只是采用面向对象没有特别的硬件。这就是说，这真的 是 一个好主意。它提醒我，事实上， 珠的排序-一个算法，虽然不同作为你的想法，也是一个排序的解决方案，利用非常理的概念引力并不令人惊讶的是，需要专门的硬件。

Answer 2

您刚刚重申了问题。计算的引力效果的顺序都会有，充其量的排序算法的啊，你正在试图击败。

Answer 3

万有引力计算是免费仅在现实世界中的电荷。在PROGRAMM你需要建模。这将是在复杂性最小另一N

Answer 4

通用排序可证明是充其量为O（n log n）的。为了改善这一点，你必须知道一些关于数据的其他不仅仅是如何比较值。

如果这些值的所有数值，基数排序给出为O（n）假设你有上部和用于数字下界。该方法可以扩展到处理任何数量的 - 并且最终，在计算机中的所有数据都用数字来表示。例如，你可以通过基数排序字符串，在各道次，由一个字符排序，好像它是一个数字。

不幸的是，处理的数据的装置通过基数排序使得可变遍数可变大小。你为O（N日志m），其中m为最大值（因为k位给您的（2 ^ k）的值-1为无符号，一半为签约）结束。例如，如果要排序的整数从0到m-1，以及 - 你实际上得到为O（n log n）的再次

。

翻译一个问题到另一个可以是一个非常好的方法，但有时它只是增加了另一层复杂性和开销。

Answer 5

这个想法看似简单，但在现实世界和模拟一个在这种情况下之间的区别是，在现实世界中一切都是并行发生。为你描述你将不得不通过思考每一个对象在一个单独的线程与线程安全的方式将它们添加到他们完成的顺序列表，开始模拟重力排序。现实中的排序性能方面你可能只需要使用的时候快速排序，或者因为它们是在同距离下降的速率。但是，如果你的公式是成正比的质量，你只是跳过所有和排序的质量。

Answer 6

在一个虚构的“引力计算机”这种排序将采取O（1）的解决。但与真正的电脑就像我们知道它，你的思想外侧不会帮助。

Answer 7

一旦你计算出他们采取击中地面的任何时候，你仍然必须为这些值排序。你不是真的得到什么，你执行一些额外的不必要的计算后，只是排序不同的号码。

修改：糟糕。忘记物理学101.他们当然会全部命中在同一时间。 ：）

任何种类的类似这样的建模只是把一种排序问题转化为另一个。你不会得到任何东西。

Answer 8

忽略其他人都已经提到的所有缺陷，这主要归结为一个O(n^2)算法，不O(n)。你必须遍历所有的“领域”，找到“最重”或“最大”之一，然后将其推到一个列表，然后用清水冲洗，重复。即，找到第一个落地的一个，你必须遍历整个列表，如果它是最后一个，它会采取O(n)一次，第二次就可能采取O(n-1)，等...但更糟糕的是，你必须每次只进行了一堆数学运算来计算一些无用的“时间”值时，你可以对你摆在首位有兴趣的值进行排序。

Answer 9

Hmmmm。重力排序。

无视重力您的具体模式是错误的，让我们看到这个想法需要我们。

物理现实具有10 ^ 80处理器。

排序的实际下限是已知的日志（N），如果你有N / 2个处理器进行排序n个对象。

如果您有几个可用的CPU内核没有任何理由，你不能在多个线程运行归并。

Answer 10

有实际上是被称为意大利面条种类相当有名的排序算法这是那种与你相似。 您可以检查出一些它在网络上的众多分析。例如在 cstheory

Answer 11

这应该是肯定只有你应该支持它合适的硬件。否则，这听起来是一个很酷的想法。希望有人提供了一个IEEE纸，使这个乱七八糟的梦显现。

Answer 12

我爱的想法！这是聪明的。虽然是别人说的话是一般的正确，在为O（n log n）的结合是一种可证明降低对一般的排序问题的约束，我们需要牢记，即下界仅对于比较基于模型真。你所建议这里是一个不同的模型完全，但它确实值得我们进一步思考。

此外，由于詹姆斯和矩阵人士指出，较重的一个不移动比更轻的速度更快，你显然需要对模型适应一些地方较重的物体（数）的确会跑得更快/更（或慢/更少进一步），这样就可以以某种方式区分编号（离心机想到以及）。

需要更多的思考，但你的想法是犀利！

（编辑） 现在看看恩里克的Phys2D的想法，我想有很多更多的感觉。

有一两件事，我建议是绝对忽略效率方面现在。 （我知道，我知道这是整个目标）。它是一种新的模式，我们首先需要弥合及其实现的想法之间的差距。只有这样我们才能理解什么时间复杂度甚至对这种模式的手段。

Answer 13

我认为这个问题可以这样做简单：你要放球的底部在不同高度，这样，当在相同的比重下降最大的将首先撞击地面，第二大第二，等等，这是本质相当于用行，而不是球......在这种情况下，你只能说heightOffTheGround = MAX_VALUE - 质谱

您也不需要大约随着时间的推移加速的担心......既然你不关心他们是如何快速去还是逼真的物理，你可以给他们所有的初始速度X，并从那里走。

问题是那时，我们已经基本上只是重述问题并解决它像这样（伪）：

int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
    foreach (currentArrayValue in sortedArray)
    {
        if (iVal = current array value
        {
            put it in my sortedArray
            remove the value from my unsortedArray
        }
    }
    if (unsortedArray is empty)
    {
        break;  // from while loop
    } 
    iVal--
}

问题是，要运行的物理引擎，你在每个时间单位得到了迭代，这将是O（1）...用非常大的常...增量值的恒定数目，该系统将运行。其缺点是，对于很大部分这些增量值，你基本上将越来越没有接近的答案：在任何给定的迭代，很可能所有的领域/线/不管将陆续...但没有会打。

您可以尝试，只是说，好吧，让我们跳过了很多中间步骤，只是向前跳，直到一个命中！但是，这意味着你必须知道哪一个是最大的......你又回到了排序问题。

Answer 14

我会适应你的想法一点点。我们也有我们的对象，但他们不重量不同，但在速度上。所以，一开始所有对象在起跑线上，并在开始拍摄对齐，他们将所有移动各自的速度到终点。

清除足够：在结束第一个对象将发出一个信号，并称它是存在的。您捕捉信号，并写入到结果文件到底是谁。

好了，所以你要来模拟。

我们把你的字段的长度为L=1。随着步长∆t每个N的对象移动vᵢ∙∆t的长度在一个时间。 这意味着每个对象需要在到达终点之前sᵢ = L / (vᵢ∙∆t)步骤。

的一点是，现在，为了有非常密切的速度的两个对象之间的区别，你需要为你所有的物体不同的步长。

现在，在最好的情况下，这意味着，物体1点结束在一个步骤中，对象2在2等。因此，步骤的总数是S = 1 + 2 + … + N = N∙(N + 1)/2。这是为了N∙N的。

如果它不是最好的情况和速度是不是同样接近对方，你必须降低步长和效果迭代很多倍。

Answer 15

如果一台计算机将被建立，基于某些标准排序对象（这是不完全荒谬的思考），那么我相信复杂的顺序就什么都没有做对象的数量，而是率局部加速度的重力加速度。假设它是在地球建模，复杂度将是O（克<子> 0 ）其中g <子> 0 是：

在简单的理由是，球形物体(n)的数目是不相关的，如果它们的中心在开始对齐。此外，由于重力的加速度会比高度本身，因为它增加了更大的影响。举例来说，如果我们用10倍提高所有物体的高度，就不会带他们10X摔到地上，但少得多的时间。这包括各种可忽略的近似值作为加速度实际上依赖于两个对象之间的距离，但是我们更感兴趣的是一个更大的图片，而不是一个特定的值，该值可以被忽略。

这主意仍然

另外，我爱硬币分类视频张贴由@Jeremy。最后的对象化倾向将是我最不担心在建立这样的机器。更多关于它的思考，这是我愚蠢的两分钱打造这样一台机器：

<击> O 0 o O o

. . . . .
. . . . .
. . . . .
= = = = =

所有对象都是变化的大小成比例，我们想通过排序标准的。它们最初由细杆水平地保持在一起，通过各球体的中心运行。底部的=特别设计，只要他们碰撞球体记录的值（可选的位置）的地方。各个领域发生了碰撞后，我们将根据记录的值有我们的排序顺序。

Answer 16

  

Debilski的回答：

     

我会适应你的想法一点点。我们的确是   有我们的对象，但他们没有什么不同   在重量，但在速度上。因此，在   开头的所有对象的对齐   在出发的起跑线上   出手，他们都会有自己的移动   各自的速度到终点。

     

清除足够：在结束第一个对象   将发出信号，称这是   那里。您捕捉信号和写   到的结果纸谁是

我的工序进一步简化其说这些对象是随机正整数。我们希望当他们接近零对他们进行排序按升序，使他们具有的距离的从零d最初等于整数本身。

假设模拟发生在离散时间步即帧，在每个帧中，每一个对象的新的距离将是：d = d - v并且当其d ≤ 0对象将得到添加到列表中。这是一个减法和一个条件。对于每个对象的两个分立的步骤，以便计算似乎是为O（n）：线性

美中不足的是，它是线性的对的一帧仅！它是由帧数成倍f需要完成。仿真本身是O（NF）：二次

然而，如果我们取一个帧的持续时间作为参数t我们得到以影响成反比方式帧f的数目的能力。我们可以增加t减少f但这是以精度为代价，我们更增加t，更多的是两个对象将因此被列为相当于同一时间内完成，即使它们的概率不大。因此，我们得到具有可调节的精度的算法（因为它是在大多数有限元模拟上下文）

我们还可以通过将其转换成自适应+递归算法细化此。在人类的代码将是：

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

我不知道是否有任何真正的类似的实现，为的人。

工作

有趣的受试者确实：）

PS。上面的伪代码是我的伪代码的想法，请随时改写它在一个更清晰或符合的方式，如果有一个。的

Answer 17

几个星期前，我在想同样的事情。

我认为使用 Phys2D 库来实现它。这可能是不切实际的，但只是为了好玩。你也可以指定负权重的对象来表示负数。随着phys2d库可以定义重力使负重量的物体会去屋顶和对象与积极的体重会掉下来。然后安排在地板和屋顶与地板和屋顶之间的距离相等的中间的所有对象。假设有长度=对象的数目的所得阵列 - [R []。然后每次一个对象触摸屋顶你在阵列R [0]的开头添加它，并增加计数器，下一次对象触摸你在r添加它的屋顶[1]，每次一个对象到达地板你在阵列[R [r.length-1]，下一次的你在r [r.length-2]中添加它的结束添加。在未移动末端对象（停留浮在中间）可以在阵列的中间加入（这些对象是0的）。

这是效率不高，但可以帮你实现你的想法。

Answer 18

1. 我相信这是很好的提/参考： 是什么关系 之间的P与NP和大自然的能力，以解决NP问题 有效？ 排序 O(nlog(n)), 为什么不试图解决NP难问题？
2. 通过物理定律的目的下降比例的 重力常数 质量可以忽略不计。
3. 模拟一个物理过程可能会影响的实际时间的复杂性。

Answer 19

分析： （1）球的所有中心都在开始对齐 （2）更大数目==>质量更高==>半径大==>到地面的距离下 （3）在“真空”相同的加速度=相同的速度演进==>为中心==相同距离>如何更大德半径...较早球体将如何撞到地面 ==>概念OK，良好的物理技术，如果当一个球砸在地面上就可以发送鉴定中信号+命中的时间...至极会给排序列表 实际上...不是一个“好”的数字技术