归并初学者问题 [英] mergesort beginner question

问题描述

亲爱的朋友们， 我现在已经在原来的算法在归并algorithm.Because的问题，要排序的名单diveded分成两个子列表和排序递归。 现在怎么样我想lengh列表划分n为进lengh N / 3的3分名单，然后这三个子表递归排序，然后结合？ 我只是简单地修改原来的算法，通过更换everwhere 2成3，怀疑是有道理的。

Dear all, I now have a question on Mergesort algorithm.Because in the original algorithm,the list to be sorted is diveded into two sublists and sort recursively. Now how about I want to divide the list of lengh n into 3 sub-lists of lengh n/3,and then sort these three sublists recursively and then combine? I just simply modify the original algorithm by replacing everwhere 2 into a 3,wondered if that makes sense.

如何使它更普遍？我们可以把名单为K子列表和它们排序，并结合？

How about make it more general?Can we divide the lists into K sublists and sort them and combine?

感谢您分享您的想法对我来说。

Thank you for sharing your ideas for me.

推荐答案

如果你有N（N> 2）名单，重要的是你需要进行（N-1）的比较上的每个合成步骤是不正确的。然而，实现变得更加复杂。

If you have n (n > 2) lists, it is not true that you need to carry out (n-1) comparisons on every merging step. However, the implementation becomes more complex.

假设你有三个列表，列表[0..2] ，并承担为简单起见你合并他们，他们都还非空（即你有不运行的任何名单中的）的末端。假设还为简单起见，所有的元素都是不同的，即当你比较两个元素，他们是绝不相同。你有那么六种可能的状态中，你就可以了，而这在列表中的第一个元素的递增的顺序对应三个列表的六个排列，也就是说，如果

Suppose you have three lists, list[0..2], and assume for simplicity you are merging them and they are all still non-empty (i.e. you have not run to the end of any of the lists). Assume furthermore for simplicity that all elements are distinct, i.e. when you compare two elements they are never the same. You have then six possible "states" in which you can be, which correspond to the six permutations of the three lists in an increasing order of the first elements on the lists, i.e. if

list[0] = [5, 7, 11, 15]
list[1] = [3, 4, 20, 21]
list[2] = [9, 10, 12, 19]

然后列出相应的置换为[1，0，2]，即列表[1] 的至少前元素和名单[2] 具有最大的正面因素。

then the corresponding permutation of the lists is [1, 0, 2], i.e. list[1] has the least front element and list[2] has the greatest front element.

在现在流行的的下一个元素（4）名单[1] 您已经知道列表[0] .front ＆LT; 列表[2] .front 基于状态[1，0，2]你在哪里。所以，现在你需要执行1或2次比较：

When you now pop the next element (4) from list[1] you know already that list[0].front < list[2].front based on the state [1, 0, 2] where you were. So now you need to perform either 1 or 2 comparisons:

if (list[1].front < list[0].front) // (A)
   --> move to state [1, 0, 2], next to pop is list[1]
else if (list[1].front < list[2].front)
   --> move to state[0, 1, 2], next to pop is list[0]
else
   --> move state[0, 2, 1], next to pop is list[0]

假设某种一致性，即比较（A）返回true的概率，即是从中删除了previous元素列表中的下一个元素是小于最小元素在另外两个名单，是1/3，所以你对平均（1/3×1 + 2/3×2）= 5/3的比较，而不是2（这将是N-1）。

Assuming some kind of uniformity, the probability that the comparison (A) returns true, i.e. that the next element on the list from which you removed the previous element is less than the least element on the other two lists, is 1/3, so you have on the average (1/3 x 1 + 2/3 x 2) = 5/3 comparisons instead of 2 (which would be n-1).

这是每插入2/3比较正常的归并，只需要每弹出元件1相比明显恶化。

This is obviously worse by 2/3 comparisons per insert the normal mergesort which only needs 1 comparison per popped element.

我们可以通过考虑也部分有序的状态取得更好的成绩。有哪些可以由三个不同的比较（表[0] - 列表[1]，列表[1] - 列表[2]和列表[0] - 列表[2]）。 （？）;如果我们允许已知结果（小于;，＆GT），以与不知道被扩充，有以下可能的状态：

We can get a better result by considering also partially ordered states. There are three distinct comparisons which can be made (list[0] -- list[1], list[1] -- list[2] and list[0] -- list[2]). If we allow for the known results (<, >) to be augmented with "don't know" (?), there are the following possible states:

0/1  1/2  0/2
  <    <    <   (total order) [0,1,2]
  <    ?    <   (0 is least but don't know if 1 < 2) [0,1,2] [0,2,1]
  <    ?    ?   (0 is < 1, but 2 can't be positioned) [2,0,1] [0,2,1] [0,1,2]
  ?    ?    ?   (no information about ordering) (all six permutations)

然后把所有关于排列交换和LT的变种;对于＆GT;在矩阵中的不同的地方。

and then all the variants regarding permutations and swapping < for > at different places in the matrix.

现在，如果是在一个（小于，＆LT;，＆LT）状态（假设[0,1,2]），你看从你求婚了previous一个列表中的下一个元素，有有两种情况：要么（1）你是不是在列表中的元素下的元素[1]，在这种情况下，你又回到一个比较状态[0,1,2]或者你得到比上表[1]的元件更高的元件。在这种情况下，可以输出列表[1]下一页，你进入了一个（小于，＆LT;？）状态：你知道，列表[1]有至少前元素，但现在不知道，如果列表[0 ]或列表[2]是下

Now if were in a (<,<,<) state (assume [0,1,2]) and you read the next element from the list from which you popped the previous one, there are two cases: either (1) you get an element that is lower than the element on list[1], in which case you are back at state [0,1,2] in one comparison; or you get an element that is higher than the element on list[1]. In this case you can output list[1] next, and you have entered a (<,?,<) state: you know that list[1] has the least front element but don't know now if list[0] or list[2] is the next.

现在的（小于，＆LT;？）状态下，你看从列表中的新元素[1]，可以用1 +（1/3 + 4/3）= 1 5/3比较找到所有列表的实际排列，你会得到回（小于，＆LT;，＆LT）状态。因此，两推这一系列花费2 5/3比较，平均为1 5/6 = 11/6每个刀片;然而，因为可以插入由相同列表中的序列中的两个最低单元平均成本甚至更低，由相同的参数，因为它是前（1/3 + 2/3 x 11/6）= 6 /可能性18 + 22/18 = 1 + 5/9，比每个刀片有5/9的比较，但超过2/3以上的稍微好一些。原来归并差

Now in a (<,?,<) state you read a new element from list[1], you can use 1 + (1/3 + 4/3) = 1 5/3 comparisons to find the actual permutation of all the lists and you get back to a (<,<,<) state. Thus this sequence of two pushes cost 2 5/3 comparisons, for an average of 1 5/6 = 11/6 per insert; however because of the possibility that you can insert two lowest elements in a sequence from the same list the average cost is even less, by the same argument as before it is (1/3 + 2/3 x 11/6) = 6/18 + 22/18 = 1 + 5/9, worse than the original mergesort by 5/9 comparisons per insert but slightly better than 2/3 above.

有关完整性，这里的算法（示片段）：

For completeness, here the algorithm (fragment shown):

state_1_lt_2: /* known list[1].front < list[2].front */
  if (list[0].front < list[1].front):
    merge_from(0)
    goto state_1_lt_2 /* 1 insert 1 comp prob 1/3 */
  else
    merge_from(1)
    if (list[0].front < list[1].front)
      if (list[1].front < list[2].front)
        merge_from(0)
        goto state_1_lt_2 /* 2 inserts 3 comps prob 2/3*1/2*1/3 = 1/9 */
      else if (list[0].front < list[2].front)
        merge_from(0)
        goto state_2_lt_1 /* 2 inserts 4 comps prob 2/3*1/2*2/3*1/2 = 1/9 */
      else
        merge_from(2)
        goto state_0_lt_1 /* 2 inserts 4 comps prob 1/9 */
    else if (list[2].front < list[1].front)
      merge_from(2)
      goto state_1_lt_0 /* 2 inserts 3 comps 2/3 x 1/2 x 1/3 = 1/9 */
    else if (list[2].front < list[0].front)
      merge_from(1)
      goto state_2_lt_0 /* 2 inserts 4 comps prob 1/9 */
    else
      merge_from(1)
      goto state_0_lt_2 /* 2 inserts 4 comps prob 1/9 */

这总结了每个的插入比较的预期数量

This sums up to an expected number of comparisons per insert of

1/3 x 1 + 4/9 x (4/2) + 2/9 x (3/2) = 6/18 + 16/18 + 6/18 = 30/18 = 1 5/9.

这篇关于归并初学者问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！