Теоретическая часть метода состоит в том, что массив чисел сортируется с начала,и каждое последующее число вставляется в уже отсортированную часть массива на предназначенное ему место.
Основная соль метода выражена в процедуре :
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
procedure injection(min, max: Integer);
var
i, j, tmp: Integer;
begin
for i := min + 1 to max do
begin
j := i;
tmp := Tab[i];
while ((j > 0) and (Tab[j – 1] > tmp)) do
begin
Tab[j] := Tab[j – 1];
j := j – 1;
end;
Tab[j] := tmp;
end;
end;
[/cc]
Для наглядности наших действий, рабочий массив Tab мы будем отображать в компоненте TStringGrid (назовем его просто Grid).Массив Tab мы объявим в главной форме программы, а процедуру сортировки запустим в отдельном потоке.До начала сортировки зададим длину массива и заполним его случайными значениями. Эти операции так же выполним в отдельном потоке.
Вот процедура обработки соответствующей кнопки на форме :
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
procedure TForm1.Button1Click(Sender: TObject); // процедура привязянная к кнопке “Заполнить”
begin
Button1.Enabled := False; // выключили кнопку
Button2.Enabled := False; // выключили кнопку
Grid.ColCount := StrToInt(Edit1.Text); // поставили количество столюбцов из компонента эдит1
Grid.Cells[Grid.ColCount – 1, 0] := ”;
ToTab := False; // поставили значение ложь
Numerator := TNumerator.Create(False); // создали дочерний поток TNumerator
while (not ToTab) do // запустили цикл для обновления значения Caption
begin
Caption := IntToStr(Unit2.Kol); // проставили значение переменной Kol из модуля Unit2
sleep(100); // приложение заснуло на 100 милисекунд
end;
Caption := ‘Массив готов. Нажмите кнопку “Сортировать”.’; // обновили Caption
Button1.Enabled := True; // включили кнопку
Button2.Enabled := True; // включили кнопку
end;
[/cc]
А здесь код потока заполнения Массива :
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
unit Unit2;
interface
uses
Classes, SysUtils;
type
TNumerator = class(TThread)
private
{ Private declarations }
protected
procedure Execute; override;
end;
var
Kol: Integer;
implementation
uses Unit1;
{ TNumerator }
procedure GridToTab; // процедура переноса значений Грида в Массив
var
i: Integer;
begin
with Form1.Grid do
for i := 0 to Form1.Grid.ColCount – 1 do // запустили цикл
begin
Kol := i;
Cells[i, 0] := IntToStr(i + 1) + ‘.’;
Cells[i, 1] := IntToStr(Random(1000000));
end;
ToTab := True;
end;
procedure TabToGrid; // процедура переноса значений Массива в Грид
var
i: Integer;
begin
for i := 0 to High(Tab) do // запустили цикл
Form1.Grid.Cells[i, 1] := IntToStr(Tab[i]);
ToGrid := True;
end;
procedure TNumerator.Execute; // эта процедура выполняется после создания и запуска потока
begin
if (not ToTab) then
GridToTab; // если ToTab= false тогда запустили процедуру GridToTab
if (not ToGrid) then
TabToGrid; // если ToGrid= false тогда запустили процедуру TabToGrid
end;
end.
[/cc]
Теперь осталось описать процедуру запуска сортировки :
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
procedure TForm1.Button2Click(Sender: TObject);// процедура привязанная к кнопке “Сортировать”
var
Taim: Int64;
i, N, T: Integer;
begin
Sorting := True; // поставили значение ложь
Button1.Enabled := False; // выключили кнопку
Button2.Enabled := False; // выключили кнопку
Taim := GetTickCount; // считываем вpемя, пpошедшее с момента запуска системы.
SetLength(Tab, Form1.Grid.ColCount); // задали длинну массиву Tab равную количеству столюбцов грида
for i := 0 to High(Tab) do // запустили цикл для работы с массивом
Tab[i] := StrToInt(Form1.Grid.Cells[i, 1]); // заполнили элемент
Sorted := False; // поставили значение ложь
qSort := TqSort.Create(False); // создали дочерний поток
T := 0;
while (not Sorted) do // запустили цикл
begin
Caption := ‘Сортировка, ‘ + FloatToStr(Round(T / 1000)) + ‘ сек.’; // обновили Caption
T := T + 100;
sleep(100); // приложение заснуло на 100 милисекунд
Application.ProcessMessages; // обработали очередь задач для приложения
end;
ToGrid := False; // поставили значение ложь
N := 0;
Numerator := TNumerator.Create(False); // создали дочерний поток
while (not ToGrid) do // запустили цикл
begin
sleep(10); // приложение заснуло на 10 милисекунд
Caption := IntToStr(N) + ‘ мсек.’; // обновили Caption
N := N + 1;
end;
Caption := ‘Массив отсортирован за ‘ + IntToStr(GetTickCount – Taim) + ‘ мсек.’; // обновили Caption
Button1.Enabled := True; // включили кнопку
Button2.Enabled := True; // включили кнопку
end;
[/cc]
Для того, чтобы иметь возможность вставлять случайные числа, нужно выполнить процедуру Randomize. Мы её будем выполнять в момент создания формы.
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
procedure TForm1.FormCreate(Sender: TObject);
begin
Randomize; // при создании формы мы инициализировали генератор случайных чисел
end;
[/cc]
Вот здесь код потока сортировки Массива :
[cc lang=”delphi” tab_size=”2″ line_numbers=”false” no_links=”false”]
unit Unit3;
interface
uses
Classes, SysUtils;
type
TqSort = class(TThread)
private
{ Private declarations }
protected
procedure Execute; override;
end;
implementation
uses Unit1;
{ TqSort }
procedure injection(min, max: Integer);
var
i, j, tmp: Integer;
begin
for i := min + 1 to max do
begin
j := i;
tmp := Tab[i];
while ((j > 0) and (Tab[j – 1] > tmp)) do
begin
Tab[j] := Tab[j – 1];
j := j – 1;
end;
Tab[j] := tmp;
end;
end;
procedure TqSort.Execute; // эта процедура выполняется после создания и запуска потока
begin
injection(0, High(Tab)); // запуск процедуры injection с параметрами ноль и максимальный индекс массива
Unit1.Sorted := True; // поставили значение ложь
end;
end.
[/cc]
В результате получим вот такую форму программы
Запуск
Заполнение
Сортировка
Вот вроде и все в этом задании, в итоге имеем одну форму, один главный поток и два дополнительных.