Программирование

Оглавление

1. ОПИСАНИЕ ПЕРЕМЕННЫХ И ПРОЦЕДУР 2

2. ВВЕДЕНИЕ 3

3. ТЕОРЕТИЧЕСКАЯ  ЧАСТЬ 4

Сортировка  простыми вставками 6

Метод последовательного поиска в упорядоченной таблице 8

4. ПРАКТИЧЕСКАЯ  ЧАСТЬ 9

5. ЛИСТИНГ ПРОГРАММЫ 14

6. ИНТЕРФЕЙС ПРОГРАММЫ 17

7. ТАБЛИЦЫ РЕЗУЛЬТАТОВ 18

8. ЗАКЛЮЧЕНИЕ 21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАДАНИЕ: Упорядочить массив чисел в диапазоне от 1 до 100000 по убыванию и возрастанию методом сортировки простых вставок.

ЦЕЛЬ РАБОТЫ: разработать блок-схему алгоритма метода сортировки простыми вставками, создать схему программы, составить и протестировать программу на языке высокого уровня Delphi, получить результаты сортировки времени и скорости в зависимости от количества вводимых символов, построить графики зависимости в промежутках: [1 … 300], [300 … 5 000], [5 000 ... 10 000]

1) время от количества  символов в указанных промежутках; 

2) скорость от количества  символов в указанных промежутках. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ОПИСАНИЕ ПЕРЕМЕННЫХ И ПРОЦЕДУР

count – число элементов;

range –целое число, содержит диапазон чисел ;

a – массив целых чисел;

x,k, i, j-целые числа;

d1- переменная типа TDateTime, используется для подсчета времени;

str – строковая переменная содержит результаты поиска;

 

procedure SortToInc (a:array of Integer) – сортирует входной  массив по возрастанию;

procedure SortToDec(a:array of Integer) – сортирует входной массив по убыванию;

function FindInc(a:array of Integer):AnsiString – выполняет поиск образца в отсортированном по возрастанию массиве;

function FindDec(a:array of Integer):AnsiString – выполняет поиск образца в отсортированном по убыванию массиве;

procedure TForm1.btn1Click(Sender: TObject) – выполняет сортировку;

procedure TForm1.btn2Click(Sender: TObject) - осуществляет поиск образца.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. ВВЕДЕНИЕ

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

Современные вычислительные системы  работают наиболее эффективно при упорядоченных  данных. Сортировка информации — это  процесс расстановки элементов  в некотором порядке. Элементы размещаются следующем образом:

1) вычисления, которые требуют определенного  порядка расположения данных, упорядоченных  по возрастанию или убыванию, могли выполняться эффективно,

2)  результаты имели осмысленный  вид,

3) последующие операции имели бы упорядоченные исходные данные.

 

Сортировка во все времена имела  большое значение. Например, в Древнем  Риме или Греции немногие пользовались библиотеками. Почему? Они не сортировали  книги по алфавиту или какому-то ещё признаку. Из-за этого поиск 1 книги мог занять недели, месяцы и даже годы.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. ТЕОРЕТИЧЕСКАЯ  ЧАСТЬ

  3.1 Сортировка простыми вставками

Один из простейших способов отсортировать массив - сортировка вставками.

Этот способ предполагает, что перед рассмотрением записи r_j предыдущие записи R₁,..., R_j-1 уже упорядочены и r_j вставляется в соответствующее место. Приняв эту схему в качестве базовой, можно построить несколько любопытных ее модификаций.

Метод простых вставок. Простейший метод сортировки посредством вставок  можно считать наиболее очевидным. Пусть 1 < j < N  к записи R_j,...,R_j-1 уже размещены так,  что (через K_t  обозначается ключ записи R_j). Будем сравнивать по очереди K_j с K_j-1,  K_j-2 ... до тех пор, пока не обнаружим, что запись R_j следует вставить между R_i и R_i+1, тогда подвинем записи R_i+1 и на одну позицию вверх и поместим новую запись в позицию i + 1. Удобно совмещать операции сравнение и перемещения, перемещая их между собой, как продемонстрировало в следующем алгоритме; поскольку запись R_j как бы "погружается" на положенный ей уровень, этот способ часто называют просеиванием или погружением (рис. 1).

 

 

 

Рис. 1. Алгоритм S: сортировка методом простых вставок.

Алгоритм S (Сортировка методам  простых вставок).   Записи R₁, …, R_N переразмещаются на том же месте.  После завершения сортировки их ключи будут упорядочены: K₁<=…<= K_N.

S1. [Цикл по j.]   Выполнить шаги от S2 до S5 при i = 2,3,...Т и после этого завершить выполнение процедуры.

S3. [Установка i, К, R] Присвоить I ß j - 1, Kß  K_j, Rß R_j. (На последующих шагах будет предпринята попытка вставить запись R в нужное место, сравнивая К с K_j ( при убывающих значениях i.)

 

S3. [Сравнение К: К(] Если  К > K_j , то перейти к шагу S5  (Мы нашли искомое место для записи R.)

S4. [Перемещение R_j,  уменьшение i.) Присвоить  R_i+1ß R_j , i ß i - 1.  Еcли  i > 0, то вернуться к шагу S3. (Еcли  i=0, то К  — наименьший из рассмотренных до сих пор ключей, а значит, запись R должна занять первую позицию.)

S5. (Перенос R на место R_i+1) Присвоить R_i+1ß R

В табл. 1 показан процесс  выполнения алгоритма S на множестве из шестнадцати чисел, которые используются для примеров в этом разделе. Данный метод чрезвычайно просто реализуется программно.

Время выполнения этой программы  равно 9B+10N—ЗА—9 машинных циклов, где N — число сортируемых запасен, А — число случаев, когда на шаге S4 значение i убывает до 0, а В — количество перемещений записей. Ясно, что А равно числу случаев, когда Kj < min{K1,... ,K j-i) при 1 < j < N,   т. e. это число левосторонних минимумов. Нетрудно прийти к выводу, что В тоже известно: число перемещения записей при фиксированном j равно числу инверсий ключа Kj, так что В равно числу инверсий перестановки К1, К2,...KN. Следовательно,

 

 

Схематически метод сортировки простыми вставками можно схематически изобразить следующим образом. На рис.2 (a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.2(b) для числа 1. Наконец, на рис.2(c) мы завершаем сортировку, поместив 2 на нужное место.

Если длина нашего массива  равна n, нам нужно пройтись по n - 1 элементам. Каждый раз нам может понадобиться сдвинуть n - 1 других элементов, получая алгоритм с временем работы O(n2).

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

 

 

Рис. 2   Сортировка вставками

  

 

 

 

 

 

3.2. Метод последовательного поиска в упорядоченной таблице

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

1. .
2. Если , перейти к шагу 4.
3. , перейти к шагу 2.
4. Если , алгоритм заканчивается успешно. В противном случае -  неудачное завершение алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. ПРАКТИЧЕСКАЯ  ЧАСТЬ

Блок-схемы:

1. Блок-схема алгоритма сортировки простыми вставками

 

 

 

 

 

 

 

 

2. . Блок-схема алгоритма  последовательного поиска в упорядоченной таблице

 

 

 

 

 

 

 

 

 

 

 

 

 

2. . Блок-схема программы сортировки

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. . Блок-схема программы поиска

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. . Описание программы сортировки

Блок 1 является начальным. В  блоке 2 происходит объявление переменных. В блоке 3 проверяется заданы ли значения диапазона и числа элементов. В блоке 4 Переменным count и range присваиваются значения. В блоке 5 задается размер массива, а в блоке 6 размеры таблиц.  В блоках 7,8 в происходит заполнение таблицы случайными числами. В блоке 9 -10 значения заносятся в массив – а. В 11 блоке в переменную d1 заносится текущее время.

В блоке 12 вызываются процедуры  сортировки. В блоке 13 выводится  отсортированные массивы. Блок 14 – конец программы .

 

5. . Описание программы поиска

Блок 1 является начальным. В  блоке 2 проверяется задан ли образец. В блоке 3 задается размер массива, а  в блоке 4 заполняется массив – a. В 5 блоке в переменную d1 заносится текущее время. В блоке 6 вызывается функция поиска образца в отсортированном по возрастанию массиве. Блоке 7-8 - поиск образца в массиве отсортированном по убыванию. В блоке 9 выводятся результаты.

Блок 10 – конец программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. ЛИСТИНГ ПРОГРАММЫ

unit Unit1;

 

interface

 

uses

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

  Dialogs, StdCtrls, Grids,DateUtils;

 

type

  TForm1 = class(TForm)

    lbl1: TLabel;

    strngrd1: TStringGrid;

    strngrd2: TStringGrid;

    lbl2: TLabel;

    lbl3: TLabel;

    strngrd3: TStringGrid;

    lbl4: TLabel;

    edt1: TEdit;

    edt2: TEdit;

    lbl5: TLabel;

    btn1: TButton;

    lbl6: TLabel;

    edt3: TEdit;

    lbl7: TLabel;

    edt4: TEdit;

    btn2: TButton;

    edt5: TEdit;

    lbl8: TLabel;

    lbl9: TLabel;

    edt6: TEdit;

    edt7: TEdit;

    lbl10: TLabel;

    lbl11: TLabel;

    edt8: TEdit;

    procedure btn1Click(Sender: TObject);

    procedure btn2Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

var

  Form1: TForm1;

  count:Integer;

implementation

 

{$R *.dfm}

procedure SortToInc(a:array of Integer);

var

i,j,x : integer;

begin

 

  for i := 2 to count do

  begin

    x := a[i];

    j := i - 1;

    while ((j > 0) and (a[j]>x)) do

    begin

      a[j+1] := a[j];

      j:=j-1;

    end;

    a[j+1] := x;

  end;

  for i := 1 to count do begin

      Form1.strngrd2.Cells[i-1,0]:=IntToStr(a[i]);

      end;

end;

procedure SortToDec(a:array of Integer);

var

i,j,x : integer;

begin

 

  for i := 2 to count do

  begin

    x := a[i];

    j := i - 1;

    while ((j > 0) and (a[j]<x)) do

    begin

      a[j+1] := a[j];

      j:=j-1;

    end;

    a[j+1] := x;

  end;

  for i := 1 to count do begin

      Form1.strngrd3.Cells[i-1,0]:=IntToStr(a[i]);

      end;

end;

function FindInc(a:array of Integer):AnsiString;