Продолжаю повторять алгоритмы. Данная статья посвящена алгоритму сортировки вставками.
Схематично её можно изобразить следующим образом.
А вот классный рисунок gif на эту тему… – вместо псевдокода.
Реализуем алгоритм сортировки вставками
Реализация через while
На многих ресурсах наблюдал реализацию через while цикл. А почему нет? Получается элегантный и простой код. В порядке тренировки сделаем в этой статье 2 реализации – через while и через for.
Создадим форму следующим образом. Нам для этого алгоритма понадобятся Memo, кнопки FillArray и InsertionSort.
В районе type напишем
|
1 2 3 4 5 6 |
... Const ArraySize=1000; type TMyArray = array [1..ArraySize] of integer; ... |
Объявим глобальную переменную
|
1 2 |
var MyArray:TMyArray; |
Заполним массив
|
1 2 3 4 5 6 7 8 9 10 11 12 |
procedure TForm2.FillArrayClick(Sender: TObject); var i:integer; begin memo1.lines.clear; //Заполняем данные for i := 1 to ArraySize do begin MyArray[i]:=Random(ArraySize); memo1.lines.add(inttostr (MyArray[i]) ); end; end; |
Сам алгоритм
|
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 |
procedure injectionSort(var MyArray:TMyArray;min,max:integer); var i,j,TemporaryValue:integer; begin //Внешний цикл for i := min+1 to max do begin TemporaryValue:=MyArray[i]; //Cохраняем во временное значение //Внутренний цикл от i, уменьшаясь до min+1 j:=i; while ((j>min) and (MyArray[j-1]>TemporaryValue)) do begin MyArray[j]:=MyArray[j-1]; dec(j); end; // Внутренний цикл //Счетчик j уменьшался пока выполнялись условия // ((j>min) and (MyArray[j-1]>CurrentValue)) // Cчетчик j встал не некоторое минимальное значение по условиям выше MyArray[j]:=TemporaryValue; // Замена последнего элемента end;//Внешний цикл end; |
Код кнопки
|
1 2 3 4 5 6 7 8 9 10 |
procedure TForm2.Button4Click(Sender: TObject); var i:integer; begin // injectionSort(MyArray,1,ArraySize); memo1.Lines.Clear; for i := 1 to ArraySize do memo1.Lines.Add(inttostr(MyArray[i])); end; |
Результат
Реализация через for
Эта реализация больше для тренировки написания алгоритмов и развития алгоритмического мышления. Скажу честно – классические алгоритмы в чистом виде давно не писал, поэтому разработка этого простого алгоритма заняла у меня аж целых 20 минут, ну и конечно листочек с карандашом в помощь. Самое главное в алгоритме – понять как он работает, порисовать, разложить на простом случае. Далее становится легче.
Итак, всё остальное тоже самое как и в примере выше, изменился только сам алгоритм – переписан через for.
|
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 |
procedure injectionSort4(var MyArray:TMyArray;min,max:integer); var i,j,k,TemporaryValue:integer; begin for i := min+1 to max do begin k:=-1; // Вспомогательный индекс TemporaryValue:=MyArray[i]; //Cохраняем во временное значение //Поиск мин. индекса при котором MyArray[j]>TemporaryValue for j := i downto min do begin if MyArray[j]>TemporaryValue then k:=j; end; //Перестановка if k<>-1 then begin for j:= i downto k+1 do MyArray[j]:=MyArray[j-1]; MyArray[k]:=TemporaryValue; end; end; end; |