Quicksort, #Vergleiche zählen klappt nicht

[Aticus]

Hallo zusammen,

schreibe grade an dem guten alten Quicksort, diesmal für das Sortieren eines eindimensionalen Arrays von Objekten, des Typs Objekte...soweit so gut: schicke Array rein, kommt sortiert raus.
Mein Problem ist, dass ich die Anzahl der Vergleiche der Objekte untereinander zählen möchte.
Als Wert für zB 8 Elemente bekam ich teills 10 Vergleiche zurück...aber da untere Schranke (soweit ich weiß) n*log(n) ist, muss bei mir irgendwo was falsch laufen.
Das Problem tritt bei mir sowohl für eine Random wahl des Pivots als auch für Wahl des mittleren Elements als Pivot auf. Wobei die Werte für Random schlimmer aussehen...was insofern wenig Sinn macht, da es kopierter code mit lediglicher Änderung der Pivot Strategie ist.

Zum zählen habe ich jeweils ausserhalb der Methode einen Counter initialisiert, damit die Rekursion nicht rumfuscht.
Und unmittelbar bevor ein Vergleich kommt, zähle ich hoch, aber i-wie tuts das nicht.
Hoffe ihr könnt mir helfen:

public class Sorter {
//hier startet quick mit mittlerem Pivot
static int vergleichequickmid=0;
public static int quickmidsort (int UntereGrenze, int ObereGrenze,Objekte[] objektsammlung)
{
int links = UntereGrenze;
int rechts = ObereGrenze;
Objekte Pivotelement = objektsammlung[((UntereGrenze+ObereGrenze) / 2)]; //Pivotstrategie
do
{
while (++vergleichequickmid>-1 && Pivotelement.compareTo(objektsammlung[links])>0) //hier zähle ich mit
links = links + 1 ;
while (++vergleichequickmid>-1 && objektsammlung[rechts].compareTo(Pivotelement)>0) //ebenso hier
rechts = rechts - 1;
if (links <= rechts)
{
//Vertauschen der Elemente
Objekte Merke = objektsammlung[links];
objektsammlung[links] = objektsammlung[rechts];
objektsammlung[rechts] = Merke;
links = links + 1;
rechts = rechts - 1;
}
} while (links <= rechts);
if (UntereGrenze < rechts)
quickmidsort(UntereGrenze, rechts, objektsammlung); //Rekursion
if (links < ObereGrenze)
quickmidsort(links, ObereGrenze, objektsammlung); //Rekursion
return vergleichequickmid;}







//Hier startet es mit randomsort
static int vergleichequickrand=0; //der counter
public static int quickrandsort (int UntereGrenze, int ObereGrenze,Objekte[] objektsammlung)
{
int links = UntereGrenze;
int rechts = ObereGrenze;
Objekte Pivotelement = objektsammlung[UntereGrenze+ rnd.nextInt(ObereGrenze-UntereGrenze)]; //Pivotstrategie
do
{
while (++vergleichequickrand>-1 && Pivotelement.compareTo(objektsammlung[links])>0) //hier zähle ich
links = links + 1 ;
while (++vergleichequickrand>-1 && objektsammlung[rechts].compareTo(Pivotelement)>0)//ebenso wie hier
rechts = rechts - 1;
if (links <= rechts)
{
//Vertauschen der Elemente
Objekte Merke = objektsammlung[links];
objektsammlung[links] = objektsammlung[rechts];
objektsammlung[rechts] = Merke;
links = links + 1;
rechts = rechts - 1;
}
} while (links <= rechts);
if (UntereGrenze < rechts)
quickmidsort(UntereGrenze, rechts, objektsammlung); //Rekursion
if (links < ObereGrenze)
quickmidsort(links, ObereGrenze, objektsammlung); //Rekursion
return vergleichequickrand;}

    private static java.util.Random rnd = new java.util.Random();
}

greetz
Aticus

 

[SlaterB]

in quickrandsort rufst du rekursiv quickmidsort auf statt wieder quickrandsort ,

auch statische Zählvariable könnte falsch verwendet werden,
am besten getrennte Klassen verwenden, mit jeweils eigenen oder geerbten Variablen/ Methoden,
dann kann das kaum mehr passieren

wie man es hätte herausfinden können:
System.out.println("call qrs: "+vergleichequickrand+", "+UntereGrenze+" - "+ObereGrenze);
zu Beginn von quickrandsort, mehr muss man gar nicht tun,
außer dann zu erkennen 'nur eine Ausgabe? hmm, gibts denn keine Rekursion?'

 

[Marco13]

Hab bei einem Test mit 8 (schon sortierten!) Elementen jetzt auch eher so um die 20 Vergleiche raus, aber das kann auch an den Änderungen liegen...

// Modified from [url]http://www.java-forum.org/java-basics-anfaenger-themen/
92162-quicksort-vergleiche-zaehlen-klappt.html[/url]

class Sorter
{
    public static void main(String args[])
    {
        int n = 8;
        Objekte array[] = new Objekte[n];
        for (int i=0; i<n; i++)
        {
            array[i] = new Objekte(i);
        }

        pivotSelector = new MidPivotSelector();
        System.out.println(quicksort(array));

        pivotSelector = new RandomPivotSelector();
        System.out.println(quicksort(array));


    }

    static int vergleichequick = 0;
    private static java.util.Random rnd = new java.util.Random();
    private static PivotSelector pivotSelector = new MidPivotSelector();

    public static int quicksort(Objekte[] objektsammlung)
    {
        vergleichequick = 0;
        return quicksort(0,objektsammlung.length-1,objektsammlung);
    }
    private static int quicksort(int UntereGrenze, int ObereGrenze,
        Objekte[] objektsammlung)
    {
        int links = UntereGrenze;
        int rechts = ObereGrenze;
        Objekte Pivotelement = pivotSelector.select(
            objektsammlung, UntereGrenze, ObereGrenze); // Pivotstrategie
        do
        {
            while (compare(Pivotelement, objektsammlung[links]) > 0)
                // hier zähle ich mit
                links = links + 1;
            while (compare(objektsammlung[rechts], Pivotelement) > 0)
                // ebenso hier
                rechts = rechts - 1;
            if (links <= rechts)
            {
                // Vertauschen der Elemente
                Objekte Merke = objektsammlung[links];
                objektsammlung[links] = objektsammlung[rechts];
                objektsammlung[rechts] = Merke;
                links = links + 1;
                rechts = rechts - 1;
            }
        }
        while (links <= rechts);
        if (UntereGrenze < rechts)
            quicksort(UntereGrenze, rechts, objektsammlung); // Rekursion
        if (links < ObereGrenze)
            quicksort(links, ObereGrenze, objektsammlung); // Rekursion
        return vergleichequick;
    }

    private static int compare(Objekte a, Objekte b)
    {
        vergleichequick++;
        return a.compareTo(b);
    }



    static class Objekte implements Comparable<Objekte>
    {
        private int n;

        public Objekte(int n)
        {
            this.n = n;
        }

        @Override
        public int compareTo(Objekte o)
        {
            return n-o.n;
        }
    }

    static interface PivotSelector
    {
        <T> T select(T t[], int min, int max);
    }

    static class MidPivotSelector implements PivotSelector
    {
        public <T> T select(T[] t, int min, int max)
        {
            return t[(min+max) / 2];
        }
    }

    static class RandomPivotSelector implements PivotSelector
    {
        public <T> T select(T[] t, int min, int max)
        {
            return t[min+rnd.nextInt(max-min)];
        }
    }

}

 

[Aticus]

Ich bin mir nach deinem Post nicht ganz sicher, ob ich lachen oder weinen soll. Das Problem in meinem Code lässt sich extrem leicht beheben (*Juche*) aber ich habe diesen dummen Fehler die ganze Zeit übersehen (*schluchz*) ...copy paste halt...

Der static counter nervt im mom wirklich noch etwas, aber das soll nicht deine Sorge sein.

Unterm Strich ganz herzlichen Dank für die schnelle Hilfe!!!

greetz
Aticus

edit:Hey Marco, wollte dich nicht übergehen, wir haben wohl schlichtweg gleichzeitig rumgetippert, auch dir danke für Mühe und Hilfe