package Model;


/**
 * F&uuml;hrt die gew&uuml;nschten Laufzeittests durch.
 * 
 * @author ISB-Arbeitskreis, Umsetzungshilfen Informatik 12
 * @version 1.0
 */

public class TESTSORTIEREN
{
    /* Anzahl der Datenelemente in Liste und / oder Baum */
    private int anzahl;
    /* Erzeugerelement f&uuml;r die Schl&uuml;sselwerte */
    private GENERATOR g;
    /* Die Vergleichsanzahlen */
    private int anzahl1, anzahl2;
    /* Die Ausgangsdaten */
    private DATENELEMENT [] daten;

    /**
     * Legt die ben&ouml;tigten Objekte an und besetzt die Attributwerte.
     * @param anzahl Anzahl der zu sortierenden Datenelemente
     */
    public TESTSORTIEREN (int anzahl)
    {
        this. anzahl = anzahl;
        g = new GENERATOR (10);
        daten = new DATENELEMENT [anzahl];
        for (int i = 0; i < anzahl; i++)
        {
            daten [i] = new STRINGDATEN (g. BezeichnerGenerieren ());
        }
    }

    /**
     * Sortiert das gegebene Feld durch Auswahl des jeweils kleinsten Elements im unsortierten Rest.
     * @param d das zu sortierende Feld
     */
    private void Auswahlsort (DATENELEMENT [] d)
    {
        int pos;
        DATENELEMENT hilf;
        anzahl1 = 0;
        for (int i = 0; i < d. length - 1; i++)
        {
            pos = i;
            for (int j = i + 1; j < d. length; j++)
            {
                anzahl1 += 1;
                if (d [j]. Vergleichen (d [pos]) < 0)
                {
                    pos = j;
                }
            }
            hilf = d [i];
            d [i] = d [pos];
            d [pos] = hilf;
        }
    }

    /**
     * Sortiert den angegebenen Teilbereich des Feldes.
     * pre: beide Felder enthalten die Ausgangsdaten, da der Start nicht vorhersagbar ist.
     * @param von das Feld mit den Ausgangsdaten
     * @param nach das Feld mit den Zieldaten
     * @param minIndex der Index, ab dem sortiert werden soll
     * @param topIndex der Index, bis zu dem (ausschlie&szlig;lich) sortiert werden soll
     */
    private void Mischen (DATENELEMENT [] von, DATENELEMENT [] nach, int minIndex, int topIndex)
    {
        int mitte;
        int pos;
        int posUnten;
        int posOben;
        if (minIndex < topIndex - 1)
        {
            mitte = (minIndex + topIndex) / 2;
            Mischen (nach, von, minIndex, mitte);
            Mischen (nach, von, mitte, topIndex);
            posUnten = minIndex;
            posOben = mitte;
            pos = minIndex;
            while (pos < topIndex)
            {
                if (posUnten >= mitte)
                {
                    while (posOben < topIndex)
                    {
                        nach [pos] = von [posOben];
                        pos += 1;
                        posOben += 1;
                    }
                }
                else if (posOben >= topIndex)
                {
                    while (posUnten < mitte)
                    {
                        nach [pos] = von [posUnten];
                        pos += 1;
                        posUnten += 1;
                    }
                }
                else
                {
                    anzahl2 += 1;
                    if (((STRINGDATEN) von [posUnten]). Vergleichen (von [posOben]) <= 0)
                    {
                        nach [pos] = von [posUnten];
                        posUnten += 1;
                    }
                    else
                    {
                        nach [pos] = von [posOben];
                        posOben += 1;
                    }
                    pos += 1;
                }
            }
        }
    }
    
    /**
     * Sortiert das gegebene Feld durch Mischen immer l&auml;ngerer Teilfelder.
     * @param d das zu sortierende Feld
     */
    private void Mergesort (DATENELEMENT [] d)
    {
        DATENELEMENT [] nach;
        nach = d. clone ();
        anzahl2 = 0;
        Mischen (d, nach, 0, d. length);
        for (int i = 0; i < d. length; i++)
        {
            d [i] = nach [i];
        }
    }
    
    /**
     * Bestimmt die Vergleichsanzahlen.
     * @param auswahl gibt an, ob Sortiren durch Ausw&auml;hlen durchgef&uuml;hrt werden soll
     * @param merge gibt an, ob Sortiren durch Mischen durchgef&uuml;hrt werden soll
     */
    public void DurchschnittsTest (boolean auswahl, boolean merge)
    {
        if (auswahl)
        {
            Auswahlsort (daten. clone ());
        }
        if (merge)
        {
            Mergesort (daten. clone ());
        }
    }
    
    /**
     * Meldet die durchschnittliche Anzahl der Vergleiche f&uuml;r die Sortierung durch direktes Ausw&auml;hlen.
     * @return Suchzeit
     */
    public int AnzahlFuerAuswahlGeben ()
    {
        return anzahl1;
    }
    
    /**
     * Meldet die durchschnittliche Anzahl der Vergleiche f&uuml;r die Sortierung durch Mischen.
     * @return Suchzeit
     */
    public int AnzahlFuerMergesortGeben ()
    {
        return anzahl2;
    }
}
