Не работает процедура сортировки. Помогите!

[Alenka_kiss]

Не работает процедура сортировки, а в чем ошибка не понятно.
Условие задачи:
Используя представление последовательности чисел в виде
линейного списка, напишите программу сортировки этой
последовательности при помощи алгоритма простого обмена.
Помогите пожалуйста разобраться!!!

Решение:

program Project1;

uses
SysUtils;

Type
List= ^Node;
Node = record
info: Integer;
next: List
end;

Var
p, s: List;
i, x, n: Integer;

Procedure Out_spisok(l: List);
Var
s: List;
begin
While l <> nil do
begin
s:= l^.next;
Write(l^.info,' ');
l:= s;
end;
WriteLn;
end;

Procedure Sorting(l: List);
Var
p, LL: List;
k: Integer;
isExchanged: Boolean;
begin
LL:= l;
Repeat
l:= LL;
p:= l^.next;
isExchanged:= False;
while p <> nil do
begin
if p^.info > l^.info then
begin
isExchanged:= True;
k:= p^.info;
p^.info:= l^.info;
l^.info:= k;
l:= l^.next;
p:= p^.next;
end;
end;
Until not isExchanged;
end;

begin
Write('Vvedite kol-vo elementov spiska: ');
ReadLn(n);
s:= nil;
For i:= 1 to n do
begin
New(p);
p^.next:= s;
Write('Vvedite chislo: ');
ReadLn(x);
p^.info:= x;
s:= p;
end;
Write('Vvedennaya posledovatelnost: ');
Out_spisok(p);
Sorting(p);
Write('Otsortirovannaya posledovatelnost: ');
Out_spisok(p);
ReadLn;
end.

[Sanyok]

Вы сами еще не разобрались? Я попробую компилятор Borland Pascal вечерком поставить, и прогоню эту прогу. А Вы сами ее по шагам не пробовали проходить?

[Alenka_kiss]

Нет не разобралась. Чего-то не получается. А надо побыстрее. А я в паскале не сильна

[Sanyok]

Вы в Delphi этот проект писали или в Borland Pascal 7.0 ?

[Alenka_kiss]

Это Паскаль. Я делфи еще не знаю, и потом, требуют токо на Паскале, потому что мы его сейчас проходим.

[Sanyok]

Ошибка в этой процедуре (в след . раз когда пишите прогу - отступы побольше делайте, хотя бы по 3 пробела), во внутреннем цикле wile.

Procedure Sorting(l: List);
Var
p, LL: List;
k: Integer;
isExchanged: Boolean;
begin
    LL:= l;
    Repeat
        l:= LL;
        p:= l^.next;
        isExchanged:= False;
        while p <> nil do
        begin
            if p^.info > l^.info then
            begin
               isExchanged:= True;
               k:= p^.info;
               p^.info:= l^.info;
               l^.info:= k;
               l:= l^.next;
               p:= p^.next;
            end;
        end;
    Until not isExchanged;
end;

Представьте, что будет, если условие внутри цикла wile не выполняется? Значение указателей p и l не изменятся, и второй, и третий, и тысячный раз Вы будете сравнивать одни и те же значения! Даже если условие не выполнилось - надо все-таки по списку вниз как-то двигаться, а то мы до nil не доберемси!

[Alenka_kiss]

Спасибо большое за науку! Только не в коня корм. Эту задачу мне не решить самостоятельно. (Это не я ее решила). И как ее исправить с учетом вышеизложенного я просто не понимаю, к сожалению.

[Sanyok]

Ну хотя бы Вы можете словесно изложить алгоритм простой сортировки? На обычном, русском языке, не на Паскале?

[Alenka_kiss]

Словесно я могу это выразить. За минимально число сравнений надо решить задачу по сортировке чего-то, то есть - выбрать элемент и поставить его на свое место. Есть сортировка включение, слиянием и обменом и другие нужные виды сортировки.
Нужно найти наибольший элемент файла и поставить его на место, найти следующий наибольший и поставить его рядом (на предыдущее место) и так далее.
Вот например сортировка выбором:

Сортировка посредством выбора.

{сортировка выбором, пример 1}
procedure Selekt(var item: DataArray; count:integer);
var
i, j, k: integer;
x: DataItem;
begin
for i := i to count-1 do
begin
k := i;
x := item[i];
for j := i+1 to count do { найти элемент с наименьшим значением }
if item[j]<x then
begin
k := j;
x := item[j];
end;
item[k] := item[i]; { обмен }
item[i] := x;
end;
end;
Может что не так сказала?

[Sanyok]

Извиняюсь.. Я имел в виду - словесно изложить алгоритм простого обмена, который Вам надо реализовать. А код писать не надо пока

[Alenka_kiss]

Почему-то в учебнике, который мне дали, внимание на этом не заостряется. Если яндекс не обманывает, то при сортировке обменом все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и в конце концов занимает крайнее правое место в массиве, после чего он исключается из дальнейшей обработки. Затем процесс повторяется, и своё место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается до тех пор, пока вся последовательность не будет упорядочена. Если на очередном проходе массива не будет сделано ни одного обмена, то массив уже упорядочен. Правильно сказала?

[Sanyok]

Ага, спасибо что ответили. А то я уж в личку Вам написал. Я в алгоритмах сам не разбираюсь

[Alenka_kiss]

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

[Alenka_kiss]

Поступило предложение
после Until not isExchanged; надо добавить l:= LL;

Код:
Until not isExchanged;
l:= LL;
а "кучу" можно освободить так (примерно так):

Код:
while p <> nil do
begin
s := p^.next;
Dispose (p);
p := s;
end;
это надо добавить после второго Out_spisok(p);

А вы что об этом думаете?

[Sanyok]

Думаю, что эти предложения не позволят сортировать список. А кучу, конечно, надо освобождать, но это может подождать (к тому же это не бросается в глаза )

Цитата:

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

Ладно, не надо ложной скромности!

Цитата:

Автор программы очень умный, ...

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

Давай потихоньку разберемся. Я Паскаль забросил лет 7 назад, а потому
знаю немногим больше твоего (если не меньше). Насколько я понял, с
массивами ты понимаешь как обрашатся, но тебя смущают списки (и, возможно
еще эти несчастные record и указатели ). record - это то же, что stuct
в Си. Это вроде коробки. Если Вам необходимо хранить несколько разнотипных
величин в одном месте (к примеру, координаты точки на плоскости и ее
цвет), удобно все это сложить в один ящик и обращаться с ним, как с единым
целым:

Type 
point = record 
x: double; 
y: double; 
color: integer; 
end; 

Естественно, как и все переменные, такая коробка сидит в памяти и имеет
адрес (точнее, адрес ее начала). Переменная-указатель на этот тип может
хранить значения начальные адресов энтих коробок.
У вас Node - это такая коробка, а List - это переменная-указатель,
которая может хранить адреса таких коробок.

У вас запись (или коробка ) объявлена след. образом:

Type 
  List= ^Node; 
  Node = record 
    info: Integer; 
    next: List 
  end;

В Вашем случае каждая "коробка" содержит указатель на такую же "коробку"
(это переменная next). Список - это цепочка таких вот "коробок", каждая
последующая связана с предыдущей указателем next. Пусть у нас список -
переменная L (это указатель на нашу "коробку", а что бы получить доступ к
самой коробке - к указателю надо применить т.н. оператор разыменования,
если я правильно понял, то вот таким образом: L^ ). Доступ к первому эл-ту:
L^
Ко второму:
L^.next^
к третьему:
L^.next^.next^
и т.д. В последней "коробке" next должен быть равен nil (если указатель
имеет значение nil, то он никуда не указывает) - это служит окончанием
списка.

Нельзя пролучить доступ непосредственно к i-тому элементу списка. Что бы
получить к нему доступ, надо сначала получить доступ к предыдущим i-1
элементам:

p = LL;
for k := 1 to i do
   p = p^.next;

что бы получить доступ полю info нашей "коробки" по имени p (которая имеет тип List) надо написать:

p^.info

Если Вы заметили - такую штуку, как список лучше сортировать таким алгоритмом, в котором требуется доступ только к двум соседним элементам (каковым и является описанный Вами способ сортировки обменом)
Извиняюсь за длинное вступление. Я просто хотел, что бы было понятны термины, которые использовались в формулировке Вашей задачи. Теперь посмотрите на этот код, выдранный из процедуры сортировки и почитайте мои комментарии:

    
    l:= LL;{Присваеваем переменной l указатель на 1-ый эл-т списка}
    p:= l^.next;{Присваеваем переменной p указатель на 2-ой эл-т списка}
    isExchanged:= False;{Если подумать, это нафиг не нужно}
    while p <> nil do {если p=nil-это конец списка, и надо выходить из цикла.}
    begin
      if p^.info > l^.info then {Если первый эл-т больше второго}
      begin                     {То:                            }
        isExchanged:= True;     {Это тоже нафиг не нужно}
        k:= p^.info;       {В этих трех строчках   }
        p^.info:= l^.info; {                       }
        l^.info:= k;       {меняем эл-ты местами   }
        l:= l^.next; {Перемещаемся к               }
        p:= p^.next; {следующему элементу списка   }
      end;
{!!!! А ЕСЛИ УСЛОВИЕ if p^.info > l^.info НЕ ВЫПОЛНЯЕТСЯ, }
{ТО НЕ ДЕЛАЕМ НИЧЕГО И ОПЯТЬ СРАВНИВАЕМ ТЕ ЖЕ ЗНАЧЕНИЯ!!!!!}
    end;

Увидели самую главную ошибку? Слово end надо в одном месте просто поднять вверх На сколько строк?