Quicksort

[Liondary]

Guten Abend,

ich versuche grade selber eine Quicksort Funktion zu schreiben, da ich denke da ich das Prinzip besser verstehe wenn ich das ganze selber schreibe anstatt eine Funktion einfach irgendwo zu kopieren. Ich hab jetzt eine Funktion geschrieben, aber leider spuckt Eclipse mir immer einen Fehler kann mir jemand sagen was ich falsch gemacht habe?

Vielen Dank und beste Grüße

import java.util.Scanner;

public class Quicksort {

    public static void main(String[] args) {
       
        Scanner scanner = new Scanner(System.in);
        int[] a = new int [10];
       
        for(int i = 0; i < a.length; i++) {
           
            System.out.print("Geben Sie die " + i + ". Zahl ein: ");
            a[i] = scanner.nextInt();
        }
       
        quicksort(a, 0, a.length-1);
       
        for(int i = 0; i < a.length; i++) {
           
            System.out.print(a[i] + ", ");
        }
    }
   
    static void quicksort(int a[], int l, int r){       
        
        int links = l;
        int rechts = r;
        int tmp;
        int p = 0;
       
        for(int i = 1; i < a.length; i++) {
   
            if(a[i] < a[p]) {
       
                tmp = a[p];
                a[p] = a[i];
                a[i] = tmp;
           
                p = i;
               
                for(int c = i; c <= 0; c--){
                   
                    if(a[p] < c) {
                        a[c] = tmp;
                        a[c] = a[p];
                        a[p] = tmp;
                   
                        p = c;
                    }
                }
            }
       
        }
       
        quicksort(a, l, p-1);
        quicksort(a, p+1, r);

    }

}

 

[Meniskusschaden]

Du rufst quicksort rekursiv auf, hast aber keine Abbruchbedingung vorgesehen. Also wird quicksort immer wieder aufgerufen, bis der Stack überläuft.

 

[Xyz1]

Die Abbruchbedingung müsste sein: if (l >= r) {.

Edit:

, da ich denke da ich das Prinzip besser verstehe wenn ich das ganze selber schreibe anstatt eine Funktion einfach irgendwo zu kopieren.

Das ist ein guter Ansatz, ich hab auch sämtliche Algos selber implementiert, bevor/nachdem ich sie verstanden hab!

Jeder lernt unterschiedlich.

 

[Liondary]

Vielen Dank euch beiden! @Der Wissende ich denke du meintest

if (r>=l) {}

Funktioniert jetzt!

hier nochmal der Code für die Nachwelt:

import java.util.Scanner;

public class Quicksort {

    public static void main(String[] args) {
      
        Scanner scanner = new Scanner(System.in);
        int[] a = new int [10];
      
        for(int i = 0; i < a.length; i++) {
          
            System.out.print("Geben Sie die " + i + ". Zahl ein: ");
            a[i] = scanner.nextInt();
        }
      
        quicksort(a, 0, a.length-1);
      
        for(int i = 0; i < a.length; i++) {
          
            System.out.print(a[i] + ", ");
        }
    }
  
    static void quicksort(int a[], int l, int r){      
       
        if (r >= l) {
      
        int links = l;
        int rechts = r;
        int tmp;
        int p = 0;
      
        for(int i = 1; i < a.length; i++) {
  
            if(a[i] < a[p]) {
      
                tmp = a[p];
                a[p] = a[i];
                a[i] = tmp;
          
                p = i;
              
                for(int c = i; c <= 0; c--){
                  
                    if(a[p] < c) {
                        a[c] = tmp;
                        a[c] = a[p];
                        a[p] = tmp;
                  
                        p = c;
                    }
                }
            }
      
        }
      
        quicksort(a, l, p-1);
        quicksort(a, p+1, r);

        }
    }
}

 

[Xyz1]

Args! So kann man es auch machen, aber es erhöht die Tiefe und verringert die Lesbarkeit!, mir hätten sie Spaghetti vorgeworfen!

 

[Liondary]

@DerWissende wie meinst du das? Was sollte ich deiner Meinung nach ändern? Bin noch Anfänger...

Es funktioniert leider doch noch nicht ganz... Jetzt spuckt er mir ein Fehler bei

quicksort(a, p+1, r);

Bedeutet 10,9,8,7,6,5,4,3,2,1 wird sortiert - aber sobald auch etwas rechts vom Pivot steht funktioniert es nicht mehr :/

 

[Xyz1]

Args!, ich meine das so:

    /**
     * @author DerWissende on 03/20/2016
     */
    private static void qsPrototype(int[] a, int l, int r) {
        if (l >= r) {
            return;
        }
        while (l < r) {
            if (a[l] > a[r]) {
                int t = a[l];
                a[l] = a[r];
                a[r] = t;
            }
            l++;
            r--;
        }
        System.out.println("l = " + l + " r = " + r);
        qsPrototype(a, 0, l - 1);
        qsPrototype(a, r + 1, a.length - 1);
    }

    /**
     * @author DerWissende on 03/20/2016
     */
    public static void main(String[] args) {
        qsPrototype(new int[]{4, 1, 2, 3}, 0, 3);
    }

Funktioniert aber nicht der Bums, "Endlosschleife". Ohne Pivot wird es nicht gehen. Warum?

AAAABER: Die Abbruchbedingung müsste wirklich so aussehen.

qsPrototype hat den Rückgabetyp void, d. h. eine Methode kann auch verlassen werden mit return;. Deines sollte aber genausogut funktionieren.

Bin auf eure Antworten gespannt.

Edit:

Schaue hier vorbei: http://www.programcreek.com/2012/11/quicksort-array-in-java/

if (lowerIndex < j) und if (i < higherIndex) braucht man glaube ich nicht. (exchangeNumbers auch nicht)

Etwas stimmt mit deinen zwei inneren Schleifen noch nicht.

 

[Liondary]

Sorry, ich weiß leider auch nicht wo bei dir das Problem liegt...

Ich habe ja einen Pivot nämlich a[0] bzw. p sollte bei mir immer auf den Pivot zeigen...

 

[Xyz1]

Wenn du das Pivot in der Mitte wählst, verbessert sich die Laufzeit (bei schon sortierten Listen).

 

[Meniskusschaden]

@Liondary: Ich glaube, da sind noch einige grundsätzliche Fehler enthalten. Ich würde mal ein paar Beispielzahlen aufschreiben und deinen Algorithmus damit auf dem Papier durchgehen. Dann fallen einige Probleme auf. Wenn du beispielsweise in der ersten for-Schleife einen Tausch vorgenommen hast, gehst du in der zweiten Schleife von dieser Position aus wieder zurück. Ausserdem ist es beim Quicksort meines Erachtens nicht so gedacht, dass man das Pivot-Element gegen das abgefragte Element vertauscht. Stattdessen sucht man von links bis zum ersten Treffer, dann von rechts bis zum ersten Treffer und tauscht die beiden Treffer gegeneinander. Das wiederholt man, bis links vom Pivot-Element nur kleinere und rechts nur größere Zahlen stehen und startet dann die rekursiven Aufrufe.
Ich würde auch den richtigen Quicksort-Algorithmus mal auf dem Papier durspielen und dann erst implementieren.

 

[Meniskusschaden]

@DerWissende: Ich habe mir das nur flüchtig angesehen, aber ich glaube eine Sache ist mir doch aufgefallen. Du gehst ja bei jeder Schleifeniteration gleichzeitig von links und von rechts eine Position weiter. Ich denke, so erwischst du nicht jedes Trefferpaar, weil die beiden Elemente ja nicht unbedingt in derselben Iteration erreicht werden.

 

[Xyz1]

Ich denke, so erwischst du nicht jedes Trefferpaar,

das stimmt, dadurch ist die Eigenschaft auch nicht gegeben, das alle links vom Pivot <= und alle rechts vom Pivot >= sind. Es war nur 'nen Entwurf, auch um das mit der Abbruchbedingung zu zeigen.

 

[Liondary]

Danke euch allen für eure Anregungen und Tipps! Hab das Problem nun folgendermaßen gelöst:

import java.util.Scanner;

public class Quicksort {

     public static void main(String[] args) {
    
         Scanner scanner = new Scanner(System.in);
         int[] a = new int [10];
    
         for(int i = 0; i < a.length; i++) {
        
             System.out.print("Geben Sie die " + i + ". Zahl ein: ");
             a[i] = scanner.nextInt();
         }
    
         quicksort(a, 0, a.length-1);
    
         for(int i = 0; i < a.length; i++) {
        
             System.out.print(a[i] + ", ");
         }
     }
    
       public static void quicksort(int a[], int links, int rechts) {
           
        if (links < rechts) {
                 
                    int help1, pivot, i, j;
                    pivot = a[rechts];            
                    i     = links;
                    j     = rechts-1;
                 
                    while(i<=j) {
                          if (a[i] > pivot) {    
                                            help1 = a[i];         
                                            a[i] = a[j];
                                            a[j] = help1;                       
                                            j--;
                           } else i++;         
                            
                    }
                 
                    help1      = a[i];
                    a[i]      = a[rechts];
                    a[rechts] = help1;        
                
                 
                    quicksort(a,links,i-1);
                    quicksort(a ,i+1,rechts);
        }
       }
}

 

[Xyz1]

Ich hab es mal abgeändert/verbessert und Ausgaben hinzufügt, kann dir aber nicht sagen, ob alles 100 % ig richtig ist:

    private static void quicksortVonLiondaryUndDW(int a[], int links, int rechts) {
        if (links < rechts) {
//            int help1, pivot, i, j;
//            pivot = a[rechts];
//            i = links;
//            j = rechts - 1;
            int mid = links + (rechts - links) / 2;
            int piv = a[mid];
            int i = links;
            int j = rechts;

            while (i < j) { /* oder <= */
//                if (a[i] > pivot) {
//                    help1 = a[i];
//                    a[i] = a[j];
//                    a[j] = help1;
//                    j--;
//                } else {
//                    i++;
//                }

                while (a[i] < piv) {
                    i++;
                }
                while (a[j] > piv) {
                    j--;
                }
                if (i < j) { /* oder <= */
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    i++;
                    j--;
                }
            }

            System.out.println("mid = " + mid);
            System.out.println("i = " + i);
            System.out.println("j = " + j);
            System.out.println("");

            quicksortVonLiondaryUndDW(a, links, j);
            quicksortVonLiondaryUndDW(a, i, rechts);
        }
    }

            quicksort(a, links, j);
            quicksort(a, i, rechts);

.... erschließt sich mir noch nicht. (Wieso i und j und nicht mid?)

Bis dann

 

[Liondary]

"i" ist im Prinzip meine "mid" und man will ja den Quicksort immer nochmal auf die Linke und die Rechte Hälfte anwenden. Deshalb von links(also 0) bis i-1 also ein Wert links neben der Mitte und von i+1 (ein Wert rechts neben unserer Mitte) bis rechts(unser letzter Array Eintrag). Ich hoffe du verstehst was ich meine. Ich danke dir aber für deine Version, ich denke die ist nochmal besser als meine. Liebe Grüße!

 

[kneitzel]

Also das klassiche Quicksort kenne ich mit leichten Abweichungen aber ich muss es nicht groß selbst beschreiben, denn Wikipedia hat das schon:

https://de.wikipedia.org/wiki/Quicksort

Da würde dann der Algorithmus einfach so aussehen:

public static void quickSort(int[] daten, int links, int rechts) {
    if (links < rechts) {
        int teiler = teile(daten, links, rechts);
        quickSort(daten, links, teiler-1);
        quickSort(daten, teiler+1, rechts);
    }
}

public static int teile(int[] daten, int links, int rechts) {
    int i = links;
    int j = rechts-1;
    int pivot = daten[rechts];
    do {
        // Suche von Links ein Element, welches größer als das Pivotelement ist
        while (daten[i]<=pivot && i < rechts) {
            i++;
        }

        // Suche von Rechts ein Element, welches kleiner als das Pivotelement ist
        while (daten[j]>=pivot && j > links) {
            j--;
        }

        if (i<j) {
            int temp = daten[i];
            daten[i] = daten[j];
            daten[j] = temp;
        }

    } while (i < j);

    if (daten[i] > pivot) {
        int temp = daten[i];
        daten[i] = daten[rechts];
        daten[rechts] = temp;
    }

    // Gib Position des Pivotelement zurück
    return i;
}

 

[Blender3D]

Falls Du damit etwas anfangen kannst. Quicksort generisch gebaut.

/**
* Generic quick sort algorithm for types implementing interface Comparable.
*
* @author Blender3D
*
*/
public class SortAlgorithms {
    /**
     * @param data
     *            Array of Comparable to be sorted.
     */
    public static <T extends Comparable<T>> void quickSort(T[] data) {
        if (data == null || data.length == 1)
            return;
        quickSortRecursiv(data, 0, data.length - 1);
    }

    private static <T extends Comparable<T>> void quickSortRecursiv(T[] data, int left, int right) {
        if (left < right) {
            int pivot = split(data, left, right);
            quickSortRecursiv(data, left, pivot - 1);
            quickSortRecursiv(data, pivot + 1, right);
        }
    }

    private static <T extends Comparable<T>> int split(T[] data, int left, int right) {
        int i = left;
        int j = right - 1;// j left from pivot
        T pivot = data[right];

        do {
            // find element bigger than pivot on left side
            while (data[i].compareTo(pivot) <= 0 && i < right)
                i++;
            // find element smaller than pivot on right side
            while (data[j].compareTo(pivot) >= 0 && j > left)
                j--;
            if (i < j)
                swap(data, i, j);
        } while (i < j); // do that till i has passed j
        if (data[i].compareTo(pivot) > 0)
            swap(data, i, right);
        return i; // pivots new position
    }

    private static <T extends Comparable<T>> void swap(T[] data, int pos1, int pos2) {
        T tmp = data[pos1];
        data[pos1] = data[pos2];
        data[pos2] = tmp;
    }
}

 

[Xyz1]

Also das klassiche Quicksort kenne ich mit leichten Abweichungen aber ich muss es nicht groß selbst beschreiben, denn Wikipedia hat das schon:

https://de.wikipedia.org/wiki/Quicksort

Da würde dann der Algorithmus einfach so aussehen:

Ok, auch eine gute Lösung. Wenn man da einsteigen möchte (untere Schranke "selbstverständlich" schon erreicht), kann man auch in der Algo Bibel oder mal in die Implementierung der API in Java (MergeSort und modifiziertes QS, soweit ich weiß) schauen. Dort heißt es DualPivotQuicksort.

* This class implements the Dual-Pivot Quicksort algorithm by
* Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
* offers O(n log(n)) performance on many data sets

Oder hier http://www.programcreek.com/2012/11/quicksort-array-in-java/ oder andere 1000 Seiten oder:
Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 9. Okt. 2015
Quicksort Algorithmus Java Basics - Anfänger-Themen 8. Apr. 2015
QuickSort (Pivotelement) Allgemeine Java-Themen 14. Dez. 2014
Java Quicksort Java Basics - Anfänger-Themen 13. Nov. 2014
"instabiles" Quicksort Plauderecke 5. Sep. 2014
[...]

Das sollte doch schon weiterhelfen.

Edit: Nochmal was, nach Quelle: http://www.programcreek.com/2012/11/quicksort-array-in-java/ :

    private static void quicksortVonLiondaryUndDW(int a[], int links, int rechts) {
        aufrufe++;
        if (links < rechts) {
            int mid = links + (rechts - links) / 2;
            int piv = a[mid];
            int i = links;
            int j = rechts;
            while (i < j) { /* oder <= , <= um 12 % schneller */

                while (a[i] < piv) {
                    i++;
                }
                while (a[j] > piv) {
                    j--;
                }
                if (i <= j) { /* muss <= , sonst funktioniert er nicht */

                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    i++;
                    j--;
                }
            }
            quicksortVonLiondaryUndDW(a, links, j);
            quicksortVonLiondaryUndDW(a, i, rechts);
        }
    }

<= in Zeile 8 macht es, obwohl es widersprüchlich erscheint, den Algo um 12 % schneller.

 

[Blender3D]

Warum sollte man derartige Algorithmen generisch programmieren?
Damit man z.B. so etwas mit einem einzigen Code erledigt.

        String [] strings = {"Peter", "Albert", "Hubert", "Gustav"};
        Integer [] integers = {10,4,8,9};
        SortAlgorithms.quickSort(strings);
        SortAlgorithms.quickSort(integers);
        for( Integer i: integers )
            System.out.println(i);
        for( String s: strings )
            System.out.println(s);

Ausgabe:
4
8
9
10
Albert
Gustav
Hubert
Peter

 

[Blender3D]

DualPivotQuicksort

Stimmt ist schneller. Java hat diesen Algorithmus seit einigen Jahren integriert. Das bedeutet die Klasse Arrays.sort( ... ) bietet die Möglichkeit, jede sortierbare Klasse( generisch ) zu ordnen und das mit der besten Geschwindigkeit.
DualPivotQuicksort: Ist wie der Name schon sagt, statt einer, zwei Pivostellen. Zum obigen Code kommt ein dritter Index dazu und der rekursive Aufruf wird in 3 statt 2 Bereiche geteilt . Auch die Bedingungen werden etwas komplizierter. Dafür läuft er aber schneller.
Um den Quicksort zu verstehen, sollte man aber bei der einfachen Variante bleiben. Ist besser zu durchschauen. Ich finde fürs Verständnis wäre es auch gut die einzelnen Arbeitsschritte in Funktionen wie tausche, teile auszulagern. Und wenn man so einen Algorithmus selbst programmiert, ist es auch wichtig zu verstehen, wie man Code wieder verwendbar macht.
Aber für den alltäglichen Gebrauch eignet sich die in Java eingebaute Variante am besten.

 

[Xyz1]

Ich weiß das alles, aber mit Generics sollte man noch nicht um sich werfen.