Versionsvergleich

Aus ProgrammingWiki

Vergleich: 2010-04-10T12:25:58+00:00 → 2011-01-10T19:41:03+00:00

<language>Java</language>
== Quicksort in Java ==
'''Der Algorithmus'''
<code id="4bbdf8e39a9bd">
−
    private int[] a;
−
    private int n;
+
void quicksort (int[] a)
+
{
+
    int n=a.length;
+
    quicksort(a, 0, n-1);
+
}
−
    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 ? "," : ""));
−
    }
+
void quicksort (int[] a, int lo, int hi)
+
{
+
    int i=lo, j=hi;
+
    int x=a[(lo+hi)/2];
−
    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);
+
    //  Aufteilung
+
    while (i<=j)
+
    {    
+
       while (a[i]<x) i++; 
+
       while (a[j]>x) j--;
+
       if (i<=j)
+
       {
+
         exchange(a,i, j);
+
         i++; j--;
+
       }
    }
−
    private void exchange(int i, int j)
−
    {
−
        int t=a[i];
−
        a[i]=a[j];
−
        a[j]=t;
−
    }
−
   
+
    // 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>
−
<eval id="4bbf141066923">
+
<run id="4bbf141066923">
int[] a = new int[] {1,42,5,23,6,5,34,52,911,2,31,4,100};
−
sort(a);
−
</eval>
+
quicksort(a);
+
display(a);
+
</run>
Quelle: [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm FH-Flensburg]