JavaQuick

Aus ProgrammingWiki

Archivierte Version vom 2010-04-09T11:52:56+00:00. Aktuelle Version

Quicksort in Java

Der Algorithmus

public Object Quicksorter ()
{
    private int[] a;
    private int n;

    public void sort(int[] values)
    {
        a=values;
        n=a.length;
        quicksort(0, n-1);
        for(int i=0; i < a.length; i++) System.out.print(a[i]+ (i < a.length-1 ? "," : ""));
    }

    private void quicksort (int lo, int hi)
    {
        int i=lo, j=hi;
        int x=a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j)
        {    
            while (a[i]<x) i++; 
            while (a[j]>x) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public int[] getArray(){
    	return a;
    }  
    return this;
}

<eval id="4bbf141066923"> QuickSort = Quicksorter (); QuickSort.sort(new int[] {1,42,5,23,6,34}); </eval>

Hinweis: Typisches OOM-Overkill-Beispiel. Es wäre sinnvoller eine statische Java-Methode für Quicksort anzubieten, die ein Array nimmt und das sortierte Array zurückliefert. Alternativ könnte man ein SortableArray von Array erben und die quicksort Methode hinzufügen - was hier im Wiki aber nicht gut geht. 20% von diesem Javacode haben eigentlich nichts mit dem Algorithmus zu tun. Überlegt doch mal ob ihr das nicht vereinfachen könnt :-)

JavaQuick

Quicksort in Java

Suche