| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Быстрая сортировка

TUser ©   (2005-02-19 15:20:00) 

Посмотрите, plz, почему этот код не работает. Пузырьками сортирует правильно, а QuickSort дает ошибку. После долгого отлаживания я перерисовал код из Борландовского Classes.pas, но он все равно не пашет. Может быть кто-нибудь увидит ошибку, которую не вижу я.
Спасибо.

begin
   {
   for i:=0 to length(S)-1 do
     for m:=length(S)-1 downto i+1 do
       if CompareGroups(S[m].Pos1, S[m].Pos2, S[m].Chain1, S[m].Chain2,
                        S[m-1].Pos1, S[m-1].Pos2, S[m-1].Chain1, S[m-1].Chain2) < 0 then
         Swap(m,m-1);

         }

   repeat
     i:=L; j:=R;
     m:=(L + R) shr 1;
     repeat
        while CompareGroups(S[i].Pos1, S[i].Pos2, S[i].Chain1, S[i].Chain2,
                            S[m].Pos1, S[m].Pos2, S[m].Chain1, S[m].Chain2) < 0 do
           inc (i);
        while CompareGroups(S[j].Pos1, S[j].Pos2, S[j].Chain1, S[j].Chain2,
                            S[m].Pos1, S[m].Pos2, S[m].Chain1, S[m].Chain2) > 0 do
           dec (j);
        if i <= j then begin
           Swap(i,j);
           inc (i); dec(j);
           end;
     until i > j;
     if L < j then
        Sort(S,L,j);
     L:=i;
   until i >= R;
end;

---

begin...end   (2005-02-19 16:20:00) [1]

И не забываем про функцию CompareValue из модуля Math.

---

MBo   (2005-02-19 16:12:00) [2]

функцию сравнения для читабельности сделай такой:
function CompareGroups(ScoreRec1,ScoreRec2: TScoreRec): shortint;

procedure QuickSortRecs(var A: array of TScoreRec);

 procedure QuickSort(var A: array of TScoreRec; iLo, iHi: Integer);
 var
   Lo, Hi : Integer;
   Mid:TScoreRec;
 begin
   Lo := iLo;
   Hi := iHi;
   Mid := A[(Lo + Hi) div 2];
   repeat
     while CompareGroups(A[Lo], Mid) < 0 do Inc(Lo);
     while CompareGroups(A[Hi], Mid) > 0  do Dec(Hi);
     if Lo <= Hi then
       SwapRecs(A[Lo], A[Hi]);
   until Lo > Hi;
   if Hi > iLo then QuickSort(A, iLo, Hi);
   if Lo < iHi then QuickSort(A, Lo, iHi);
 end;

begin
 QuickSort(A, Low(A), High(A));
end;


---

TUser   (2005-02-19 16:05:00) [3]

Кстати, если упихать все это дело в TList - то все нормально сортируется. Там используется QuickSort, причем код я уже оттуда срисовал один в один. Вот и хотелось бы понять, - почему кодгда код пищут программисты Борланда, он работает, а когда точно такой же код пишу я, - получается ерунда какая-то? :)

---

TUser   (2005-02-19 15:53:00) [4]

Массив из вот таких записей

  TScores = array of
   record
     Chain1, Chain2: TChain;
     Pos1, Pos2: integer;
     Value: single;
   end;

Ну, и есть функция, по которой они сравниваются
function CompareGroups(Pos11, Pos21: integer;
                      Chain11, Chain21: TChain;
                      Pos12, Pos22: integer;
                      Chain12, Chain22: TChain): shortint;

procedure C(I1, I2: integer);
begin
  if I1 < I2 then
    result:=-1
    else
  if I1 > I2 then
    result:=1
    else
    result:=0;
end;

begin
 C(Pos11, Pos12);
 if result = 0 then
   C(Pos21, Pos22);
 if result = 0 then
   C(integer(Chain11), integer(Chain12));
 if result = 0 then
   C(integer(Chain21), integer(Chain22));
end;

---

MBo   (2005-02-19 15:31:00) [5]

Опиши, что нужно сортировать.

---

Наверх