Collections Generisches MergeSort mit Arrays

[transdenzentral]

Hallo Leute,

ich bin grad dabei ein generisches MergeSort mit Arrays zu schreiben. Folgenden Code habe ich mir bisher zusammengebaut.

Mir ist schon klar, dass man eigentlich solche Sortieralgorithmen nicht selber schreibt, aber in Vorbereitung auf eine anstehende Klausur ist das unumgänglich.

package sort;

import java.util.Arrays;

public class Sort {

/**
	 * 
	 * @param array
	 * @see [url=http://www.youtube.com/watch?v=XaqR3G_NVoo]Merge-sort with Transylvanian-saxon (German) folk dance - YouTube[/url]
	 * @return
	 */
	public static <T extends Comparable<T>> T[] mergeSort(T[] array) {
		if (array.length == 1) {
			return array;
		}
		T[] arrayLeft = mergeSort(Arrays
				.copyOfRange(array, 0, array.length / 2));
		T[] arrayRight = mergeSort(Arrays.copyOfRange(array, array.length / 2,
				array.length));

		return merge(arrayLeft, arrayRight);

	}

	private static <T extends Comparable<T>> T[] merge(T[] arrayLeft,
			T[] arrayRight) {
		@SuppressWarnings("unchecked")
		T[] array = (T[]) new Comparable[arrayLeft.length + arrayRight.length];

		int pointerRight = 0;
		int pointerLeft = 0;
		int result = 0;

		while (pointerLeft < arrayLeft.length
				|| pointerRight < arrayRight.length) {

			if (pointerLeft >= arrayLeft.length) {
				for (T t : Arrays.copyOfRange(arrayRight, pointerRight,
						arrayRight.length)) {
					array[result] = t;
					result++;
					pointerRight++;
				}
			} else if (pointerRight >= arrayRight.length) {
				for (T t : Arrays.copyOfRange(arrayLeft, pointerLeft,
						arrayLeft.length)) {
					array[result] = t;
					result++;
					pointerLeft++;
				}
			} else {
				if (arrayLeft[pointerLeft].compareTo(arrayRight[pointerRight]) < 0) {
					array[result] = arrayLeft[pointerLeft];
					pointerLeft++;
				} else {
					array[result] = arrayRight[pointerRight];
					pointerRight++;
				}
				result++;
			}

		}
		return array;

	}

}

Als Test habe ich folgende JUnit Klasse gebaut:

package test;

import static org.junit.Assert.assertTrue;

import java.util.Random;

import org.junit.After;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;

import sort.Sort;

public class TestSort {

	private static Integer[] array;
	private static Integer[] workingCopy;

	@BeforeClass
	public static void initial() {
		Random random = new Random();
		array = new Integer[4];
		for (int i = 0; i < array.length; i++) {
			array[i] = random.nextInt(100);
		}

	}

	@Before
	public void setUp() {
		workingCopy = array.clone();
		Sort.print(workingCopy);
	}
	

	@Test
	public void mergeSort() {
		workingCopy = Sort.mergeSort(workingCopy);		
		assertTrue(isSorted(workingCopy));
	}

	@After
	public void tearDown() {
		Sort.print(workingCopy);
		workingCopy = null;
	}

	public boolean isSorted(Integer[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			if (array[i + 1].compareTo(array[i]) < 0) {
				return false;
			}
		}
		return true;

	}

}

Ich hab mich jetzt eine Zeit lang mit dem Debugger in Eclipse abgemüht und herausgefunden, dass mein Algorithmus prinzipiell funktioniert und mir das übergebene Array richtig sortiert. Aber im TestCase kracht es dann bei jedem Durchlauf. Casten funktioniert nicht. Wie kann ich das besser machen bzw. hinbiegen, dass der Test auch tatsächlich positiv durchläuft (es IST ja sortiert).

Viele Grüße & Vielen Dank,
Hoffe Ihr könnt mir helfen

transdenzentral

 

[nillehammer]

Ich weiß nicht, ob das schon der Fehler ist, aber in der Methode isSorted in Deinem Test ist ein kleiner Fehler drinnen:

  if (array[i + 1].compareTo(array[i]) < 0) {
      return false;
  }

Der Code funktioniert nur, wenn das zu prüfende Array keine Doubletten enthält. Auch bei Benutzung von Random (siehe die Vorbereitung deines Tests) kann es aber passieren, dass es Doubletten gibt. Ich meine, es müsste so richtig sein:

  if (array[i + 1].compareTo(array[i]) <= 0) {
      return false;
  }

[EDIT]
Ach ja, und nach dem Du mit array[i + 1].compareTo(array) auf dem größeren Integer das compareTo aufrufst, müsste es dann natürlich noch >= statt <= sein!
[/EDIT]

 

[transdenzentral]

Danke für den Hinweis, nillehammer.

Allerdings liegt darin nicht der eigentliche Fehler wie ich grade testweise sicher gestellt habe.

Die Exception fliegt trotzdem.

 

[nillehammer]

Ich hab grad noch was nacheditiert (siehe meine letzte Anwort)

 

[transdenzentral]

Ich glaube, dass es "<=" sein muss - bin ich mir sogar ziemlich sicher (auch wenn mich die compareTo() öfters verwirrt).
Für die anderen Sortierverfahen (Quellcode hier nicht mit reingepackt) läuft die Testmethode sauber durch. (Ingieneursinduktion...)

Ist wie gesagt aber nicht mein eigentliches Problem. Das Problem ist die ClassCastException, in Zeile 38.

 

[SlaterB]

hier ein kürzeres Programm mit denselben Problem:

public class Test {
    public static void main(String[] args)    {
        Integer[] k = new Integer[4];
        k = mergeSort(k);
    }

    public static <T extends Comparable<T>>T[] mergeSort(T[] array)  {
        @SuppressWarnings("unchecked")
        T[] array2 = (T[])new Comparable[4];
        return array2;
    }
}

Arrays und Generics sind nunmal nicht so gut zu verweben,

dass ein zurückgegebenes Comparable[] nicht zum Typ Integer[] passt liegt auf der Hand,
du könntest Comparable[] als Datentypen im Test verwenden, auch recht offensichtlich,
allzu störend kann das im Moment auch nicht sein

 

[transdenzentral]

Manchmal sieht man den Wald vor lauter Generics nicht

Danke SlaterB.
Auf diese Weise klappt alles super! Hätte man auch drauf kommen können...

 

[nillehammer]

Ist wie gesagt aber nicht mein eigentliches Problem. Das Problem ist die ClassCastException, in Zeile 38.

Sorry, hab gedacht, es geht um den Testdurchlauf. Dass Dein eigentliches Problem eine ClassCastException war, hab ich beim Durchlesen Deiner Ursprungsfrage einfach nicht geblickt. (Obwohl's da stand und man es bei genauer Quellcodelektüre auch hätte sehen können )