DELPHI - QuickSort

Dla specjalistów Programowanie
#1

Witam, mam problem! Nie chodzi tu o błąd w kodzie programu, tylko o jego funkcjonowanie.

procedure QuickSort(var A: array of Integer);

procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);

  var

    Lo, Hi, Mid, T: Integer; begin

    Lo := iLo;

    Hi := iHi;

    Mid := A[(Lo + Hi) div 2];

    repeat while A[Lo] < Mid do Inc(Lo);

      while A[Hi] > Mid do Dec(Hi);

      if Lo <= Hi then

      begin

        T := A[Lo]; A[Lo] := A[Hi];

        A[Hi] := T;

        Inc(Lo);

        Dec(Hi);

      end; until Lo > Hi;

    if Hi > iLo then Quick_Sort(A, iLo, Hi);

    if Lo < iHi then Quick_Sort(A, Lo, iHi);

  end;

 begin

  Quick_Sort(A, Low(A), High(A));

end;

Dostałem ciąg liczb:

3-7-8-1-[4]-2-6-9-5

Program dzieli pole na pół, więc Mid=4 - Uzyskujemy element Pivot.

Lo=iLo=3

Hi=iHi=5

3 i 5 stoją na właściwych pozycjach więc przesuwa Lo i Hi oczko w lewo i prawo.

Lo natrafiło na liczbę 7 ,która jest większa niż 4.

Hi natrafiło na liczbę 2 ,która jest mniejsza niż 4.

Liczby zostają zamienione

3-(2)-8-1-[4]-(7)-6-9-5

Lo=8

Hi=4

I tu jest problem, nie wiem co dalej zrobi program:

Wychodzi na to że liczby 4 i 8 mają być zamienione.

3-2-[4]-1-(8)-7-6-9-5

Lo=1

Hi=1

Wtedy Lo i Hi miało by tą samą wartość, więc program skończyłby swoją prace, choć 1 powinno być po lewej stronie 4.

Robię gdzieś błąd, mógłby mi ktoś pomóc, powiedzieć gdzie leży błąd i pokazać jak program będzie sortował dalej?

Z góry dziękuję.

PS. To mój pierwszy post, jeśli napisałem go w złym dziale proszę o przeniesienie !

#2

Wycięte bo głupoty były sam pomyliłem indeksy z wartościami brzegu iLow, iLo - lepsze nazwy (czytelniejsze) następnym razem. Jest ok.

Teraz rekursywnie wywołasz sortowanie dla tablic 3 2 4 1 a drugi if dla 8 7 6 9 5, tylko ze w ramach pierwszego wywołania nastąpi kolejne (przechodzenie drzewa wywołań rekursywnych pre-order)

#3

Moim skromnym ( bo średnio się na tym znam ) zdaniem, Mid czyli wartość [4] nie powinna wchodzić w dalsze sortowanie. W miejsce 1 powinno się znaleść 4 , wtedy zmienne by miały parametry:

iLo:3

Lo:1

Mid:4

iHi:5

Hi:8

Wtedy sortowanie wywołałoby się rekursywnie przez 2 pola:

3-2-1

oraz

8-7-6-9-5

Moim zdaniem coś źle zrozumiałem, dlatego ta 4 i 1 są na złych pozycjach. Myślę że znajdzie się ktoś kto skoryguję mój błąd.