import java.util.Comparator;
import java.util.Random;

public class Median{

    private static void vertauschen(Object[] daten, int i, int j){
	Object hilf = daten[i];
	daten[i] = daten[j];
	daten[j] = hilf;
    }

    // eigentlich private, dann aber nicht zu testen
    static int zufaelligAufteilen(Object[] daten, Comparator vgl,
					 int links, int rechts, Random gen){
	int stelle = links + gen.nextInt(rechts - links + 1);
	vertauschen(daten, links, stelle);
	return Sort.partition(daten, links, rechts, daten[links], vgl);

    }


    // ordnungszahl bei 0 beginnen lassen für kleinstes Element
    public static Object auswaehlen(Object[] daten, Comparator vgl,
				  int links, int rechts, int ordnungszahl){
	Random gen = new Random();
	return auswaehlen(daten, vgl, links, rechts, ordnungszahl, gen);
    }

    /* die rekursive Methode braucht einen Zufallszahlengenerator und darf
       ihn nicht bei jedem rekursiven Aufruf initialisieren */
    private static Object auswaehlen(Object[] daten, Comparator vgl,
				  int links, int rechts, int ordnungszahl,
				  Random gen){
	if (links == rechts && ordnungszahl == 0) return daten[links];
	int stelle = zufaelligAufteilen(daten, vgl, links, rechts, gen);
	if (ordnungszahl <= stelle - links){
	    return auswaehlen(daten, vgl, links, stelle, ordnungszahl, gen);
	}
	else{
	    return auswaehlen(daten, vgl, stelle+1, rechts,
		       ordnungszahl - (stelle - links + 1), gen);
	}


    }
	

    public static Object median(Object[] daten, Comparator vgl){
	int laenge = daten.length;
	int ordnungszahl = laenge/2;
	return auswaehlen(daten, vgl, 0, laenge-1, ordnungszahl);

    }


}