Содержание

 

      Введение

     Тема  данной курсовой работы заключается  в разработке проекта, позволяющего сортировать заданный линейный массив целых чисел тремя методами.

     Для раскрытия темы необходимо рассмотреть  следующие понятия:

     Массив - это структура данных, которая может заключать в себе несколько отдельных значений данных, подобно тому, как здание - это физическая структура, которая может содержать несколько этажей.

     Или вот такое определение:

     Массив - это однородная структура   однотипных  данных, одновременно хранящихся в последовательных ячейках оперативной памяти. Эта структура должна иметь имя и определять заданное количество данных (элементов).

     Если  дать более простое определение, то массив является контейнером общего назначения. В нем может содержаться любое количество элементов, в том числе и элементы разных типов данных. Массив может содержать даже другие массивы. Массив можно сравнить с комодом, у которого несколько ящиков. В каждом ящике находятся некоторые предметы, но сам комод содержит только ящики. Нас же, конечно, интересует только содержимое этих ящиков, т.е. значения. Значения в массиве являются информацией, которой мы можем распоряжаться по своему усмотрению, например, сортировать в определенном порядке. 

     Сортировка - процесс перестановки значений данного массива в определенном порядке. Целью сортировки являются упорядочение массивов для облегчения последующего поиска значений в данном массиве.

     Каждое  значение, хранящееся в массиве, называется элементом. А каждый элемент имеет свой порядковый номер (индекс).

     Массивы бывают одномерные, двумерные и многомерные.

     Одномерный (линейный) массив - это   однородная структура   однотипных  данных, для получения доступа к его элементам достаточно одной индексной переменной.

     Данная  работа направлена на детальное изучение процесса сортировки линейного массива  различными методами и создание проекта, позволяющего сортировать массив целых чисел различными способами с наглядным представлением хода алгоритмов сортировки. Данный проект будет удобен в преподавании дисциплин, связанных с программированием на различных языках программирования высокого уровня с целью демонстрации методов сортировки и проведения сравнительного анализа данных способов сортировки.   
 
 
 
 
 
 
 

 

     Основная  часть

     1 Разработка эскизного и технического проектов программы

 

     Требуется разработать  проект, который позволяет сортировать заданный линейный массив целых чисел различными методами, например, методом линейной сортировки, пузырька, Шелла и др. Предусмотреть использование не менее трех методов. 

     

1.   Назначение и область  применения

 

     Необходимо  разработать проект, демонстрирующий правила работы трех алгоритмов сортировки линейных массивов. Программа может быть использована в учебных целях. 

     

2.  Технические характеристики
1. Постановка задачи

 

     По  условию задачи необходимо организовать возможность формирования линейного  массива целых чисел максимальной размерностью 20 штук. Предоставить пользователю возможность выбора метода (Шелла, «Пузырька», Прямого выбора) и способа (по возрастанию, по убыванию) сортировки данного массива. Вывести результаты процедуры сортировки. 

2.  Описание алгоритма

 

     Исходя  из постановки задачи и выбранной  среды разработки, алгоритм данной программы будет иметь следующий  вид, который приведен на рисунке 1.  
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Рисунок 1 -  Обобщенная схема алгоритма. 

     

3.  Организация входных и выходных данных

 

     Входными  данными данного проекта являются следующие значения:

• количество элементов в массиве;
• элементы исходного массива.

Сформировав массив, пользователь выбирает метод  и способ сортировки, нажимает кнопку сортировать, после чего появляется результат: отсортированный массив и все циклы обмена выбранного метода сортировки - выходные данные. 

4. Выбор среды разработки программных средств

 

     Так как в условии задачи сказано  разработать проект, то наиболее удобно использование среды разработки программных приложений Delphi.

     Среда Delphi – это могучая среда разработки программ, являющаяся одновременно и редактором и компилятором. Данная среда ориентирована, прежде всего, в операционных системах Windows.

     В основе любой программы на Delphi лежит язык Object Pascal – язык программирования высокого уровня, позволяющий использовать такие объектно-ориентированные языковые средства, как динамические массивы, перегрузка методов, параметры, заданные по умолчанию, файловые потоки и многое другое. 

     Delphi - одна из самых мощных систем, позволяющих на самом современном уровне создавать как отдельные прикладные программы  Windows, так и разветвленные комплексы предназначенные для работы в корпоративных сетях и в Интернет.

     Основой Delphi является графическая среда разработки приложений, называемая интегрированной средой разработки (Integrated Development Environment, IDE).  Delphi, как и всякая современная среда разработки приложений основана на объектно-ориентированном программировании.

     Среда предоставляет вам формы, на которых размещаются компоненты. Обычно это оконная форма, хотя могут быть и невидимые формы. На форму с помощью мыши переносятся и размещаются пиктограммы компонентов, имеющихся в библиотеках Delphi. С помощью простых манипуляций вы можете  изменить размеры и расположение этих компонентов. При этом вы все время в процессе проектирования видите результат - изображение формы и расположенных на ней компонентов. Результаты проектирования видны не компилируя программу, немедленно после выполнения какой-то операции с помощью мыши.

     Основным  достоинством визуального программирования является то, что во время проектирования формы и размещения на ней компонентов  Delphi автоматически формирует коды программы, включая в нее соответствующие фрагменты, описывающие данный компонент. А затем в соответствующих диалоговых окнах пользователь может изменить заданные по умолчанию значения каких-то свойств этих компонентов и, при необходимости, написать обработчики каких-то событий. То есть, проектирование сводится, фактически, к размещению компонентов на форме, заданию некоторых их свойств и написанию, при необходимости, обработчиков событий.

     Компоненты  могут быть визуальные, видимые при  работе приложения, и невизуальные, выполняющие те или иные служебные  функции. Визуальные компоненты сразу видны на экране в таком же виде, в каком их увидит пользователь во время выполнения приложения. Это позволяет очень легко выбрать место их расположения и их дизайн – форму, размер, оформление, текст, цвет и т.д. Невизуальные компоненты видны на форме в процессе проектирования в виде пиктограмм, но пользователю во время выполнения они  не видны, хотя и выполняют для него за кадром весьма полезную работу.   

     В библиотеки визуальных компонентов  Delphi включено множество типов компонентов и их номенклатура очень быстро расширяется от версии к версии.  Имеющегося, уже сейчас вполне достаточно,  чтобы построить практически любое самое замысловатое приложение, не прибегая к созданию новых компонентов. Это позволяет создавать приложения, которые выглядят совершенно профессионально.

Компоненты библиотек  Delphi и типы других объектов оформляются в виде классов. Классы – это типы, определяемые пользователем. В классах описываются свойства объекта, его методы и события, на которые он может реагировать. В Delphi множество очень полезных классов включены в библиотеки системы. Этими классами вы пользуетесь при работе в Интегрированной Среде Программирования.  Delphi базируется на языке Object Pascal. Компиляторы с языков этого семейства Паскаль фирмы Borland были одними из самых быстрых компиляторов. В настоящее время Object Pascal – это объектно-ориентированный язык с твердой опорой в виде хорошего компилятора.

По сравнению  с другими программными продуктами Delphi имеет ряд преимуществ:

Быстрота разработки приложения.

Высокая производительность разработанного приложения.

Низкие требования разработанного приложения к ресурсам компьютера.

Наращиваемость за счет встраивания новых компонент и инструментов в среду Delphi.

Возможность разработки новых компонент и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходниках).

Удачная проработка иерархии объектов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

      2 Методы сортировки массивов

 

     Под сортировкой массива подразумевается  процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке. Например, если имеется массив целых чисел а, то после выполнения сортировки по возрастанию должно выполняться условие:

     a[1] < a[2] < … <= a[Size], где

     Size – верхняя граница индекса массива.

     Существует  много методов (алгоритмов) сортировки массивов. Рассмотрим Метод «Пузырька» или метод Обмена, Метод прямого  выбора и метод Шелла. 

     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