Пузырьковая сортировка по возрастанию и убыванию для двунаправленного списка.
| Delphi |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
| type
//Типы для описания списка.
//Тип данных - определяет данные, которые будет содержать каждый элемент списка.
TData = Integer;
//Тип, описывающий элемент списка.
TPElem = ^TElem;
TElem = record
Data : TData;
PNext : TPElem;
PPrev : TPElem;
end;
//Тип, описывающий список.
TList = record
PFirst : TPElem;
PLast : TPElem;
end;
//Процедуры для работы со списком.
//Удаление всего списка из памяти и инициализация.
procedure ListFree(var aList : TList);
var
PNext, PDel : TPElem;
begin
if aList.PFirst = nil then Exit;
PNext := aList.PFirst;
while PNext <> nil do begin
PDel := PNext;
PNext := PNext^.PNext;
Dispose(PDel);
end;
aList.PFirst := nil;
aList.PLast := nil;
end;
//Добавление элемента в конец списка.
procedure AddL(var aList : TList; const aPElem : TPElem);
begin
if aPElem = nil then Exit;
aPElem^.PNext := nil;
aPElem^.PPrev := nil;
if aList.PFirst = nil then
aList.PFirst := aPElem
else begin
aList.PLast^.PNext := aPElem;
aPElem^.PPrev := aList.PLast;
end;
aList.PLast := aPElem;
end;
//Распечатка списка.
function ListText(const aList : TList) : String;
var
PElem : TPElem;
i : Integer;
begin
Result := '';
i := 0;
PElem := aList.PFirst;
while PElem <> nil do begin
Inc(i);
if i > 1 then Result := Result + ', ';
Result := Result + IntToStr(PElem^.Data);
PElem := PElem^.PNext;
end;
end;
//Пузырьковая сортировка по возрастанию.
procedure SortBubbleAsc(const aList : TList);
var
P1, P2, P : TPElem;
Data : TData;
F : Boolean;
begin
if aList.PFirst = aList.PLast then Exit;
P := aList.PLast;
repeat
F := False;
P1 := aList.PFirst;
P2 := P1^.PNext;
while P1 <> P do begin
if P1^.Data > P2^.Data then begin
Data := P1^.Data;
P1^.Data := P2^.Data;
P2^.Data := Data;
F := True;
end;
P1 := P2;
P2 := P1^.PNext;
end;
P := P^.PPrev;
until not F;
end;
//Пузырьковая сортировка по убыванию.
procedure SortBubbleDesc(const aList : TList);
var
P1, P2, P : TPElem;
Data : TData;
F : Boolean;
begin
if aList.PFirst = aList.PLast then Exit;
P := aList.PLast;
repeat
F := False;
P1 := aList.PFirst;
P2 := P1^.PNext;
while P1 <> P do begin
if P1^.Data < P2^.Data then begin
Data := P1^.Data;
P1^.Data := P2^.Data;
P2^.Data := Data;
F := True;
end;
P1 := P2;
P2 := P1^.PNext;
end;
P := P^.PPrev;
until not F;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
List : TList;
PElem : TPElem;
i : Integer;
begin
//Инициализация списка.
List.PFirst := nil;
List.PLast := nil;
//Создаём несколько элементов и помещаем их в список
//через процедуру добавления в конец списка.
Randomize;
for i := 1 to 10 do begin
New(PElem);
PElem^.Data := Random(10); //0..9.
AddL(List, PElem);
end;
//Показываем весь список в Мемо.
Memo1.Lines.Add('--------------------------------------------------');
Memo1.Lines.Add('Исходный список:');
Memo1.Lines.Add(ListText(List));
//Сортируем элементы по убыванию.
SortBubbleDesc(List);
//Показываем весь список в Мемо.
Memo1.Lines.Add('Список после сортировки по убыванию (невозрастанию):');
Memo1.Lines.Add(ListText(List));
//Сортируем элементы по возрастанию.
SortBubbleAsc(List);
Memo1.Lines.Add('Список после сортировки по возрастанию (неубыванию):');
Memo1.Lines.Add(ListText(List));
//Удаление списка из памяти.
ListFree(List);
end; |
|
В этом коде в алгоритме сортировки для перестановки элементов применяется копирование значения поля основных данных Data. На самом деле, одно из преимуществ списков заключается в том, что элементы можно "перемещать", не копируя основные данные. Это особенно важно в случае, когда основные данные весьма объёмные - это может быть, например, запись со множеством полей, некоторые из которых могут быть массивами. В этом случае следует отказаться от копирования основных данных и применять действия с указателями. Один из путей в отношении указателей - это "перешнуровка" указателей на перемещаемые элементы списка. Такой подход не очень удобен и требует в общем тоже достаточных вычислительных затрат. Т. к. для двунаправленного списка, при этом способе, для перестановки двух элементов может потребоваться переопределить 8 указателей. Поэтому лучшим решением будет не действия с указателями на элементы, а использование указателей на основные данные. Это означает вот что. Вместо такого определения элементов списка:
| Delphi |
1
2
3
4
5
6
7
8
9
| //Тип данных - определяет данные, которые будет содержать каждый элемент списка.
TData = Integer;
//Тип, описывающий элемент списка.
TPElem = ^TElem;
TElem = record
Data : TData;
PNext : TPElem;
PPrev : TPElem;
end; |
|
следует применить такой способ:
| Delphi |
1
2
3
4
5
6
7
8
9
10
11
| //Тип данных - определяет данные, которые будет содержать каждый элемент списка.
TData = Integer;
//Указатель на основные данные.
TPData = ^TData;
//Тип, описывающий элемент списка.
TPElem = ^TElem;
TElem = record
PData : TPData;
PNext : TPElem;
PPrev : TPElem;
end; |
|
Т. е., здесь элемент списка содержит указатель на основные данные. И при перестановках элементов списка, собственно, сами эти элементы не переставляются, а переставляются указатели на основные данные элементов. Это самый оптимальный способ.
Если потребуется, код можно переписать под этот механизм.
(
Сообщение было отмечено как решение
