# Pivot-Wahl beim QuickSort steigert die Effizienz, eine Lüge???



## deggit_biber (30. Jan 2017)

Hallo

Ich beschäftige mich gerade mit dem QuickSort genau gesagt mit der Wahl eines geeigneten Pivot-Elements zur Steigerung der Effizienz.

Soweit ich gelernt habe, trägt die Wahl des Pivot-Elements maßgeblich zur Effizienz des Algorithmus bei. Dies wollte ich einmal überprüfen, indem ich drei verschieden Varianten, die sich in ihrer Wahl des Pivot-Elements unterscheiden, programmiert habe.

Variante 1: quickSortLinks 
Immer das linke Element als Pivot nehmen

Variante 2: quickSortMitte

Immer ein Element aus der Mitte nehmen
Variante 3 quickSortRandom

Drei Werte Random aussuchen und dann das nehmen, welches vom Wert in der Mitte liegt.

Die Effizienz überprüfe ich mit einem einfachen Zähler, der Vergleiche. Alle drei Algorithmen laufen auf einem eigenen Array, welches aber von der Int-Wert Belegung identisch sind.

Zu meinem Erstaunen benötigen alle drei Algorithmen fast genau die gleiche Anzahl an vergleichen, um das Array zu sortieren.

Jetzt frage ich mich, habe ich etwas falsch gemacht?
- Zähler an der falschen stelle
- falscher QuickSort-Algorithmus? (Der Grund-Algo, stammt von dieser Seite: http://www.algolist.net/Algorithms/Sorting/Quicksort)
- wer weiß was… ;-)

Hier einmal der Code.

```
import java.util.Random;

/**
* Beschreiben Sie hier die Klasse Sortieren.
*
* @author (Ihr Name)
* @version (eine Versionsnummer oder ein Datum)
*/
public class QuickSortPivot
{
    int n;
    int vergleicheLinks=0, vergleicheMitte=0, vergleicheRandom=0;
   
    private int[] arr1;
    private int[] arr2;
    private int[] arr3;   

    /**
     * Konstruktor für Objekte der Klasse Sortieren
     *
     * @param pElemente Anzahl der zu sortierenden Elemente
     *
     */
    public QuickSortPivot(int pElemente)
    {    
        System.out.print('\u000C'); // Konsole leeren. 
        arr1 = new int[pElemente];
        arr2 = new int[pElemente];
        arr3 = new int[pElemente];

        arrayFuellen();
        arrayDuplizieren();

        System.out.println("Elemente des unsortierten Arrays:");
        arrayAusgebenLinks(arr1);
        System.out.println("");

   
        quicksortLinks(arr1, 0, arr1.length-1);
        System.out.println("Pivot-Element Links");
        arrayAusgebenLinks(arr1);
        System.out.println("");

        //quicksortLinks(arr1, 0, arr1.length-1);
        //System.out.println("Pivot-Element Links - Erneutes Sortieren auf dem bereits sortierten Array");
        //arrayAusgebenLinks(arr1);
        //System.out.println("");
       

        quicksortMitte(arr2, 0, arr2.length-1);
        System.out.println("Pivot-Element Mitte");
        arrayAusgebenMitte(arr2);
        System.out.println("");

        //quicksortMitte(arr2, 0, arr2.length-1);
        //System.out.println("Pivot-Element Mitte - Erneutes Sortieren auf dem bereits sortierten Array");
        //arrayAusgebenMitte(arr2);
        //System.out.println("");

       
        quicksortRandom(arr3, 0, arr3.length-1);
        System.out.println("Pivot-Element Random");
        arrayAusgebenRandom(arr3);
        System.out.println("");

        //quicksortRandom(arr3, 0, arr3.length-1);
        //System.out.println("Pivot-Element Random - Erneutes Sortieren auf dem bereits sortierten Array");
        //arrayAusgebenRandom(arr3);
        //System.out.println("");
    }  

    /**
     * Die Methode arrayFuellen() befüllt das Array
     * mit Random-Werten zwischen 0 und 100
     */  
    public void arrayFuellen()
    {
        Random rnd = new Random();

        for(int i=0; i<=arr1.length-1; i++)
        {
            arr1[i] = rnd.nextInt(1000);   //liefert eine zufällige Zahl zwischen 0 und 1000
        }
    }
    /**
     * Die Methode arrayDuplizieren() vervielfältigt
     * das Original-Array
     */  
    public void arrayDuplizieren()
    {
        for(int i=0; i<=arr1.length-1; i++)
        {
            arr2[i] = arr1[i]; 
            arr3[i] = arr1[i];
        }
    }

   

    void quicksortLinks(int arr[], int left, int right)
    {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quicksortLinks(arr, left, index - 1);
        if (index < right)
            quicksortLinks(arr, index, right);
    }
    int partition(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
        int pivot = arr[left];

        while (i <= j)
        {
            vergleicheLinks++;
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
           
            if (i <= j)
            {
               
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

   
   
    void quicksortMitte(int arr[], int left, int right)
    {
        int index = partition2(arr, left, right);
        if (left < index - 1)
            quicksortMitte(arr, left, index - 1);
        if (index < right)
            quicksortMitte(arr, index, right);
    }
    int partition2(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j)
        {
            vergleicheMitte++;
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
           
            if (i <= j)
            {
               
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }   

   
    void quicksortRandom(int arr[], int left, int right)
    {
        int index = partition3(arr, left, right);
        if (left < index - 1)
            quicksortRandom(arr, left, index - 1);
        if (index < right)
            quicksortRandom(arr, index, right);
    }
    int partition3(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
       
        // Vergleichselement pivot
        int p1=0, p2=0, p3=0;
        int pivot = 0;

        Random rnd1 = new Random();
        Random rnd2 = new Random();
        Random rnd3 = new Random();
       
        if (arr.length<3)
        {
            pivot = arr[left];
        }
       
        if (arr.length>=3)
        {
            p1 = arr[left+rnd1.nextInt(right-left+1)];  
            p2 = arr[left+rnd2.nextInt(right-left+1)];
            p3 = arr[left+rnd3.nextInt(right-left+1)];   

            if (p2<p1 && p3>p1 || p2>p1 && p3<p1)    
            {
                pivot = p1;
            }
            if (p1<p2 && p3>p2 || p1>p2 && p3<p2)    
            {
                pivot = p2;
            }
            if (p1<p3 && p2>p3 || p1>p3 && p2<p3)    
            {
                pivot = p3;
            }

            if (p1==p2 || p2==p3 || p1==p3)  
            {
                pivot = p1;
            }
        }
  
        while (i <= j)
        {
           
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
           
            if (i <= j)
            {
                vergleicheRandom++;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }      

   

    /**
     * Die Methode arrayAusgeben() gibt die Integer-Werte
     * der der Arrays aus.
     *
     */   
    public void arrayAusgebenLinks(int arr[])
    {
        for(int i=0; i<=arr.length-1; i++)
        {
            System.out.print(arr[i] + ", ");
        }
        System.out.println("");
        System.out.print("Anzahl der Vergleiche: " +vergleicheLinks);
        System.out.println("");
    } 
    public void arrayAusgebenMitte(int arr[])
    {
        for(int i=0; i<=arr.length-1; i++)
        {
            System.out.print(arr[i] + ", ");
        }
        System.out.println("");
        System.out.print("Anzahl der Vergleiche: " +vergleicheMitte);
        System.out.println("");
    }
    public void arrayAusgebenRandom(int arr[])
    {
        for(int i=0; i<=arr.length-1; i++)
        {
            System.out.print(arr[i] + ", ");
        }
        System.out.println("");
        System.out.print("Anzahl der Vergleiche: " +vergleicheRandom);
        System.out.println("");
    }   
}
```

Ich habe die drei Algorithmen auf einem Array der Größe 10000, mit random Elemente zwischen 0 und 1000, laufen lassen. Ausgabe siehe Anhang


Im Anhang mein BlueJ-Projekt.

Ich würde gerne wissen, ob ich einen Fehler gemacht habe, oder ob das mit der Wahl des Pivot-Elements doch nicht stimmt. (kann ich mir ja eigentlich nicht vorstellen)

viele liebe Grüße,
Deggit


----------



## JStein52 (30. Jan 2017)

1.) das angehaengte Projekt enthält den Quicksort nicht.
2.) in der Ausgabe fällt auf dass die Pivot-Elemente soweit sie sichtbar sind genau gleich sind.


----------



## JCODA (30. Jan 2017)

deggit_biber hat gesagt.:


> Soweit ich gelernt habe, trägt die Wahl des Pivot-Elements maßgeblich zur Effizienz des Algorithmus bei.


Das stimmt. Allerdings hat es nichts damit zu tun, das Pivot links,rechts oder random zu wählen. (Das ist in diesem Fall einfach "random" (weil ohne Betrachtung der Gesamtheit der Elemente))
Sondern es hat damit zu tun, wie es sich zum median verhält. Wenn du als Pivot immer den Median wählst, hast du die beste Laufzeit, da die rekursiven Reste möglichst gleichgroß sind. 
Leider benötigt man auch Zeit um den Median zu berechnen, deshalb versucht man eine gute "Heuristik" zu finden, um möglichst nahe am Median zu liegen.


----------



## deggit_biber (30. Jan 2017)

@JStein52: Danke, dass du auch hier einmal rein schaust. 
1) Wie das angehängte Projekt enthält den QuickSort nicht. Liegt es vielleicht an der BlueJ-Datei? ICh habe den Anhang gerade noch einmal heruntergeladen und mit BlueJ geöffnet. Klappt alles. 
2) In der Ausgabe sind die Pivot-Element gar nicht sichtbar. Sondern nur die Elemente der Array und die Anzahl der Vergleiche die benötigt wurden, um das Array zu sortieren. 

@JCODA: Auch dir vielen Dank, dass du einmal drüber geschaut hast. 
Aber gerade beim 3er Random Wählen müsste doch statistisch Häufiger ein Wert in der Mitte raus kommen als beim immer links wählen. 

Beispiel:
Sei Zahlenreihe:
787, 960, 515, 12, 341, 740, 882, 352, 207, 611, 36, 158, 669, 158, 164, 506, 701, 481, 586, 316, 615

Wähle ich immer das erste so habe ich 787, 960 usw. 
bei Zahlen zwischen 0 und 1000 hätte ich am liebsten immer die 500, richtig?

Also wähle ich jetzt drei Random und nehme das mittlere, dann komme ich der 500 doch immer näher, als wenn ich immer nur das erste nehmen würde 

Random: 740, 207 und 669 -> 669

So meine Logik, leider klappt es nicht im Programm. Ich hätte zumindest beim bei der Random-Variante eine kleine Verbesserung, also weniger Vergleiche, erwartet. Aber egal ob ich 1000 oder 1000000 Zahlen sortieren lasse. Die Vergleiche sind immer nahezu identisch, da kann doch etwas nicht stimmen!?

LG
Deggit


----------



## JStein52 (30. Jan 2017)

deggit_biber hat gesagt.:


> Wie das angehängte Projekt enthält den QuickSort nicht.


Das ist die Klasse Sortieren aus deinem Anhang.

```
/**
* Beschreiben Sie hier die Klasse Sortieren.
*
* @author (Ihr Name)
* @version (eine Versionsnummer oder ein Datum)
*/
public class Sortieren
{
    private List<Integer> liste;

    /**
     * Konstruktor fÃ¼r Objekte der Klasse Sortieren
     */
    public Sortieren()
    {
        System.out.print('\u000C'); // Konsole leeren.
        listeErstellen();
        listeAusgeben();
        System.out.println("insertionSort() ausfÃ¼hren.");
        insertionSort();
        listeAusgeben();

        listeErstellen();
        System.out.println("selectionSort() ausfÃ¼hren.");
        selectionSort();
        listeAusgeben();
    }
   
    /**
     * Die Methode selectionSort() realisiert das
     * Sortieren durch Auswaehlen.
     *
     */
    public void selectionSort()
    {
        List<Integer> sortierteListe = new List<Integer>();
        liste.toFirst();
        while (!liste.isEmpty())
        {          
            int hilf = liste.getContent();
            liste.next();

            while (liste.hasAccess())
            {
                if (liste.getContent() < hilf)
                {
                    hilf = liste.getContent();

                }               
                liste.next();
            }
            loescheElement(hilf);
            sortierteListe.append(hilf);
        }

        liste = sortierteListe;
    }

    /**
     * Die Methode loescht ein Elemente mit dem Wert
     * der als Parameter angegebenen Variablen aus der Originalliste.
     *
     * @param pWert der Wert des zu loeschenden Elementes
     */
    public void loescheElement(int pWert)
    {
        liste.toFirst();
        while (liste.hasAccess() && liste.getContent() != pWert)
        {              
            liste.next();
        }
        if (liste.getContent() == pWert) liste.remove();
        liste.toFirst();
    }

    /**
     * Die Methode insertionSort() realisiert das
     * Sortieren durch Einfuegen.
     *
     */
    public void insertionSort()
    {
        List<Integer> sortierteListe = new List<Integer>();
        while (!liste.isEmpty())
        {
            liste.toFirst();
            int aktuelles = liste.getContent();
            sortierteListe.toFirst();
            while (sortierteListe.hasAccess() && sortierteListe.getContent() < aktuelles)
            {
                sortierteListe.next();
            }
            if (sortierteListe.hasAccess())
            {
                sortierteListe.insert(aktuelles);
            }
            else {
                sortierteListe.append(aktuelles);
            }
            liste.remove();
        }
        liste = sortierteListe;
    }
    /**
     * Die Methode listeErstellen() erzeugt die
     * Originalliste mit vorgegebenen Integer-Werten.
     *
     */
    public void listeErstellen()
    {
        liste = new List<Integer>();
        liste.append(7);
        liste.append(13);
        liste.append(2);
        liste.append(36);
        liste.append(203);
        liste.append(8);
        liste.append(12);
    }
    /**
     * Die Methode listeAusgeben() gibt die Integer-Werte
     * der Originalliste aus.
     *
     */
    public void listeAusgeben()
    {
        liste.toFirst();
        System.out.println("Listenelemente:");
        while (liste.hasAccess())
        {
            System.out.print(liste.getContent().intValue());
            liste.next();
            if (liste.hasAccess()) System.out.print(", ");
        }
        System.out.println("");
    }
}
```
 und ansonsten ist nur noch eine Klasse List enthalten.


----------



## deggit_biber (30. Jan 2017)

ohhh du hast recht!!! Ich Programmiere immer auf alten Dateien und auf den ersten Blick sah es nach der richtigen Datei aus. Entschuldige bitte! Ich bin ja total dankbar, dass überhaupt jemand einmal drüber schaut.


----------



## JCODA (30. Jan 2017)

Also, als ich die Element-Größe auf bis zu 10000000 und die arrayGröße auf 1000000 und noch ne kleine änderung am Pivot gemacht hab' erhalte ich immer bessere Werte für das Mittlere aus Drei. Siehe folgenden Code. (Ich hab leider einige Änderungen gemacht u.a. Kommentare raus - sorry ... )


```
import java.util.Random;


public class QuickSortPivot {
    //int n;
    int vergleicheLinks = 0, vergleicheMitte = 0, vergleicheRandom = 0;

    private int[] arr1;
    private int[] arr2;
    private int[] arr3;

    private Random rnd = new Random();
   
    public static void main(String args[]) {
        new QuickSortPivot(1000000);
    }

    public QuickSortPivot(int pElemente) {
        System.out.print('\u000C'); // Konsole leeren.
        arr1 = new int[pElemente];
        arr2 = new int[pElemente];
        arr3 = new int[pElemente];

        arrayFuellen();
        System.out.println("");

        quicksortLinks(arr1, 0, arr1.length - 1);
        System.out.println("Pivot-Element Links");
        arrayAusgeben(arr1,vergleicheLinks);
        System.out.println("");


        quicksortMitte(arr2, 0, arr2.length - 1);
        System.out.println("Pivot-Element Mitte");
        arrayAusgeben(arr2,vergleicheMitte);
        System.out.println("");


        quicksortRandom(arr3, 0, arr3.length - 1);
        System.out.println("Pivot-Element Random");
        arrayAusgeben(arr3,vergleicheRandom);
        System.out.println("");

    }

    public void arrayFuellen() {
        for (int i = 0; i < arr1.length ; i++) {
            arr1[i] = rnd.nextInt(10000000);                                        
            arr2[i] = arr1[i];
            arr3[i] = arr1[i];
        }
    }

   
    void quicksortLinks(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quicksortLinks(arr, left, index - 1);
        if (index < right)
            quicksortLinks(arr, index, right);
    }

    int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[left];

        while (i <= j) {
            vergleicheLinks++;
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;

            if (i <= j) {

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    void quicksortMitte(int arr[], int left, int right) {
        int index = partition2(arr, left, right);
        if (left < index - 1)
            quicksortMitte(arr, left, index - 1);
        if (index < right)
            quicksortMitte(arr, index, right);
    }

    int partition2(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            vergleicheMitte++;
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;

            if (i <= j) {

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    void quicksortRandom(int arr[], int left, int right) {
        int index = partition3(arr, left, right);
        if (left < index - 1)
            quicksortRandom(arr, left, index - 1);
        if (index < right)
            quicksortRandom(arr, index, right);
    }

    int partition3(int arr[], int left, int right) {
        //System.out.println(left+" "+right);
        int i = left, j = right;
        int tmp;

        // Vergleichselement pivot
        int p1 = 0, p2 = 0, p3 = 0;
        int pivot = 0;

       

        if (right-left < 2) {
            pivot = arr[left];
        }else {
            int range = right - left + 1;
            p1 = arr[left + rnd.nextInt(range)];
            p2 = arr[left + rnd.nextInt(range)];
            p3 = arr[left + rnd.nextInt(range)];

            pivot = getMiddle(p1, p2, p3);
            //System.out.println(left + " "+ right);
            //System.out.println(p1+" "+p2+" "+p3+" "+pivot);
        }

        while (i <= j) {

            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;

            if (i <= j) {
                vergleicheRandom++;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    private int getMiddle(int p1, int p2, int p3) {
        int pivot = p1;
        if (p1 < p2 && p3 > p2 || p1 > p2 && p3 < p2) {
            pivot = p2;
        }else if (p1 < p3 && p2 > p3 || p1 > p3 && p2 < p3) {
            pivot = p3;
        }else if (p1 == p2){
            pivot = p1;
        }else if(p2 == p3 || p1 == p3) {
            pivot = p3;
        }
        return pivot;
    }


    public void arrayAusgeben(int arr[],int vergleiche) {
        for (int i = 0; i <= arr.length - 1; i++) {
            // System.out.print(arr[i] + ", ");
        }
        System.out.println("");
        System.out.print("Anzahl der Vergleiche: " + vergleiche);
        System.out.println("");
    }


}
```


----------



## deggit_biber (30. Jan 2017)

Toll!!! Lag es dann wohl hauptsächlich an den falschen Start setting?

Eine Kleinigkeit ist mir noch aufgefallen. Beim RandomQuickSort ist der Vergleichszähler in der If-Anweisung. soll das so sein? Bei den anderen beiden ist er in der while-schleife.

vielen lieben Dank,
für deine Mühe

PS: Packe ich den Zähler auch in die while-Schleife, schneidet der Random wieder viel schlechter ab. Eigentlich müssten die Zählen doch bei allen drei Algorithmen an der gleichen Stellen sein, oder?


----------



## JCODA (30. Jan 2017)

deggit_biber hat gesagt.:


> Eine Kleinigkeit ist mir noch aufgefallen. Beim RandomQuickSort ist der Vergleichszähler in der If-Anweisung. soll das so sein? Bei den anderen beiden ist er in der while-schleife.
> PS: Packe ich den Zähler auch in die while-Schleife, schneidet der Random wieder viel schlechter ab. Eigentlich müssten die Zählen doch bei allen drei Algorithmen an der gleichen Stellen sein, oder?


Ooops. hehe tut mir leid, da ist was schief gelaufen. Ich steh gerade aufm Schlauch ...


----------



## deggit_biber (30. Jan 2017)

Also der Ort muss überall gleich sein, denke da sind wir uns einig ;-)
Ich würde den Zähler auch in die While-Schleife packen, da ja i mit j verglichen wird und erst wenn er ein i findet, das >= pivot ist und ein j, das <= pivot ist tauscht er. 

Leider sind dann die Anzahl der Vertauschungen beim Random wieder am schlechtesten und von der Logik müssten sie doch am besten sein ;-) 

Ich raff das net...


----------



## JCODA (30. Jan 2017)

Okay, wenn ich folgendes tue: Also Alle Element-Vergleiche zähle, in denen "arr" vorkommt (d.h. innerhalb der beiden while und zwei zusätzlich, da die while-vergleiche ja einmal mehr ausgeführt werden) dann siehts ganz gut aus: 

```
import java.util.Random;


public class QuickSortPivot {
    //int n;
    int vergleicheLinks = 0, vergleicheMitte = 0, vergleicheRandom = 0;

    private int[] arr1;
    private int[] arr2;
    private int[] arr3;

    private Random rnd = new Random();
   
    public static void main(String args[]) {
        new QuickSortPivot(1000000);
    }

    public QuickSortPivot(int pElemente) {
        System.out.print('\u000C'); // Konsole leeren.
        arr1 = new int[pElemente];
        arr2 = new int[pElemente];
        arr3 = new int[pElemente];

        arrayFuellen();
        System.out.println("");

        quicksortLinks(arr1, 0, arr1.length - 1);
        System.out.println("Pivot-Element Links");
        arrayAusgeben(arr1,vergleicheLinks);
        System.out.println("");


        quicksortMitte(arr2, 0, arr2.length - 1);
        System.out.println("Pivot-Element Mitte");
        arrayAusgeben(arr2,vergleicheMitte);
        System.out.println("");


        quicksortRandom(arr3, 0, arr3.length - 1);
        System.out.println("Pivot-Element Random");
        arrayAusgeben(arr3,vergleicheRandom);
        System.out.println("");

    }

    public void arrayFuellen() {
        for (int i = 0; i < arr1.length ; i++) {
            arr1[i] = rnd.nextInt(10000000);                                        
            arr2[i] = arr1[i];
            arr3[i] = arr1[i];
        }
    }

   
    void quicksortLinks(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quicksortLinks(arr, left, index - 1);
        if (index < right)
            quicksortLinks(arr, index, right);
    }

    int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[left];

        while (i <= j) {
            vergleicheLinks+=2;
            while (arr[i] < pivot){
                vergleicheLinks++;
                i++;
            }
            while (arr[j] > pivot){
                vergleicheLinks++;
                j--;
            }
               

            if (i <= j) {

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    void quicksortMitte(int arr[], int left, int right) {
        int index = partition2(arr, left, right);
        if (left < index - 1)
            quicksortMitte(arr, left, index - 1);
        if (index < right)
            quicksortMitte(arr, index, right);
    }

    int partition2(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            vergleicheMitte+=2;
            while (arr[i] < pivot){
                i++;
                vergleicheMitte++;
            }
            while (arr[j] > pivot){
                vergleicheMitte++;
                j--;
            }
               

            if (i <= j) {

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    void quicksortRandom(int arr[], int left, int right) {
        int index = partition3(arr, left, right);
        if (left < index - 1)
            quicksortRandom(arr, left, index - 1);
        if (index < right)
            quicksortRandom(arr, index, right);
    }

    int partition3(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;

        int p1 = 0, p2 = 0, p3 = 0;
        int pivot = 0;
        if (right-left < 2) {
            pivot = arr[left];
        }else {
            int range = right - left + 1;
            p1 = arr[left + rnd.nextInt(range)];
            p2 = arr[left + rnd.nextInt(range)];
            p3 = arr[left + rnd.nextInt(range)];

            pivot = getMiddle(p1, p2, p3);
        }

        while (i <= j) {
            vergleicheRandom+=2;
            while (arr[i] < pivot){
                i++;
                vergleicheRandom++;
            }
               
            while (arr[j] > pivot){
                j--;
                vergleicheRandom++;
            }
               

            if (i <= j) {               
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    private int getMiddle(int p1, int p2, int p3) {
        int pivot = p1;
        if (p1 < p2 && p3 > p2 || p1 > p2 && p3 < p2) {
            pivot = p2;
        }else if (p1 < p3 && p2 > p3 || p1 > p3 && p2 < p3) {
            pivot = p3;
        }else if (p1 == p2){
            pivot = p1;
        }else if(p2 == p3 || p1 == p3) {
            pivot = p3;
        }
        return pivot;
    }


    public void arrayAusgeben(int arr[],int vergleiche) {
        for (int i = 0; i <= arr.length - 1; i++) {
            // System.out.print(arr[i] + ", ");
        }
        System.out.println("");
        System.out.print("Anzahl der Vergleiche: " + vergleiche);
        System.out.println("");
    }


}
```


----------



## deggit_biber (30. Jan 2017)

ohhh ja das sieht schon recht gut aus.

Warum machst du dies? 

vergleicheLinks+=2;

bin auch gerade mit der Notation nicht so vertraut. Setzt du hier VergleicheLinks auf 2?


----------



## JCODA (30. Jan 2017)

das ist äquivalent zu vergleicheLinks=vergleicheLinks+2;
Also vergleicheLinks wird um 2 erhöht. 
Und warum mache ich das: Bei einer while-Schleife wird ja immer ein Vergleich mehr ausgeführt, als die Schleife betreten wird, denn irgendwann ist ja die Bedingung falsch, aber der Vergleich wurde ja trotzdem durchgeführt.


----------



## deggit_biber (30. Jan 2017)

Ahhh das leuchtet ein.

Müsste ich das in der inneren while dann nicht auch machen?

```
while (arr[i] < pivot)
            {
                vergleicheLinks++;
                i++;
            }
```
ändern in

```
while (arr[i] < pivot)
            {
                vergleicheLinks+=2;
                i++;
            }
```

Also eigentlich in allen while-schleifen, oder?

Denke da gerade noch einmal drüber nach. 
So ganz passt es mit dem 
vergleicheLinks+=2;
aber nicht, glaube ich zumindest. 
Wenn ich das so lassen, dann wird doch bei jedem Eintritt in die while-Schleife der Zähler um zwei erhöht. Aber eigentlich müsste er doch bei jedem Eintritt nur um eins erhöht werden und wenn er nicht rein kann, dann müsste er auch um eins erhöht werden. 
Beispiel er kann 10 mal reingehen, dann wären 10+1 Vergleichen (+1, weil noch der letzte Vergleich hinzukommt, da wo er nicht reingehen konnte)

Bei vergleicheLinks+=2;
wären es aber 20 Vergleiche. 

Habe ich da jetzt einen Denkfehler?


----------



## JCODA (30. Jan 2017)

ich hab +2 gemacht, weil es zwei while-Schleife sind und bei jeder wird einmal mehr die bedingung getestet als die Schleife ausgeführt


----------



## deggit_biber (30. Jan 2017)

Ahhh, ok das macht Sinn! 
Ich danke dir sehr für deine Hilfe.
Vielen lieben Dank
Deggit


----------



## JStein52 (31. Jan 2017)

Ich habe auch mal ein bisschen rumprobiert. Die drei Verfahren sind bei der Anzahl Vergleiche und Anzahl Vertauschungen etwas unterschiedlich. Bei mir ergaben sich folgende Werte:

```
Vergleiche             Vertauschungen
Pivot-Left:        577000                  158900
Pivot-Mitte:       488000                  156300
Pivot-Random:      391000                  162400
```


----------



## deggit_biber (31. Jan 2017)

@JStein52: Vielen lieben Dank! Das deckt sich mit meinen Ergebnissen. Hätte trotzdem gedacht, dass die Auswirkungen größer wären. Ich denke richtig gute Implementierungen nutzen noch den ein oder anderen Trick ;-) 

vielen lieben Dank an euch beide.
LG
Deggit


----------

