AuK/Teile und Herrsche 1 SS10/JavaQuick

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Quicksort in Java ==

'''Der Algorithmus'''

<code id="4bbdf8e39a9bd">
void quicksort (int[] a)
{
    int n=a.length;
    quicksort(a, 0, n-1);
}

void quicksort (int[] a, 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(a,i, j);
         i++; j--;
       }
    }

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

void exchange(int[] a, int i, int j)
{
    int t=a[i];
    a[i]=a[j];
    a[j]=t;
}

void display(int[] a)
{
    for(int i=0; i < a.length; i++) System.out.print(a[i]+ (i < a.length-1 ? "," : ""));
}
</code>

<run id="4bbf141066923">
int[] a = new int[] {1,42,5,23,6,5,34,52,911,2,31,4,100};
quicksort(a);
display(a);
</run>

Quelle: [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm FH-Flensburg]