Einzelnen Beitrag anzeigen

shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#2

Re: Anfängerproblem mit Quicksort...

  Alt 26. Jan 2010, 18:42
Beim Quicksort-Algorithmus können ganz kleine Änderungen wie z.B. kleiner-gleich (<=) statt kleiner (<) teilweise grosse Konsequenzen haben.

Manchmal ist es auch so, dass Quicksort trotzdem noch sortiert dann aber bei bestimmten Eingangsmengen ein sehr ungünstiges Laufzeitverhalten zeigt.

Man muss also sehr vorsichtig sein wenn man an Quicksort etwas "verbessern" will.

Wenn man sich den Pseudocode auf Wikipedia anschaut:
Code:
procedure quicksort(array, left, right)
  if right > left
    select a pivot index (e.g. pivotIndex := (left+right)/2)
    pivotNewIndex := partition(array, left, right, pivotIndex)
    quicksort(array, left, pivotNewIndex - 1)
    quicksort(array, pivotNewIndex + 1, right)
Dann fällt auf, dass hier +1 und und -1 bei den rekursiven Aufrufen verwendet wird.
Das ist bei deinem Code nicht der Fall.
Andreas
  Mit Zitat antworten Zitat