Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 04.12.2012, 15:09   #1
New man
Форумчанин
 
Регистрация: 24.01.2011
Сообщений: 774
По умолчанию Странности с быстрой сортировкой

Я напсал простенькую программку на Delphi 7, которая требует от
пользователя число, затем создает случайный массив и сортирует его.
затем выводит на экран.
Почему-то при длине массива больше трех, программа выдает
EStackOverflow. Причем ошибку вызывает именно быстрая сортировка.
Спрашивается, почему? Помогите, дорогие форумчане.
Код:
program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var arr:array of longword;
  fix:longword=0;
function Qs(l,h:byte):longword;
var x,m:longword;
   i,j:byte;
begin
  x:=arr[random(h-l+1)+l];
  i:=l;
  j:=h;
  inc(fix);
  repeat
    while arr[i]<x do inc(i);
    while arr[j]>x do dec (j);
    if i<j then
      begin
        m:=arr[i];
        arr[i]:=arr[j];
        arr[j]:=m;
        inc(i);
        dec(j);
      end;

  until i>=j;
  result:=1;
  if h>i then inc(result,Qs(i,h));
  if j>l then inc(result,Qs(l,j));

end;
var a,b,c,n,i:byte;
begin
  n:=0;
  i:=0;
  readln(n);
  setlength(arr,n);
  randomize;
  for i:=0 to n-1 do
  begin

      arr[i]:=random(24)*3600+random(60)*60+random(60);
  end;
     for i:= 0 to n-1 do
    writeln(arr[i]div 3600:2,' ',arr[i]div 60 mod 60:2,' ',arr[i]mod 60:2,' ');

   try
   writeln('Depth: ',Qs(0,n-1));
   readln;
   except
   end;
   writeln ('FIX: ',fix);
   readln;
   writeln('Âûâîä');
   for i:= 0 to n-1 do
    writeln(arr[i]div 3600,' ',arr[i]div 60 mod 60,' ',arr[i]mod 60,' ');
   readln;
   readln;
   readln;
   readln;
end.
a.k.a. Angelicos Phosphoros
Мой сайт
New man вне форума Ответить с цитированием
Старый 04.12.2012, 15:35   #2
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

А зачем внутри сортировки рандом?
s-andriano вне форума Ответить с цитированием
Старый 04.12.2012, 15:35   #3
Xardas
Сисадмин
Форумчанин
 
Аватар для Xardas
 
Регистрация: 28.12.2007
Сообщений: 320
По умолчанию

Рекурсия -> не совсем корректное условие завершения рекурсии -> переполнение стека. Я не разбирался в этом коде, при длине массива 10, 3 раза выполнилась программа, 1 раз - переполнение стека. Массив заполняется случайными числами, вероятно, что какие-то значения препятствуют корректному выходу из рекурсии
Xardas вне форума Ответить с цитированием
Старый 04.12.2012, 15:37   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Потому что рекурсия оказывается бесконечной. Добавьте отладочную печать, выводите то, с какими аргументами вызывается Qs.
Abstraction вне форума Ответить с цитированием
Старый 04.12.2012, 18:22   #5
New man
Форумчанин
 
Регистрация: 24.01.2011
Сообщений: 774
По умолчанию

Код:
if i<j then
      begin
        m:=arr[i];
        arr[i]:=arr[j];
        arr[j]:=m;
        inc(i);
        dec(j);
      end;
В этом участке надо изменить условие на <=
Ошибка в один символ, а такие последствия...
a.k.a. Angelicos Phosphoros
Мой сайт
New man вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Странности с полиморфизмом _Bers Общие вопросы C/C++ 4 03.02.2012 20:48
Ограничитель в быстрой сортировке Юлия999 Помощь студентам 1 08.06.2011 10:47
странности ControlServiceEx() m_kostik Win Api 5 28.10.2010 20:39
Метод быстрой сортировки Nord18 Паскаль, Turbo Pascal, PascalABC.NET 1 05.06.2010 11:24
сортировка массива Методом Хоара (быстрой сортировкой) wild-weight Паскаль, Turbo Pascal, PascalABC.NET 3 26.09.2009 16:46