mardi 3 novembre 2015

MergeSort - how do I sum up all recursive array calls?

I'm studying computer science and our current task is to program the merge-sort algorithm with an array length of 2^k (k = 1-16) and random numbers and each position. We have to output the runtime of this algorithm by summing up the length of all recursive array-calls.

Our teacher gave the following example: array length = 4: runtime = 2*2 + 4*1 = 8

My current logic is that every instance is nothing else but the length of the array and thats why I thought its enough to add the array.length after each recursive call. This however makes too many calls...

My output for array...

length 4: 4 8 12 (0...3)

length 8: 16 24 32 40 48 56 (0...7)

length 16: 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 (0...15)

One thing is clear, the output is always equal to the initial array length. I've made the correct values bold, these values should be the finial output... if I understand it correctly.

Can somebody help me with the runtime-calculation?

My Code:

Keep in mind that the intArr-size is typically not 16 [or 8, or 4] but "value" which is the 2^k reference. I've lowered the size in order to make it easier find out the failure in the runtime-calculation.

import java.util.Random;

public class Mergesort {

static int runtime;

Random generator = new Random();

static int base = 2;

static int potency = 1 + (int) (Math.random() * ((16)));

static int value = (int) java.lang.Math.pow(base, potency);

public static int[] intArr = new int[16];

{

    for (int i = 0; i < intArr.length; i++) {
        intArr[i] = generator.nextInt(100);
    }

}

public static void main(String[] args) {

    Mergesort ms = new Mergesort(); 
    int[] arr = ms.splitHalf(0, intArr.length - 1); 

    System.out.println("Mergesort-Algorithm" + "\n" + "\n" + "Position:" + " Wert");
    for (int i = 0; i < arr.length; i++) { 
        System.out.println(i + 1 + ": " + arr[i]);
    }
}

public int[] splitHalf(int l, int r) { 
    if (l < r) { 

        int q = (l + r) / 2;

        splitHalf(l, q); 
        splitHalf(q + 1, r); 
        merge(l, q, r); 

    }
    return intArr; 

}

private void merge(int l, int q, int r) { 

    int[] arr = new int[intArr.length];

    int left;
    int right;

    for (left = l; left <= q; left++) {
        arr[left] = intArr[left];
    }
    for (right = q + 1; right <= r; right++) {
        arr[r + q + 1 - right] = intArr[right];
    }
    left = l;
    right = r;
    for (int k = l; k <= r; k++) { 
        if (arr[left] <= arr[right]) { 
            intArr[k] = arr[left]; 
            left++; 
        } else {
            intArr[k] = arr[right]; 
            right--; 
        }

    }
    runtime = runtime + arr.length;
    System.out.println(runtime);

}

}




Aucun commentaire:

Enregistrer un commentaire