Сортировка односвязного динамического списка по неубыванию методом простого выбора.
Сортировка производится изменением связей между элементами списка, а не перезаписью ключевых полей (это не интересно) .
<*+ MAIN *>
MODULE N75488945;
IMPORT io := InOut, STextIO, Random, TimeConv;
TYPE
Item = POINTER TO RECORD
Value: INTEGER;
Next: Item
END;
VAR
List: Item;
C: CHAR;
PROCEDURE CreateList(n: INTEGER): Item;
VAR
B, P, Q: Item;
i: INTEGER;
BEGIN
FOR i := 1 TO n DO
NEW(P);
P.Value := SHORT(ENTIER(Random.Uniform() * 199) - 99);
IF B = NIL THEN
B := P
END;
IF Q # NIL THEN
Q.Next := P
END;
Q := P
END;
RETURN B
END CreateList;
PROCEDURE WriteList(P: Item);
BEGIN
io.WriteLn;
WHILE P # NIL DO
io.WriteInt(P.Value, 4);
P := P.Next
END;
io.WriteLn
END WriteList;
PROCEDURE PrevItem(Q, P: Item): Item;
BEGIN
IF Q = P THEN
RETURN NIL
ELSE
WHILE P # Q.Next DO
Q := Q.Next
END;
RETURN Q
END
END PrevItem;
PROCEDURE MinItem(P: Item): Item;
VAR Min: Item;
BEGIN
Min := P;
P := P.Next;
WHILE P # NIL DO
IF P.Value < Min.Value THEN
Min := P
END;
P := P.Next
END;
RETURN Min
END MinItem;
PROCEDURE SwapItems(VAR B, P: Item; Q: Item);
VAR R, S: Item;
BEGIN
IF P = Q THEN
RETURN
END;
R := PrevItem(B, P);
S := PrevItem(B, Q);
IF R # NIL THEN
R.Next := Q
ELSE
B := Q
END;
IF P.Next = Q THEN
P.Next := Q.Next;
Q.Next := P
ELSE
R := P.Next;
P.Next := Q.Next;
Q.Next := R;
S.Next := P
END;
P := Q
END SwapItems;
PROCEDURE SortList(VAR B: Item);
VAR P, M: Item;
BEGIN
P := B;
WHILE P.Next # NIL DO
M := MinItem(P);
SwapItems(B, P, M);
P := P.Next
END
END SortList;
BEGIN
Random.InitSeed(TimeConv.millisecs());
io.WriteString("Исходный список: ");
List := CreateList(SHORT(ENTIER(Random.Uniform() * 91) +10));
WriteList(List);
SortList(List);
io.WriteString("Отсортированный список: ");
WriteList(List);
STextIO.ReadChar(C)
END N75488945.
Функции:
CreateList(N) - создание списка из N элементов, возвращает указатель на голову;
PrevItem(L,P) - возвращает указатель на элемент списка L, который указывает на P;
MinItem(P) - возвращает указатель на элемент с минимальным ключом (поиск, начинается с элемента P).
Процедуры:
WriteList - вывод списка на экран;
SwapItems(L,P,Q) - в списке с головой L меняет местами элементы P и Q;
SortList(L) - сортирует список L.
Примечание.
В данном языке все создаваемые указатели по-умолчанию инициализируются значением NIL, а также есть автоматический сборщик мусора.
Если вы будете переписывать программу на другой язык, где всего этого нет, то нужно в создаваемые указатели явно записывать значения nil, NULL, NONE (в зависимости от языка) . И после работы со списком, его нужно будет удалить вручную.
![](//otvet.imgsmail.ru/download/0a640c777e06edb0c56678375ae1adca_i-57.jpg)
Заранее спасибо!