Java-Implementierung von Quick Sort

78034
user830818

Dies ist meine Implementierung von Quicksort (Algorithmus aus dem Cormen-Buch). Dies ist eine Implementierung vor Ort. Bitte lassen Sie uns Probleme mit dieser oder anderen Ideen wissen, um sie zu verbessern. Es führt bei logN aus.

import java.util.ArrayList;

public class MyQuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {

        //int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 };
        int a[]={23,44,1,2009,2,88,123,7,999,1040,88};
        quickSort(a, 0, a.length - 1);
        System.out.println(a);
        ArrayList al = new ArrayList();
    }

    public static void quickSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }

    private static int partition(int[] a, int p, int r) {

        int x = a[p];
        int i = p-1 ;
        int j = r+1 ;

        while (true) {
            i++;
            while ( i< r && a[i] < x)
                i++;
            j--;
            while (j>p && a[j] > x)
                j--;

            if (i < j)
                swap(a, i, j);
            else
                return j;
        }
    }

    private static void swap(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
Antworten
24
Dies ist O (n log n) nicht log n smohamed vor 7 Jahren 4
Aufgrund der Rekursion wird es nicht skaliert: Die JVM hat keine Optimierung für das Aufrufaufruf. Sie erhöht den Methodenaufrufstapel einfach auf einen Wert, der proportional zum zu sortierenden Array ist, und schlägt bei einem zu großen Array fehl. (Und selbst für Sprachen / Plattformen, die * eine * Tail Call-Optimierung haben, glaube ich nicht, dass sie es tatsächlich auf diesen Code anwenden könnten) Shivan Dragon vor 6 Jahren 0
Ich denke, es ist erwähnenswert, dass die Partitionsmethode das Pivot nicht zum endgültigen Ziel führt, was sich von dem klassischen QuickSort unterscheidet, das Sie auf Wikipedia überprüfen können. Ajk_P vor 5 Jahren 0

5 Antworten auf die Frage

21
Jeff Mercado

Wenn der Algorithmus einem Buch entnommen wurde, ist die Wahrscheinlichkeit groß, dass er so gut wie möglich ist. So lange Sie dem Buchstaben gefolgt sind, sollte Ihre Implementierung wirklich keine Probleme haben.

Es gibt jedoch eine Sache, die meiner Meinung nach verbessert werden könnte, die Schnittstelle, um die Sortierung einzuleiten. Wenn ich darüber nachdenke, eine Sammlung zu sortieren, würde ich erwarten, ein paar Dinge bereitzustellen, natürlich die Sammlung und möglicherweise einen Vergleich. Alles andere, was die Weitergabe von implementierungsspezifischen Werten erfordert, fühlt sich für mich einfach "falsch" an. Es könnte in Ordnung sein, wenn diese Indizes den Start- und Stop-Bereich der zu sortierenden Werte darstellen, aber ich würde das immer noch als separate Überladung machen.

Ihre Implementierung hingegen erfordert die Sammlung und die Indizes, die für den Algorithmus erforderlich sind. Dies wäre keine ideale Schnittstelle zum Arbeiten, da Sie daran denken müssen, bestimmte Werte zu übergeben, um die Sortierung durchzuführen, wenn sie stattdessen für mich berechnet werden könnten. Ich würde eine Überladung aufdecken, die nur die Auflistung akzeptiert, um die tatsächliche Implementierung mit den richtigen Argumenten aufzurufen.

Auch wenn dies der bekannte Schnellsortieralgorithmus ist, würde ich immer noch bessere Variablennamen angeben. Nicht wirklich ein Problem, persönliche Vorlieben.

// this overload is the public interface to do the sort
public static void quickSort(int[] collection)
{
    quickSort(collection, 0, collection.length - 1);
}

// note: method is now private
private static void quickSort(int[] collection, int pivotIndex, int rangeIndex)
{
    // etc...
}
+1 für die Variablennamen würde den Code klarer machen. Der Code ist ziemlich gut in Funktionen unterteilt, anstelle des üblichen Wirrwarrs, das wir oft gesehen haben (dies richtet sich an niemanden im Besonderen). Eric-Karl vor 9 Jahren 3
8
Landei

Ich sehe eine kleine Verbesserung. Anstatt...

i++;
while ( i< r && a[i] < x)
  i++;
j--;
while (j>p && a[j] > x)
  j--;

...Du kannst schreiben:

do {
  i++;
} while (i < r && a[i] < x);
do {
  j--;
} while (j > p && a[j] > x);

Und Jeff hat recht mit der öffentlichen Schnittstelle.

6
zeruitle

Wenn Sie versuchen, eine bereits sortierte Array-Größe über 20000 zu sortieren, führt dies zu einem Stapelüberlauf. Die Partition hat Probleme, wenn auf ein großes sortiertes Array gestoßen wird.

6
Pedro Dusso

Es sieht wirklich gut aus, aber ich empfehle immer diese Richtlinien, wenn jemand noch einmal eine Schnelle Sortierung programmieren muss:

  1. Randomisierung: Zufällige permutierende Schlüssel können O (n²) vermeiden, wenn Daten nahezu sortiert werden.
  2. Baum-Median: Verwenden Sie den Median des ersten, mittleren und letzten Elements, um den Drehpunkt auszuwählen. Je größer die Daten, desto mehr Proben.
  3. Lassen Sie kleine Sub-Arrays für die Insertion-Sortierung: Beenden Sie die Quicksort-Rekursion und wechseln Sie zur Insert-Sortierung, wenn weniger als 20 Elemente vorhanden sind:

         // Insertion sort on smallest arrays
         if (rangeIndex < 20) {
             for (int i=pivotIndex; i < rangeIndex + pivotIndex; i++)
                 for (int j=i; j > pivotIndex && x[j-1]>x[j]; j--)
                     swap(x, j, j-1);
             return;
         }
    
  4. Machen Sie zuerst die kleinere Partition: Für die Rekursion wird nur O (logn) Speicherplatz benötigt

Alle diese Tipps stammen aus dem ausgezeichneten Buch The Algorithm Design Manual von Steven Skiena.

3
user30155

Ich sehe eine weitere Verbesserung. Ich denke, es ist sinnvoller zu denken, dass sich die Marker ( iund j) bewegen sollten, nachdem der Austausch abgeschlossen ist. Es bereinigt den Code um ein paar Zeilen und ist sinnvoller.

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p;
    int j = r;

    while (true) {
        while (i < r && a[i] < x)
            i++;
        while (j > p && a[j] > x)
            j--;

        if (i < j) {
            swap(a, i, j);
            i++;
            j--;
        } else {
            return j;
        }
    }
}