获取mergesort-tree的高度

I have an implementation of the mergesort algorithm. How do I calculate the height of the tree?

我有mergesort算法的实现。如何计算树的高度?

So far I can get the number of recursive calls, but not the height of the tree:

到目前为止,我可以获得递归调用的数量,但不能获得树的高度:

static int swaps=0;
static long comparisons=0;
static int recursionsdepth=0;

public static int[] sort(int[] array) {

    recursionsdepth++;
    if (array.length > 1) {

        int middle = (int)(array.length / 2);

        int[] left = new int[middle];
        for (int i = 0; i <= left.length - 1; i++) {
            left[i] = array[i];
        }

        int[] right = new int[array.length - middle];
        for (int i = middle; i <= array.length - 1; i++) {
            right[i - middle] = array[i];
        }

        left = sort(left);
        right = sort(right);

        return merge(left, right);
    }
    else
    {  
        recursionsdepth--;
        return array;
    }
}

For {1,5,7,9} the recursive calls are 3 ( 1 for {1,5,7,9} ,1 for {1,5} and 1 for {7,9}), but the height of the tree is 2.

对于{1,5,7,9},递归调用为3({1,5,7,9}为1,{1,5}为1,{7,9}为1),但是高度为树是2。

1 个解决方案

#1

Merge Sort repeatedly divides the array into two equal (almost) parts as long as the array size is greater than 1. It doesn't care about the initial state of the array, i.e. it would do so even if the array is already sorted. Now, there is only one way to do so for any given array of length n. And therefore, the height of the merge-sort tree will be constant with respect to n. That is the height will be ceil(log n) where base is 2. You don't need to actually run your program to find this out.

只要数组大小大于1,Merge Sort就会重复地将数组划分为两个相等(几乎)的部分。它不关心数组的初始状态,即即使数组已经排序也会这样做。现在,对于任何长度为n的给定数组,只有一种方法可以实现。因此,合并排序树的高度相对于n是恒定的。这是高度将是ceil(log n),其中base是2.你不需要实际运行你的程序来找到它。

Since the OP is hell-bent on calculating the height while actually running the sorting code, here it is:

由于在实际运行排序代码时,OP在计算高度时非常弯曲,这里是:

Pass an additional variable to the sort function that would store the depth of the current node. And use a global variable to store the maximum depth that has been achieved until now. Below code is slight modification of the one posted in the question:

将另一个变量传递给sort函数,该函数将存储当前节点的深度。并使用全局变量来存储迄今为止已实现的最大深度。下面的代码稍微修改了问题中的帖子:

static int swaps=0;
static long comparisons=0;
static int recursionsdepth=0;

public static int[] sort(int[] array, int depth) { // at first call depth = 0

    recursiondepth = Math.max(recursiondepth, depth);
    if (array.length > 1) {

        int middle = (int)(array.length / 2);

        int[] left = new int[middle];
        for (int i = 0; i <= left.length - 1; i++) {
            left[i] = array[i];
        }

        int[] right = new int[array.length - middle];
        for (int i = middle; i <= array.length - 1; i++) {
            right[i - middle] = array[i];
        }

        left = sort(left, depth+1);
        right = sort(right, depth+1);

        return merge(left, right);
    }
    else
    {  
        return array;
    }
}