Глава 43 пример 2 (Быстрая сортировка)

[Garrus_En]

Наткнулся на ошибку в коде второго примера.. запуск программы вывел мне странный реультат:
До сортировки:
549
593
716
845
603
858
545
848
424
624

После сортировки:
424
549
545
845
603
858
716
848
593
629


Из примера видно, что элементы попеременно поменялись местами:
2 с 9 , 1 со 2 , 3 с 6

Не пойму отчего так произошло? код переписан из примера полностью.

[Oleg_D]

Не пойму отчего так произошло? код переписан из примера полностью.

Выкладывайте свой код, посмотрим. Мой код таков:

Код: Выделить всё

{ P_43_2 - Быстрая сортировка }

const CSize=10;    { размер массива }

type TNumbers = array [1..CSize] of Integer;
var  Arr  : TNumbers;

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

procedure QuickSort(var arg: TNumbers; aL, aR: Integer);
var
    L, R : integer; { левый и правый индексы }
    M, T : Integer; { среднее значение и временное хранилище }
begin
    { Начальные значения левого и правого индексов }
    L:= aL;    R:= aR;
    { Вычисляем среднее значение }
    M:= (arg[L] + arg[(L + R) div 2] + arg[R]) div 3;
    { Цикл встречного движения }
    repeat
      { Пока левый элемент меньше среднего,
        двигаем левый индекс вправо }
      while arg[L] < M do L:=L+1;
      { Пока правый элемент больше среднего,
        двигаем правый индекс влево }
      while arg[R] > M do R:=R-1;
      { После остановки сравниваем индексы }
      if L <= R then begin
        { Если индексы еще не "встретились" }
        if arg[L]>arg[R] then begin
          { и левый элемент оказался больше правого,
            то меняем элементы местами }
          t:= arg[L];  arg[L]:= arg[R]; arg[R]:= t;
        end;
        { Делаем еще шаг навстречу }
        L:=L+1;  R:=R-1;
      end;
    until L > R; { пока индексы не "встретятся" }
    { если левая часть не отсортирована, то сортируем ее }
    if R > aL then QuickSort(arg, aL, R);
    { если правая часть не отсортирована, то ее тоже сортируем }
    if L < aR then QuickSort(arg, L, aR);
    { выход после сортировки обеих частей }
end;

{ Процедура распечатки массива }

procedure ShowArray(const arg: string);
var i: integer;
begin
  Writeln(arg);
  for i:=1 to CSize do Writeln(Arr[i]);
  Readln;
end;

var i: integer;

begin
  { Заполняем массив случайными числами }
  Randomize;
  for i:=1 to CSize do Arr[i]:=1+Random(1000);
  ShowArray('До сортировки:');
  QuickSort(Arr, 1, CSize);
  ShowArray('После сортировки:');
end.



[Garrus_En]

один в один.. сидел просматривал... символ к символу... почти ( ещё строку randomize; добавил перед заполнением)
может быть фпс неможет загнать этот цикл сам в себя?? на каком компиляторе проверялось?

[Oleg_D]

на каком компиляторе проверялось?

На FP 2.6.0 и на Delphi
А вы не глазами проверяйте, к копи-пастом на форум выкладывайте.

[Garrus_En]

Код: Выделить всё

        {P_43_2 QuickSort}
const CSize=10;         
type TNumbers = array [1..CSize] of integer;
var
   Arr:TNumbers;
Procedure QuickSort(var arg: TNumbers; aL,aR: integer);
var
        L,R: integer;   
        M,T: integer;   
begin
        L:=aL; R:=aR;
       

        M:=(arg[L]+arg[(L+R)div 2]+arg[R])div 3;
        repeat 
                while arg[L]<M do L:=L+1;
                while arg[R]>M do R:=R-1;
                if L <= R then begin
                if arg[L]>arg[R] then begin
            t:=arg[L]; arg[L]:= arg[R]; arg[R]:=t;
                        end;
                        L:=L+1; R:=R-1;
                end;
        until L>R;     
        if R>aL then quickSort(arg,aL,R);
        if L>aR then QuickSort(arg,L,aR);
        end;
        procedure ShowArray(const arg:string);
var i:integer;
begin
        Writeln(Arg);
        for i:=1 to CSize do Writeln(arr[i]);
        Readln;
end;
var i: integer;
begin           
        randomize;
        for i:=1 to CSize do Arr[i]:=1+random(1000);
        ShowArray('До сортировки:');
        QuickSort(Arr,1,CSize);
        ShowArray('После сортировки:');
end.

вот он

[Oleg_D]

Надо так:

if L < aR then QuickSort(arg, L, aR);

У вас так (больше вместо меньше):

if L > aR then QuickSort(arg,L,aR);

И старайтесь форматировать текст аккуратней, для сдвига блоков предварительно выделенного текста очень удобны комбинации клавиш:
Ctrl+K+I -- сдвиг блока вправо
Ctrl+K+U -- сдвиг блока влево
Ctrl+K+H -- отмена выделения блока

[Garrus_En]

Спасибо