4. Pivot im Quicksort Algorithmus bestimmen

Pivot im Quicksort Algorithmus bestimmen

  • A

    Hallo,

    ich habe unten stehenden Quellcode, indem die Funktion zur Ermittlung des Pivotelements eines Quicksort-Suchalgorithmus geschrieben ist. Diese funktioniert nicht mit der Formel für das Pivotelement=(ug+og)/2.

    Könnt Ihr das mal prüfen, ob ich das richtig beschreibe:

    1. Der Funktion Findpivot wird der Array-Index-Bereich ug-og übermittelt.
    2. Zwei Hilfs-Variablen werden deklariert.
    3. Firstkey bekommt den ersten Wert aus dem Array-Index 0 zugewiesen, wobei man an .key sieht, dass hier die Schlüsselwerte sortiert werden.
    4. Die Startbedingung der For-Schleife macht iCnt=ug+1 und addiert zu iCnt den Wert 1, solange iCnt <= og gültig ist.

    5. Mit der If Verzweigung wird überprüft, ob der Schlüssel wom zweiten Index beginnend größer als das erste Index ist.
    6. Ist das der Fall, wird der Index-Wert von iCnt an die For-Schleife zurückgegeben

    7. Ist das nicht der Fall, wird mit else if geprüft, ob icnt kleiner als firstkey ist.
    8. Ist das der Fall, wird ug an die For-Schleife zurückgegeben.

    /***********************************************************************
 * Suchen des Pivot-Elementes im Array-Index-Bereich ug..og
 ***********************************************************************/

int findpivot(int ug, int og) {

    int firstkey;
    int iCnt;

    firstkey = a[ug].key;

    for (iCnt = ug + 1; iCnt <= og; iCnt++) {
    if ( a[iCnt].key > firstkey ) 
        return iCnt;
        else if ( a[iCnt].key < firstkey )
            return ug;
    }

    // FORALL i in {ug..og} . a[i].key = a[ug].key
    return ALL_IDENTICAL;

}

//POST: findpivot(ug,og) != ALL_IDENTICAL =>
//        EXISTS i in {ug..og} . 
//              a[i].key < a[findpivot(ug,og)].key
//      findpivot(ug,og) = ALL_IDENTICAL => 
//        FORALL i in {ug..og} . a[i].key = a[ug].key
    0
  • R

    Laut Deinem Code ist a ein Array, in dem Daten unsortiert liegen. Warum sollte die Suche nach dem Pivotelement also erst bei a[ug] beginnen, wenn es möglicherweise sogar auf a[0] liegt?

    0
  • A

    so sieht z.B. mein Array aus:
    4|5|9|13|2|12|1

    Dann wird doch zu Beginn das zweite Element aus dem Array mit dem Ersten verglichen und dann das nächste mit dem Ersten, solange bis die for schleife beim 4 Element mit dem Inhalt 2 angekommen ist. Denn 2<4 :). Oder bricht die Schleife schon beim ersten return ab und das pivotelement wäre schon mit 5 gefunden ??? Funktion siehe oben... Brauche dringend Hilfe

    0
  • A

    ach die Schleife geht nur solange, wie die zu vergleichenden Elemente gleich sind, right ?

    0
  • R

    Wie sieht Dein Aufruf aus?

    [ Dieser Beitrag wurde am 12.05.2003 um 16:22 Uhr von RenéG editiert. ]

    0
  • A

    Hallo Rene,
    danke für die Hilfe:

    habs herausgefunden 🙂 🙂

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

    0
Anmelden zum Antworten