Ergebnis der Suchanfrage

• Forum: Algorithmen, Datenstrukturen und Klassendesign

  AW: Quicksort - theorie

    Delphi
    by Uwe Raabe, 14. Mai 2013
  So in etwa. In dem Fall sind iLo=0 und iHi=1. Die erste while-Schleife läuft nicht, da A = mid ist. Die zweite wird einmal durchlaufen. Danach sind Lo = 0 = Hi und die if-Bedingung schlägt zu, tauscht dabei aber nur A mit A, was ja nichts ändert. Dann haben wir nach Inc(Lo) und Dec(Hi) Lo = 1 und Hi = -1. Das bringt die repeat-Schleife zum Abbruch und die rekursiven Aufrufe erfolgen auch nicht.
• Forum: Algorithmen, Datenstrukturen und Klassendesign

  AW: Quicksort - theorie

    Delphi
    by Uwe Raabe, 14. Mai 2013
  Das ist bei dieser Implementation von Quicksort so, muss aber nicht zwingend so sein. Es gibt auch Implementierungen, die das Pivot-Element gar nicht in die Rekursion mit einfließen lässt. Geht man wie in diesem Fall davon aus, daß kein Wert doppelt vorkommt, dann kann man das Pivot-Element auch zwischen den Listen anordnen.
  
  
  
  
  Ich weiß nicht genau, was du damit meinst. Lo und Hi sind...
• Forum: Algorithmen, Datenstrukturen und Klassendesign

  AW: Quicksort - theorie

    Delphi
    by Uwe Raabe, 14. Mai 2013
  Das ist genau der Punkt. QuickSort wird nach dem repeat-until rekursiv aufgerufen. Einmal für A] = (3,2,4,1) und dann für A = (8,7,6,9,5). Zu diesem Zeitpunkt sind aber alle Werte im unteren Array-Bereich kleiner als die Werte im oberen Array-Bereich. Jeder rekursive Aufruf sortiert also nur noch einen Teilbereich des gesamten Arrays. Der repeat-until Block im Quicksort sortiert nicht die Zahlen...
• Forum: Algorithmen, Datenstrukturen und Klassendesign

  AW: Quicksort - theorie

    Delphi
    by Uwe Raabe, 14. Mai 2013
  Start: L=0, Hi=8, A=3, A=5, Mid=4
  repeat
  nach den beiden while-Schleifen: Lo=1, Hi=5, A=7, A=2
  if-Bedingung ist true, also tauschen und Lo/Hi weiterbewegen: Lo=2, Hi=4, A=8, A=4
  until-Bedingung ist false, also weiter nach repeat
  beide while-Schleifen werden nicht durchlaufen, da A{8} < Mid {4} und A {4} < Mid {4} fehlschlagen
  if-Bedingung ist immer noch true, also tauschen und weiterbewegen...
• Forum: Algorithmen, Datenstrukturen und Klassendesign

  AW: Quicksort - theorie

    Delphi
    by Uwe Raabe, 13. Mai 2013
  Low(A) und High(A) geben den unteren und oberen Index von Array A zurück - nicht die Werte an diesen Positionen. Damit haben iLo und iHi beim ersten Aufruf auch die Werte 0 und 8 und nicht 3 und 5.
  
  Edit: Die Methode funktioniert übrigens.