LINUX.ORG.RU
решено Форум — Development  

Сортировка пузырьком и делфи

 ,


2

2

Почему эта сортировка не работает? Компилятор ошибок не выдает, приложение запускается, но при осуществлении сортировки, приложение крашится, и выскакивает ошибка в связи с вызовом класса исключений...

//MArr- заданный пользователем и собранный из случайных чисел 2 мерный динамический массив из int'ов
//i-строки
//j-столбцы
        i:=Low(MArr);
        Sort:=true;
      
        while Sort do
        begin

        sort:=false;

          Repeat

          begin
          for j:= Low(MArr[i]) to High(MArr[i]) do    
            begin

            // перебор каждой ячейки строки от 1 до последней
            if ( j<High(MArr[i]) ) then
              begin
              if ( MArr[i, j]>MArr[i, j+1] ) then
              begin
              Sort:=True;
              Tmp:=MArr[i, j];
              MArr[i, j]:=MArr[i, j+1];
              MArr[i, j+1]:=Tmp;
              end;
              end

            else if ( i<High(MArr) ) then
            begin
            if ( MArr[i, j]>MArr[i+1, 0] ) then
              begin
              Sort:=True;
              Tmp:=MArr[i+1, 0];
              MArr[i+1, 0]:=MArr[i, j];
              MArr[i, j]:=Tmp;
              end;
            end;
            end;

            Inc(i);
          end;
          until (i=High(MArr)+1);
        end;
★

Последнее исправление: cetjs2 (всего исправлений: 2)

Ответ на: комментарий от Rot1

Это просто предположение, Delphi я не знаю, а в коде дельфийского пузырька разбираться желания не возникает.

Непонятно, почему ты запостил это на ЛОРе, не попытавшись найти причину ошибки с помошью дебагера?

theNamelessOne ★★★★★
()
Ответ на: комментарий от theNamelessOne

Попробовал дебаггером. Да, выход за пределы массива. Почему то 

 until (i=High(MArr)+1); 

 не останавливает цикл при достижении i заданного в условии значения. Даже если я напишу 
 until (i=High(MArr)-1); 
, он все равно не останавливает цикл...
Rot1 ★
() автор топика

ты бы вачпоинты на переменные поставил или просто отладочные принты воткнул. думаю это решит проблему.

exception13 ★★★★★
()
Ответ на: комментарий от Rot1

что-то с синтаксисом не так... Если после цикла for поставить ";", то из цикла выход осуществляется, но тогда сам цикл for не работает

Rot1 ★
() автор топика

Всем спасибо. Проблема была в цикле 

while Sort do


Нужно было обнулять "i" в его начале
Rot1 ★
() автор топика

Почему не наложить на матрицу линейный массив и не сортировать его?

bormant ★★★★★
()

Хорошо бы увидеть собственно задание.

bormant ★★★★★
()

Полагаю, вы собирались написать вместо приведенного кошмара что-то наподобие:

type TMatrix = array of array of Integer;

procedure BubbleSort(var m: TMatrix);
var Done: Boolean;
  procedure Swp(var a, b: Integer);
  var t: Integer;
  begin
    t:=a; a:=b; b:=t; Done:=False;
  end;
var i, j: Integer;
begin
  repeat
    Done:=True;
    for i:=Low(m) to High(m)-1 do begin
      for j:=Low(m[Low(m)]) to High(m[Low(m)])-1 do
        if m[i,j]>m[i,j+1] then Swp(m[i,j],m[i,j+1]);
      if m[i,High(m[Low(m)])]>m[i+1,Low(m[Low(m)])] then
        Swp(m[i,High(m[Low(m)])],m[i+1,Low(m[Low(m)])]);
    end;
    i:=High(m);
    for j:=Low(m[Low(m)]) to High(m[Low(m)])-1 do
      if m[i,j]>m[i,j+1] then Swp(m[i,j],m[i,j+1]);
  until Done;
end;

var
  m: TMatrix;
  i, j: Integer;
begin
  Randomize;
  SetLength(m,5,5);
  for i:=Low(m) to High(m) do for j:=Low(m[Low(m)]) to High(m[Low(m)]) do
    m[i,j]:=-99+Random(199);
  BubbleSort(m);
  WriteLn('M =');
  for i:=Low(m) to High(m) do begin
    for j:=Low(m[Low(m)]) to High(m[Low(m)]) do Write(m[i,j]:4); WriteLn;
  end;
end.

bormant ★★★★★
()

При желании можно заменить нулями все выражения Low(...), реализацию динамических массивов вряд ли кто-то будет переделывать:

procedure BubbleSort(var m: TMatrix);
var Done: Boolean;
  procedure Swp(var a, b: Integer);
  var t: Integer;
  begin
    t:=a; a:=b; b:=t; Done:=False;
  end;
var i, j: Integer;
begin
  repeat
    Done:=True;
    for i:=0 to High(m)-1 do begin
      for j:=0 to High(m[0])-1 do
        if m[i,j]>m[i,j+1] then Swp(m[i,j],m[i,j+1]);
      if m[i,High(m[0])]>m[i+1,0] then
        Swp(m[i,High(m[0])],m[i+1,0]);
    end;
    i:=High(m);
    for j:=Low(m[0]) to High(m[0])-1 do
      if m[i,j]>m[i,j+1] then Swp(m[i,j],m[i,j+1]);
  until Done;
end;

bormant ★★★★★
()
Ответ на: комментарий от bormant

Да. Про то, что можно еще и сокращать область сортировки я знаю. Это допишется

Rot1 ★
() автор топика
Ответ на: комментарий от bormant

Это чтобы не вызывать цикл перебора, когда сортировка больше не требуется. Спасибо за помощь и ответы. Приму их к сведению

Rot1 ★
() автор топика
Ответ на: комментарий от buratino

Можете читать как
«
Free Pascal

{$mode Delphi}
...
»
если от этого легче.

bormant ★★★★★
()
Ответ на: комментарий от Rot1

Это чтобы не вызывать цикл перебора, когда сортировка больше не требуется.

Нет.
По крайней мере это так не работает, как вы об этом говорите.
Пузырьку нужен минимум один проход, чтобы убедиться в отсортированности массива. Для этого вполне достаточно цикла с гарантированным одним проходом:

repeat
  Done:=True;
  {просмотр массива, при обмене установка Done:=False}
until Done;
Конструкция с while в этом случае неудобна, поскольку нужно дополнительно задавать значение флага перед входом в цикл:
Cont:=True;
while Cont do begin
  Cont:=False;
  {просмотр массива, при обмене установка Cont:=True}
end;

bormant ★★★★★
()
Последнее исправление: bormant (всего исправлений: 1)

Сокращение перебора:

procedure BubbleSort(var m: TMatrix);
var si, sj: Integer;
  procedure Swp(i, j, i2, j2: Integer);
  var t: Integer;
  begin
    t:=m[i,j]; m[i,j]:=m[i2,j2]; m[i2,j2]:=t; si:=i; sj:=j;
  end;
var i, j, ti, tj: Integer;
begin
  ti:=High(m); tj:=High(m[High(m)]);
  repeat
    si:=Low(m); sj:=Low(m[Low(m)]);
    for i:=Low(m) to ti-1 do begin
      for j:=Low(m[i]) to High(m[i])-1 do
        if m[i,j]>m[i,j+1] then Swp(i,j,i,j+1);
      if m[i,High(m[i])]>m[i+1,Low(m[i+1])] then
        Swp(i,High(m[i]),i+1,Low(m[i+1]));
    end;
    for j:=Low(m[ti]) to tj-1 do
      if m[ti,j]>m[ti,j+1] then Swp(ti,j,ti,j+1);
    ti:=si; tj:=sj;
  until (si=Low(m)) and (sj=Low(m[Low(m)]));
end;

или даже
procedure BubbleSort(var m: TMatrix);
var si, sj: Integer;
  procedure Test(i, j, i2, j2: Integer); inline;
  var t: Integer;
  begin
    if m[i,j]>m[i2,j2] then begin
      t:=m[i,j]; m[i,j]:=m[i2,j2]; m[i2,j2]:=t; si:=i; sj:=j;
    end;
  end;
var i, j, ti, tj: Integer;
begin
  ti:=High(m); tj:=High(m[High(m)]);
  repeat
    si:=Low(m); sj:=Low(m[Low(m)]);
    for i:=Low(m) to ti-1 do begin
      for j:=Low(m[i]) to High(m[i])-1 do Test(i,j,i,j+1);
      Test(i,High(m[i]),i+1,Low(m[i+1]));
    end;
    for j:=Low(m[ti]) to tj-1 do Test(ti,j,ti,j+1);
    ti:=si; tj:=sj;
  until (si=Low(m)) and (sj=Low(m[Low(m)]));
end;

bormant ★★★★★
()
Ответ на: комментарий от bormant

или, что то же самое:

procedure BubbleSort(var m: TMatrix);
var si, sj: Integer;
  procedure Test(i, j, i2, j2: Integer); inline;
  var t: Integer;
  begin
    if m[i,j]>m[i2,j2] then begin
      t:=m[i,j]; m[i,j]:=m[i2,j2]; m[i2,j2]:=t; si:=i; sj:=j;
    end;
  end;
var i, j, ti, tj: Integer;
begin
  si:=High(m); sj:=High(m[High(m)]);
  repeat
    ti:=si; tj:=sj; si:=Low(m); sj:=Low(m[Low(m)]);
    for i:=Low(m) to ti-1 do begin
      for j:=Low(m[i]) to High(m[i])-1 do Test(i,j,i,j+1);
      Test(i,High(m[i]),i+1,Low(m[i+1]));
    end;
    for j:=Low(m[ti]) to tj-1 do Test(ti,j,ti,j+1);
  until (si=Low(m)) and (sj=Low(m[Low(m)]));
end;

bormant ★★★★★
()
Ответ на: комментарий от UVV

адекватным

Зря ;)

но где пробелы?

Пробелы после запятых и двоеточий в объявлении переменных и в прототипах функций. Где ещё нужны пробелы, какие? Не совсем понимаю.

Предпочитаю компактный стиль, чтобы функция по-прежнему помещалась на экране. Каков ваш вариант приемлемого форматирования?

При адекватной раскраске (символы отличны от идентификаторов) никаких дополнительных пробелов не нужно.
Если считаете иначе, паскалевых форматтеров как грязи, нет?

bormant ★★★★★
()
Последнее исправление: bormant (всего исправлений: 2)

на хаскеле перепиши

anonymous
()
Ответ на: комментарий от UVV

Это вас QBasic покусал своим автоформатированием.
Там-то оно получалось даром (на автомате) и хоть выглядело вырвиглазно, не требовало лишних телодвижений.

Такой стиль также может быть хорош для чтения в VGA 132х25 и аналогичных режимах, но кто ими сейчас пользуется... Может быть хорош для высоких и узких шрифтов в редакторе кода, но таких исчезающие мало. В остальных случаях придётся «бегать глазами» и «вертеть головой» чтобы читать излишне длинные строки :)

Само по себе — пижонство это чистой воды, но мы же тут не в проекте, для которого был зачем-то выбран именно такой стиль, чтобы его придерживаться.

Больше скажу, поначалу читать подобный разбавленный пробелами код кажется удобным, как первоклашке букварь. Но со временем приобретаются навыки «скорочтения», и лишние пробелы начинают только мешать. Скорее всего, вы просто мало читали/писали паскалевского кода, не набрана критическая масса...

bormant ★★★★★
()
Ответ на: комментарий от Harald

психика была травмирована дельфёй

Порезаться пластилиновым шаром — это нужен особый талант, свой или преподавателя.

На Delphi/Lasarus вполне можно писать прикладное ПО, языковых средств pascal вполне достаточно.
Теперь-то многоопытный спец к осознанию того, какие именно элементы языка/среды нанесли травму, наверняка подошёл настолько, что готов поделиться? Просим, просим.

bormant ★★★★★
()
Ответ на: комментарий от bormant

Мы сейчас конкретно про паскаль или про программирование в принципе? Я просто на паскале лет 10 не писал.

UVV ★★★★★
()
Ответ на: комментарий от UVV

ТС начал про паскаль, пример с пробелами привели паскалевый, про паскаль и отвечал.

Безусловно есть случаи когда пробелы помогают, например, вызов с передачей нескольких параметров — длинных выражений, удобно раскидать на отдельные строки или поделить дополнительными пробелами. Но тут совсем не такой случай, согласитесь. И если 

  for j:=Low(m[i]) to High(m[i])-1 do Test(i,j,i,j+1);

я читаю на автомате (пробелами разделены смысловые сущности), то в варианте 
  for j := Low(m[i]) to High(m[i]) - 1 do Test(i, j, i, j + 1);

беглый просмотр спотыкается на каждом лишнем пробеле, в особенности на "- 1" и «+ 1». Возможно, дело привычки, спорить не буду. Я сам долго писал в варианте 2, но он мне уже давно не нравится. Тем не менее, чистой воды вкусовщина, переформатировать можно влет под требования того или иного проекта.

bormant ★★★★★
()
Ответ на: комментарий от UVV

Вот вам та же функция в Borland-стайл:

procedure BubbleSort(var m: TMatrix);
var
  si, sj: Integer;

  procedure Test(i1, j1, i2, j2: Integer); inline;
  var
    t: Integer;
  begin
    if m[i1, j1] > m[i2, j2] then
    begin
      t := m[i1, j1];
      m[i1, j1] := m[i2, j2];
      m[i2, j2] := t;
      si:=i;
      sj:=j;
    end;
  end;

var
  i, j, ti, tj: Integer;
begin
  si := High(m);
  sj := High(m[High(m)]);
  repeat
    ti := si;
    tj := sj;
    si := Low(m);
    sj := Low(m[Low(m)]);
    for i := Low(m) to ti - 1 do
    begin
      for j := Low(m[i]) to High(m[i]) - 1 do
        Test(i, j, i, j + 1);
      Test(i, High(m[i]), i + 1, Low(m[i + 1]));
    end;
    for j := Low(m[ti]) to tj - 1 do
      Test(ti, j, ti, j + 1);
  until (si = Low(m)) and (sj = Low(m[Low(m)]));
end;

ни за что не поверю, что это легче читать, чем ее изначальный компактный вариант:
Сортировка пузырьком и делфи (комментарий)

bormant ★★★★★
()
Ответ на: комментарий от bormant

чтобы функция по-прежнему помещалась на экране

логично, чо, ещё можно екран пошире взять чтобы две функции помещалось

anonymous
()
Ответ на: комментарий от Deleted

Вопрос не винспецифичный (см. FPC, {$mode Delphi}).

bormant ★★★★★
()
Ответ на: комментарий от EXL

Она не приходит только к ушедшим молодыми, увы.

bormant ★★★★★
()
Ответ на: комментарий от bormant

Это легче читать чем компактный вариант.

Jini ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development