quicksort

[witch doctor]

Ich habe hier ein Java Programm, welches den Quicksort ausführt.

Ich habe dazu mal eine kleine Frage. Aber zunächst erstmal das Programm.

package quicksort;

public class quicksorter

{

    private int[] a;

    public void sort(int[] a0)

    {

        a=a0;

        quicksort(0, a.length-1);

    }

    private void quicksort (int lo, int hi)

    {

        int low=lo, high=hi;

        int x=a[(lo+hi)/2];

        //  Aufteilung

        while (low<=high) //Zeiger haben sich noch nicht getroffen

        {    

            while (a[low]<x) low++; 

            while (a[high]>x) high--;


            if (low<=high)

            {

                exchange(low, high); //ruft Tauschfunktion auf

                low++; high--;

            }

        }

        // Rekursion

        if (lo<high) quicksort(lo, high);

        if (low<hi) quicksort(low, hi);

    }


    private void exchange(int i, int j) //Tauschfunktion

    {

        int t=a[i];

        a[i]=a[j];

        a[j]=t;

    }

}    // end class QuickSorter

Eigentlich verstehe ich nur folgende Programmzeile nicht:

if (lo<high) quicksort(lo, high);

if (low<hi) quicksort(low, hi);

Wieso einmal lo<high und low<hi???

Ich hoffe ihr könnt mir helfen.

[Crush]

Da low als unterer Grenzwert hochgezählt und high als oberer Grenzwert bei jedem Tausch runtergezählt wird, dürfen diese nicht miteinander verglichen werden, sondern mit der oberen oder unteren Grenze. Deshalb das inkrementierende low mit dem feststehenden hi und das dekrementierende high mit dem festehenden lo. Diese Werte werden rekursiv in den Quicksort wieder eingebracht und das Sortierfeld dabei immer wieder halbiert, bis es nicht mehr teilbar ist. Es wird zweimal als if-Abfrage rekursiv durchlaufen. Durch die Rekursionsschleife wird zuerst (lo<high) bis zur Unteilbarkeit durchlaufen und danach (low<hi).

[witch doctor]

Ach so! Beim näheren Nachdenken und dem Aufzeichnen einer Zahlenreihe wurde es mir klar! Danke!!

Wie sähe das denn iterativ aus? Würde das dann mit einer while-Schleife gelöst werden?

while(lo<high)

       {

            teile und tausche

         }

[Crush]

Ja genau, so kann man das auch betrachten. Es sind zwei While-Schleifen hintereinander:

while(lo<high) { teile und tausche }

while(low<hi) { teile und tausche }

Man kann ja praktisch jede Rekursion iterativ darstellen.