Массив целых чисел тремя методами

     2.1 Метод «Пузырька»  или метод Обмена 

     В основе алгоритма лежит обмен  соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом элементы, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут). Поэтому данный метод сортировки обменом иногда называют методом «Пузырька». Это процесс повторяется столько раз, сколько элементов в массиве минус единица [4]. На рисунках 2 и 3 представлен данный алгоритм на конкретном примере, массив 4, 9, 7, 6, 2, 3.

     

     Рисунок 2 -  Нулевой проход, сравниваемые пары выделены. 

     

     Рисунок 3 -  Все проходы алгоритма. 

     На  практике данный метод почти не используется, так как очень медленно работает.

      Блок-схема данного алгоритма приведена на рисунке 4: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Рисунок 4 -  Блок-схема метода «Пузырек».

     2.2 Метод прямого  выбора 

     Алгоритм  сортировки массива по возрастанию  методом прямого выбора может  быть представлен так:

     1. Просматривая массив от первого  элемента, найти минимальный элемент и поместить его на место первого элемента, а первый – на место минимального.

     2. Просматривая массив от второго  элемента, найти минимальный элемент  и поместить его на место  второго элемента, а второй –  на место минимального.

     3. И так далее до предпоследнего[4].

     Например, если сортировать массив 2  8  6  9  4, то схема проходов будет выглядеть  так:

2   8  6  9  4

2   4  6  9  8

2   4  6  9  8

2   4  6  8  9 

     Блок-схема данного алгоритма представлена на рисунке 5:

     

 
 

       
 
 
 
 
 
 
 
 

     Рисунок 5 -  Блок-схема метода «Прямой выбор». 

     2.3 Метод Шелла 

      Сортировка  Шелла - это еще одна модификация пyзыpьковой соpтиpовки. Суть ее состоит в том, что здесь выполняется сpавнение ключей, отстоящих один от дpyгого на некотоpом pасстоянии d. Исходный pазмеp d обычно выбиpается соизмеpимым с половиной общего pазмеpа соpтиpyемой последовательности. Выполняется пyзыpьковая соpтиpовка с интеpвалом сpавнения d. Затем величина d yменьшается вдвое и вновь выполняется пyзыpьковая соpтиpовка, далее d yменьшается еще вдвое и т.д. Последняя пyзыpьковая соpтиpовка выполняется пpи d=1. Качественный поpядок соpтиpовки Шелла остается O(N^2), сpеднее же число сpавнений, опpеделенное эмпиpическим пyтем - log2(N)^2*N. Ускоpение достигается за счет того, что выявленные "не на месте" элементы пpи d>1, быстpее "всплывают" на свои места.

      Процесс сортировки массива представлен  на рисунке 6:

      

     Рисунок 6 -  Проходы метода Шелла.

     Блок-схему данного алгоритма приведена на рисунке 7:

     

     

     

     

     Рисунок 7 -  Блок-схема метода Шелла.

 

      3 Проектирование и разработка проекта

     3.1 Проектирование программы 

     Для разработки  данного проекта используется среда визуального программирования Delphi. Проект содержит одно окно Form1 предоставляющее возможность ввода количества и элементов исходного массива, выбора метода и способа сортировки и вывода результатов программы. Данное окно содержит следующие объекты:

     

     Рисунок 2 -   Окно программы – Form1 

     1 - Компонент Form1.

     Свойства:

     Caption – Сортировка линейного массива.

     2 – компонент Label1.

     Свойства:

     Caption – Введите количество элементов в массиве;

     Font: Color – clRed; Size: 14.

     3 -  компонент Label2

     Свойства:

     Caption – ‘ ‘;

     Font: Color - ClGray; Size:8.

     4 – компонент Button1

     Свойства:

     Caption – Сортировать

     Font: Color - ClBlack; Size:12.

     События:

       Button1Click – выполняет выбранный пользователем метод сортировки массива.

     5 - Компонент GroupBox1

     Свойства:

     Caption – Выберите метод и способ сортировки

     Font: Color - ClPurple; Size:12.

     6 – компоненты RadioButton1, RadioButton2, RadioButton3

     Свойства:

     Caption – Метод сортировки

     Font: Color -clBlue ; Size:8.

     7 – компоненты RadioButton4, RadioButton5, RadioButton6, RadioButton7, RadioButton8, RadioButton9

     Свойства:

     Caption – Способ сортировки

     Font: Color -clBlack ; Size:8.

     8 – компоненты Panel1, Panel2, Panel3

     Свойства:

     Caption – ‘ ‘

     9 – компонент Edit1

     Свойства:

     Text – 1;

     10 – компонент UpDown1

     Свойства:

     Min – 1;

     Max – 20;

     Associate – Edit1

     11 – компонент StringGrid1

     Свойства:

ColCount – 1; 
FixedCols – 0; 
RowCount – 1; 
Height – 25; 
DefaultColWidth – 40; 
Width – 49; 
Options.goEditing – True; 
Options.AlwaysShowEditing – True; 
Options.goTabs – True. 

     3.2 Текст программы 

     unit Unit1; 

     interface 

     uses

       Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

       Dialogs, StdCtrls, Grids, ComCtrls, ExtCtrls; 

     type

       TForm1 = class(TForm)

         StringGrid1: TStringGrid;

         Label1: TLabel;

         Edit1: TEdit;

         UpDown1: TUpDown;

         Button1: TButton;

         GroupBox1: TGroupBox;

         RadioButton1: TRadioButton;

         RadioButton2: TRadioButton;

         RadioButton3: TRadioButton;

         Label2: TLabel;

         Panel1: TPanel;

         RadioButton4: TRadioButton;

         RadioButton5: TRadioButton;

         Panel2: TPanel;

         RadioButton6: TRadioButton;

         RadioButton7: TRadioButton;

         Panel3: TPanel;

         RadioButton8: TRadioButton;

         RadioButton9: TRadioButton;

         procedure UpDown1Click(Sender: TObject; Button: TUDBtnType);

         procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

         procedure Button1Click(Sender: TObject);

          

       private

         { Private declarations }

       public

         { Public declarations }

       end; 

     var

       Form1: TForm1;

       size:integer; //размерность массива

     implementation 

     {$R *.dfm} 

     procedure TForm1.UpDown1Click(Sender: TObject; Button: TUDBtnType);

     begin

       StringGrid1.ColCount:=StrToInt(Edit1.Text);

       StringGrid1.RowCount:=0;

       StringGrid1.Width:=42*StrToInt(Edit1.Text);

       StringGrid1.Height:=40;

       size:= StrToInt(Edit1.text);

     end; 

     procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

     begin

       case Key of

         #8,'0'..'9','-' : ; // цифры и клавиша <Backspace>, клавиша минус

         #13: // клавиша <Enter>

           if StringGrid1.ColCount < StringGrid1.ColCount-1

             then StringGrid1.ColCount := StringGrid1.ColCount + 1;

               else key := Chr(0); // остальные символы запрещены

       end;

     end; 

     procedure TForm1.Button1Click(Sender: TObject);

     var

     a:array[1..20] of integer;

     k:integer; //текущий элемент массива

     i:integer;// индекс для ввода и вывода  массива

     buf:integer; // буфер для обмена элементами массива

     ch:boolean; // true, если в текущем цикле были  обмены

     j:integer; // номер эл-та, сравниваемого с  минимальным

     min:integer; //номер мин-го эл-та в части  массива от i до верхн границы  массива

     d:integer;

     begin

       //ввод массива

       for i:=1 to size do

         if StringGrid1.Cells[i-1,0]=''

           then ShowMessage('Заполните все ячейки массива')

             else a[i]:= StrToInt(StringGrid1.Cells[i-1,0]);

             Label2.Caption:=''; 

       // сортировка методом "пузырька"

       //по возрастанию

       if (RadioButton1.Checked=true) and (RadioButton4.Checked=true)then

         repeat

           ch:=false; // пусть в текущем циклк  нет обменов

           for k:=1 to size-1 do

             if a[k] > a[k+1]

               then