Сортировка массива методом вставок

Теоретическая часть метода состоит в том, что массив чисел сортируется с начала,и каждое последующее число вставляется в уже отсортированную часть массива на предназначенное ему место.

Основная соль метода выражена в процедуре :

[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]
В результате получим вот такую форму программы

Запуск

Заполнение

Сортировка

Вот вроде и все в этом задании, в итоге имеем одну форму, один главный поток и два дополнительных.

 

 

Нашли ошибку в тексте?

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *