quicksort

andro

habs selbst rausgefunden...

[ Dieser Beitrag wurde am 12.05.2003 um 20:12 Uhr von andro editiert. ]

andro

[ Dieser Beitrag wurde am 12.05.2003 um 18:56 Uhr von andro editiert. ]

Dill

lass uns doch teilhaben an deinem wissensgewinn ... besser als löschen

andro

nagut *g*

musste das unter zeitdruck verstehen und das problem war, dass ich nicht gleich erkannte, dass mit if ( li < re ) die Indexnummer des Arrays gemeint und
nicht wie ich immer angenommen habe, der Inhalt vom Array. Ist ja eigentlich logisch, dass Werte nur geswappt werden, wenn die untere Grenze < als die obere Grenze ist, denn man will ja keine bereits sortierten Bereiche wieder durcheinanderpuzzeln. Naja, die Funktion zur Partitionierung funktioniert aber wirklich ganz gut in der Praxis... So und jetzt steht hier wieder was cu

int partition( int ug, int og, int pivotkey ) {

    int li, re;

    li = ug;

    re = og;

    do {

  if  (a[li].key < pivotkey) li++;

  if (a[re].key >= pivotkey) re--;

        if ( li < re ) {
           swap(re,li);
           // FORALL i in {ug..li} . a[i].key < pivotkey
           // FORALL j in {re..og} . a[j].key >= pivotkey
    }

    } while ( li <= re );

    return li;

}