Quicksort

[fragejava]

Hallo,

bei Quicksort ist es doch so, dass in einem Rekursionsschritt alle Elemente in der linken Teilhälfte kleiner gleich dem Pivotelement sind und alle rechten Teilhälfte-elemente größer dem Pivotelement sind. Anschließend steht das Pivotelement an der richtigen Stelle.

So implementiert:

    public static <T> void quicksort(T[] array, Comparator<T> comp) {
        quicksort(array, comp, 0, array.length - 1);
    }

    private static <T> void quicksort(T[] array, Comparator<T> comp, int anfang, int ende) {
        if (anfang >= ende) {
            return;
        }

        int m = anfang + (ende - anfang) / 2;
        int l = anfang;
        int r = ende;
        while (l < r) {
            while (l < r && comp.compare(array[l], array[m]) <= 0) {
                l++;
            }
            while (l < r && comp.compare(array[r], array[m]) >= 0) {
                r--;
            }
            if (l < r) {
                swap(array, l, r);
            }
        }
        if (comp.compare(array[l], array[m]) != 0) {
            swap(array, l, m);
        }

        quicksort(array, comp, anfang, l - 1);
        quicksort(array, comp, l + 1, ende);
    }

Wenn ich damit aber teste, bekomme ich als Ergebnis "ungefähr" sortierte Arrays (nicht ganz durcheinander, aber aber auch nicht ganz sortiert).

Den Fehler kann ich nicht nachvollziehen, da m.M.n. nach jedem Durchlauf der äußeren while-Schl. gilt, dass alle Elemente mit Index < l kleiner gleich dem Pivotelement sind und alle Elemente mit Index > l größer gleich dem Pivotelement sind. Wenn das Pivotelement dann auch noch auf die Stelle l gesetzt wird, ist es richtig einsortiert. Wo ist der Fehler?

 

[awda23ws23]

in der Prüfung

if (l < r) {

Quicksort in Java

 

[fragejava]

Etwas genauer? (Eigentlich ist mir das schon aufgefallen, aber ein Begründung ist das ja nicht.)

Habe es geändert:

    private static <T> void quicksort(T[] array, Comparator<T> comp, int anfang, int ende) {
        if (anfang >= ende) {
            return;
        }

        int m = anfang + (ende - anfang) / 2;
        int l = anfang;
        int r = ende;
        while (l < r) {
            while (l < r && comp.compare(array[l], array[m]) <= 0) {
                l++;
            }
            while (l < r && comp.compare(array[r], array[m]) >= 0) {
                r--;
            }
            if (l < r) {
                swap(array, l, r);
            }
        }
        if (l < m && comp.compare(array[l], array[m]) > 0
                || l > m && comp.compare(array[l], array[m]) < 0) {
            swap(array, l, m);
        }

        quicksort(array, comp, anfang, l - 1);
        quicksort(array, comp, l + 1, ende);
    }

So funktioniert es und es ist m.M.n. effizienter als die Version bei Wikipedia. Könnte das jemand bestätigen?

Es werden m.M.n. Schritte eingespart, wenn nicht l und r bis ganz nach links bzw. ganz nach rechts gesetzt werden müssen. Richtig?

 

[fragejava]

Ich hab es getestet. Für 10 Millionen Elemente benötigt java.util.Arrays.sort() ungefähr 17 Sekunde und dieses Quicksort 19 Sekunden. Wie kommt das, wenn es doch so schnell sein soll? Gibt es eine bessere Implementierung?

 

[Dekker]

Ich glaube der sort von Java ist schneller weil es sich dabei nicht um Quicksort sondern um Merge-sort handelt. Sicher bin ich mir nicht.

 

[fragejava]

Das kann gut sein, dass das instabile Quicksort nicht genommen wird.

Jetzt hab ich ein weiteres "Phänomen":

    private static <T> void quicksortB(final T[] array, final Comparator<T> comp, final int anfang, final int ende) {
        if (anfang >= ende) {
            return;
        }

        final int m = ende;
        int l = anfang;
        int r = ende - 1;
        while (l < r) {
            while (l < r && comp.compare(array[l], array[m]) <= 0) {
                l++;
            }
            while (l < r && comp.compare(array[r], array[m]) >= 0) {
                r--;
            }
            if (l < r) {
                swap(array, l, r);
                l++;
                r--;
            }
        }
        if (comp.compare(array[l], array[ende]) > 0) {
            swap(array, l, ende);
        }

        quicksort(array, comp, anfang, l - 1);
        quicksort(array, comp, l + 1, ende);
    }

Dieses quicksort ist für Elemente bis 1 Millionen schneller als Arrays.sort()

Änderungen:

- Lauf nur bis l == r, nicht bis l == ende bzw. r == anfang
- Pivot: letztes Elmement, dadurch ist die if-Abfr. nach der while-Schl. kürzer
- Bei swap(): l und r werden in- bzw. dekrementiert, dadurch entfallen zwei unnötige if-Abfr. pro swap()

Es ist allso Effizienter als das, was bei Wikipedia steht... Aber warum nicht für "richtig große Arrays"? Habe mit -Xms512m übrigens mehr Speicher zuweisen müssen, weil Arrays.sort() sonst nicht funktioniert hätte.

 

[hierUndDa]

Java verwendet QuickSort:

%29]
public static void sort(int[] a)

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Parameters:
a - the array to be sorted

 

[fragejava]

Dann wurde es wahrscheinlich ungefähr so wie oben implementiert, nur die Wahl des Pivot dauert länger (meine Vermutung). Für zufällige nicht unendlich große Arrays ist das nämlich schneller.

Wie ist denn Collections.sort() ? Stabil=?

 

[faetzminator]

Ich würde sagen, dass die Laufzeit immer noch gleich gross ist wie jene des "normalen" Quicksort, also mit [c]O(n * log(n))[/c] (bzw. Worst Case [c]O(n^2)[/c]) zu rechnen ist.

 

[fragejava]

ja, du würdest das sagen, weil du auch nicht getestet hast.

Es ist für zufällige Arrays schneller als die verbesserte Version von Arrays.sort()

Das ist mal Fakt. Also lass lieber solche unqualifizierten Aussagen.

Dass der worst-case nicht eliminiert ist, ist schon klar.

 

[HoaX]

Nur weil du eine Behauptung aufstellst ist etwas noch lange nicht fakt. _Beweise_ doch mal wo und warum deine Version schneller ist!

Btw verwendest du ja Comparator in deiner Klasse, d.h. um das gleiche Array mit java.util.Arrays zu sortieren musst du ja Arrays#sort(T[], Comparator<T>) aufrufen. Und das enthält keinen Quicksort, sondern Mergesort.

 

[fragejava]

Habe ich bereits. Ich hab gesagt, dass nur Änderungen vorgenommen sein können (wie die länger dauernde Wahl des Pivot), die mehr Schritte benötigen. Damit ist klar, dass der Algo dann schneller/langsamer ist.

Die LandauNotation interessiert überhaupt nicht, denn in der Theorie ist auch Arrays.sort() nicht schneller als n^2

Wie immer wird die Praxis unterbewertet, von so Neunmalklugen wie hier...

Selbst die Entwickler oben gehen von einer praktischen Abschätzung aus... Aber dir das zu erklären wäre wohl vergebens.

 

[HoaX]

Es gibt nicht _das_ Arrays.sort, selbst diese sind unterschiedlich implementiert!

Und nein, das genügt nicht als Beweis. Ich lese hier nur lauter Behauptungen...

 

[fragejava]

Wie soll man auch einen Nichtssehenden die Welt erklären?

Und das ich dann noch diese triviale Behauptung, das jede andere Wahl des Pivots länger dauert (und damit auch quicksort), beweisen soll, ist mehr als lächerlich.

 

[Empire Phoenix]

trivial, naja mach mal den Beweis formal korekt so trivial ist der garnicht.

Abgesehen davon das ein Merge sort schneller als Quicksort ist, da man dieses IMMER mit entsprechenden inputs auf einen O(n^2) laufzeit bringen kann, während MergeSort maximal auf O(n*log(n)) geht. (btw 10millionen element sind nun jetzt wirklich nicht ansatzweise viel, womit Quicksort vorrübergehen durchaus schneller sein kann, aber die O notation ist ja fürs unendliche gedacht)

 

[fragejava]

btw 10millionen element sind nun jetzt wirklich nicht ansatzweise viel,

ich muss zumindest 512mb Hauptspeicher zuweisen, damit mit Arrays.sort() überhaupt sortiert werden kann. Außerdem ist bei Elementen > 10 Millionen Arrays.sort() auf einmal schneller, vorher nicht. Das war das Phänomen. Und theoretisch ist man immer bei n^2. Bei zufälligen Eingaben dürfte die Wahl des Pivots aber egal sein, weshalb es dann schneller ist-aber egal, glaubt mir ja eh keiner

 

[HoaX]

Eben, du zeigst nur Code und stellst Behauptungen auf. Du zeigst nicht einmal wie du zu dem Schluss kommst was schneller ist (Code). Es ist in keiner Weise nachvollziehbar was du für Testwerte benutzt hast usw. Sowas ist nunmal kein Beweis!
Wo kommen denn deine Millionen Testwerte hier? Ich wette aus java.util.Random oder sonstigem Zufallszahengenerator... und das ist dann Praxisfremd!

 

[fragejava]

Man kann doch wohl sagen, dass bei zwei gleichen Programmen das Programm langsamer ist, dessen Änderung mehr Zeit benötigt. Denn dass ein Programm dann langsamer wird, wenn ein Teil langsamer geworden ist, ist doch wohl nicht beweisbedürftig. Ich vermute eher, ich soll dir das mal machen, weil du das selbst nichts hinkriegst.

 

[Sonecc]

Du behauptest also, dass dein Sort schneller ist als ein anderer, weil er bei ein paar Durchläufen schneller war?
Das ist insofern schon unglaubwürdig und unfundiert, als dass Hintergrundprozesse, die CPU, Speicher und Festplatte verwenden, den PC bremsen und damit deinen Test verfälschen. Desweiteren ist es (sagen wir mal...) gewagt Leute anzugreifen und als dumm hinzustellen, wenn du selbst keine Ahnung hast.

 

[SlaterB]

[..]gewagt Leute anzugreifen und als dumm hinzustellen, wenn du selbst keine Ahnung hast.

machst du das nicht gerade selber?

ich beobachte den Thread seit kurzem, fragejava hat einen gewissen Stil aber noch scheinen ja alle halbwegs zufrieden,
kein Grund für irgendwas,
soll jetzt aber bitte keiner weiterdiskutieren und sich später beschweren, jeder kann sofort aufhören hier zu posten

 

[HoaX]

Du konstruierst dir einen Testfall mit lauter Zufallszahlen, d.h. die Werte sind so gut wie garnicht vorsortiert. Das ist der Optimalfall für Quicksort, und vergleichst diesen gegen eine andere Implementierung.

Oben sagst du wir würden uns nicht für die Praxis interessieren aber selbst kümmerst du dich auch nicht darum! Dein Code mag evtl. in diesem einen Fall schneller sein, aber das ist Praxisfremd! Du beziehst dich auf einen Testfall, wir reden aber vom Gesamten, und darauf kommst es an.
Des weiteren habe ich bereits oben darauf hingeweisen dass Arrays#sort für die einzelnen Datentypen durchaus unterscheidlich implementiert ist. Du redest immernoch nur von Arrays#sort ohne zu sagen welches du verwendest, und schon alleine das macht deine Tests in keiner Weise nachvollziehbar.

Und argumentierst ziemlich Flach, "beweist" Dinge rein durch von dir aufgestellte, nicht ohne weiteres nachvollziehbare Behauptungen, und nennst uns Neunmalklug? Herzlichen Glühstrumpf!

 

[Jango]

...soll jetzt aber bitte keiner weiterdiskutieren und sich später beschweren, jeder kann sofort aufhören hier zu posten

Da fange ich erst an...

@ TO: Wolltest du nun Hilfe, oder jeden hier belehren? Das kam nicht so ganz klar rüber...

 

[Sonecc]

Sry für Off-Topic, aber da zuckte grade zweimal mein Finger Richtung Danke-Button.