Subato 309/Mergesort

Resource Files

Mergesort

Implementieren Sie (aufsteigenden) Mergesort in Java.
Führen Sie die Methode runTest() für Array-Größen von 1.000 bis 10.000.000 durch und zeichnen Sie die Laufzeit auf. Erkennen Sie dass das Verfahren eine deutlich geringere Komplexität als $\Theta(n^2)$ besitzt?
Ist Ihre Implementierung stabil? Begründen Sie warum. Schlagen Sie eine Änderung vor, die das Verfahren instabil (falls es stabil ist) oder stabil (falls es instabil ist) macht.

Fold all Unfold all Fullscreen Settings Help

package de.hsrm.ads; import java.util.Random; public class MergeSort { // buffer for merge operation. int[] b; public void sort(int[] a) { // FIXME } public static void swap(int[] a, int pos1, int pos2) { int tmp = a[pos1]; a[pos1] = a[pos2]; a[pos2] = tmp; } // always the same pseudo random numbers! private static final Integer DEFAULT_SEED = Integer.valueOf(654321); public static int[] createRandomArray(int n) { int[] a = new int[n]; for (int i=0; i<n; ++i) a[i] = i; // shuffle randomly. Random rand = new Random(DEFAULT_SEED*n); for (int i=0; i<n; ++i) { int pos = rand.nextInt(n); swap(a, i, pos); } return a; } public static void runTest(int n) { long startTime; long endTime; int[] a = createRandomArray(n); MergeSort sort = new MergeSort(); startTime = System.currentTimeMillis(); sort.sort(a); endTime = System.currentTimeMillis(); System.out.format( "[n=%d] : %d ms.\n", n, (endTime - startTime)); } public static void main(String[] args) { } }

java

package de.hsrm.ads;

import java.util.Random;

public class MergeSort {

// buffer for merge operation.
	int[] b;
	
	public void sort(int[] a) {
		// FIXME
	}
	
	public static void swap(int[] a, int pos1, int pos2) {
		int tmp = a[pos1];
		a[pos1] = a[pos2];
		a[pos2] = tmp;
	}

// always the same pseudo random numbers!
	private static final Integer DEFAULT_SEED = Integer.valueOf(654321);

public static int[] createRandomArray(int n) {
		int[] a = new int[n];
		for (int i=0; i<n; ++i) 
			a[i] = i;
		// shuffle randomly.
		Random rand = new Random(DEFAULT_SEED*n); 
		for (int i=0; i<n; ++i) {
			int pos = rand.nextInt(n);
			swap(a, i, pos);
		}
		return a;
	}

public static void runTest(int n) {

long startTime;
		long endTime;

int[] a = createRandomArray(n);
		MergeSort sort = new MergeSort();
		startTime = System.currentTimeMillis();
		sort.sort(a);
		endTime = System.currentTimeMillis();
		System.out.format(
				"[n=%d] : %d ms.\n",
				n, (endTime - startTime));
	}

public static void main(String[] args) {
	}
	
}

You are not logged in and therefore you cannot submit a solution.