quciksort

habe das selbe im rund um die programmierung schon gepostet aber vlt wars da falsch?

ich habe ein problem mit der sedgewickvariante von quicksort (ich bin mir bewusst dass es evt mehrere Varianten davon geben wird hoffe aber dass sich alle ähneln)...

ich soll bestimmen wie viele Vergleiche dieser Algorithmus bei n gleichen werten benötigt... wenn ich es mit stift und zettel versuche komme ich immer wieder auf etwa n^2 vergleiche... ich habe einen algorithmus aus dem internet gesucht und diesen getestet und da werden angeblich nur 2 vergleiche vorgenommen... beides verwirrt mich...

beim ersten dachte ich dass der worst case für quicksort bei einem vorsortiertem feld vorläge und nicht bei n gleichen werten

zum zweiten kann ich mir nicht vorstellen dass 2 vergleiche ausreichen (paarweiser vergleich = n log n????)

hier ist der code den ich in meinem skript habe, vlt befindet sich darin ja ein fehler

Zum sortiern eines Arrays mit den Grenzen l und r: 

Ist r > l Dann 
{ 
    i = l; j=r; x=F[l]; 
    Wiederhole bis j<i 
    { 
        Wiederhole 
        { 
            i = i+1; 
        } solange F[i] < x; 
        Wiederhole 
        { 
            j = j-1; 
        } solange F[j] > x; 
        Ist j<i 
            Verlasse die Schleife 
        Vertausche F[i] mit F[j]; 
    } 
    Vertausche F[l] mit F[j]; 
    Qicksort(l,j-1); 
    Quicksort(i,r); 
}

ist daran etwas falsch??
ich habe es leider niocht geschafft das in java zu schreiben, vor allem da ich nicht weiß wie r und l laufen sollen von 0 bis n-1 oder 1 bis n?
muss ich bei einem Zugriff etwas anpssen etwa F[j-1] oder so??
ich bekomme immer nur ArrayBoundExceptions und das obwohl ich jede erdenkliche Kombination mal probiert habe(n sollte)

PRIEST

http://de.wikipedia.org/wiki/Quicksort

pseudocode und struktogramm

uch kenne das struktogramm und auch alles andere und habe fleißig gegooglet nur
wir sollen das verwenden was wir aufgeschrieben haben und das unterscheidet sich von dem doch etwas oder täuscht der eindruck?