Программирование. 6
Оглавление
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) скорость от количества
символов в указанных
- ОПИСАНИЕ ПЕРЕМЕННЫХ И ПРОЦЕДУР
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) - осуществляет поиск образца.
- ВВЕДЕНИЕ
В XXI веке, как никогда, встала проблема
хранения, перемещения, защиты информации,
а для этого информацию нужно правильно
расположить, т. е. отсортировать в порядке
убывания или возрастания. Не одна большая
программа не обходится без сортировщика
слов, чисел, списков. В таких программах
сортировщик должен работать быстро эффективно
и без сбоев.
Современные вычислительные системы работают наиболее эффективно при упорядоченных данных. Сортировка информации — это процесс расстановки элементов в некотором порядке. Элементы размещаются следующем образом:
1) вычисления, которые требуют определенного порядка расположения данных, упорядоченных по возрастанию или убыванию, могли выполняться эффективно,
2) результаты имели осмысленный вид,
3) последующие операции имели бы упорядоченные исходные данные.
Сортировка во все времена имела большое значение. Например, в Древнем Риме или Греции немногие пользовались библиотеками. Почему? Они не сортировали книги по алфавиту или какому-то ещё признаку. Из-за этого поиск 1 книги мог занять недели, месяцы и даже годы.
В век же компьютерных технологий
этот вопрос стал особенно остро. Ведь
теперь когда многие вещи автоматизированы,
требуется быстрая и
Было придумано множество
- ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
3.1 Сортировка простыми вставками
Один из простейших способов отсортировать массив - сортировка вставками.
Этот способ предполагает, что перед рассмотрением записи rj предыдущие записи R1,..., Rj-1 уже упорядочены и rj вставляется в соответствующее место. Приняв эту схему в качестве базовой, можно построить несколько любопытных ее модификаций.
Метод простых вставок. Простейший метод сортировки посредством вставок можно считать наиболее очевидным. Пусть 1 < j < N к записи Rj,...,Rj-1 уже размещены так, что (через Kt обозначается ключ записи Rj). Будем сравнивать по очереди Kj с Kj-1, Kj-2 ... до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri и Ri+1, тогда подвинем записи Ri+1 и на одну позицию вверх и поместим новую запись в позицию i + 1. Удобно совмещать операции сравнение и перемещения, перемещая их между собой, как продемонстрировало в следующем алгоритме; поскольку запись Rj как бы "погружается" на положенный ей уровень, этот способ часто называют просеиванием или погружением (рис. 1).
Рис. 1. Алгоритм S: сортировка методом простых вставок.
Алгоритм S (Сортировка методам простых вставок). Записи R1, …, RN переразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены: K1<=…<= KN.
S1. [Цикл по j.] Выполнить шаги от S2 до S5 при i = 2,3,...Т и после этого завершить выполнение процедуры.
S3. [Установка i, К, R] Присвоить I ß j - 1, Kß Kj, Rß Rj. (На последующих шагах будет предпринята попытка вставить запись R в нужное место, сравнивая К с Kj ( при убывающих значениях i.)
S3. [Сравнение К: К(] Если К > Kj , то перейти к шагу S5 (Мы нашли искомое место для записи R.)
S4. [Перемещение Rj, уменьшение i.) Присвоить Ri+1ß Rj , i ß i - 1. Еcли i > 0, то вернуться к шагу S3. (Еcли i=0, то К — наименьший из рассмотренных до сих пор ключей, а значит, запись R должна занять первую позицию.)
S5. (Перенос R на место Ri+1) Присвоить Ri+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. Метод последовательного поиска в упорядоченной таблице
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод последовательного поиска в упорядоченной таблице. Алгоритм последовательного поиска в упорядоченной таблице реализуется следующим образом. Дана таблица записей , ключи которых расположены в порядке возрастания . Алгоритм предназначен для поиска записи с ключом .
- .
- Если , перейти к шагу 4.
- , перейти к шагу 2.
- Если , алгоритм заканчивается успешно. В противном случае - неудачное завершение алгоритма.
- ПРАКТИЧЕСКАЯ ЧАСТЬ
Блок-схемы:
- Блок-схема алгоритма сортировки простыми вставками
- . Блок-схема алгоритма последовательного поиска в упорядоченной таблице
- . Блок-схема программы сортировки
- . Блок-схема программы поиска
- . Описание программы сортировки
Блок 1 является начальным. В блоке 2 происходит объявление переменных. В блоке 3 проверяется заданы ли значения диапазона и числа элементов. В блоке 4 Переменным count и range присваиваются значения. В блоке 5 задается размер массива, а в блоке 6 размеры таблиц. В блоках 7,8 в происходит заполнение таблицы случайными числами. В блоке 9 -10 значения заносятся в массив – а. В 11 блоке в переменную d1 заносится текущее время.
В блоке 12 вызываются процедуры сортировки. В блоке 13 выводится отсортированные массивы. Блок 14 – конец программы .
- . Описание программы поиска
Блок 1 является начальным. В блоке 2 проверяется задан ли образец. В блоке 3 задается размер массива, а в блоке 4 заполняется массив – a. В 5 блоке в переменную d1 заносится текущее время. В блоке 6 вызывается функция поиска образца в отсортированном по возрастанию массиве. Блоке 7-8 - поиск образца в массиве отсортированном по убыванию. В блоке 9 выводятся результаты.
Блок 10 – конец программы.
- ЛИСТИНГ ПРОГРАММЫ
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]:=
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]:=
end;
end;
function FindInc(a:array of Integer):AnsiString;
var
i,j,x,k : Integer;
str: AnsiString;
begin
x := StrToInt(Form1.edt4.Text);
k:=0;
i:=1;
while((i<=count) and (x>=a[i])) do
begin
if(x=a[i])then begin k:=k+1; str:=str+' '+IntToStr(i); end;
i:=i+1;
end;
if(k=0)then str :='Нет такого элемента';
Form1.edt7.Text:=IntToStr(k);
Result:= str;
end;
function FindDec(a:array of Integer):AnsiString;
var
i,j,x,k : Integer;
str: AnsiString;
begin
x := StrToInt(Form1.edt4.Text);
k:=0;
i:=1;
while((i<=count) and (x<=a[i])) do
begin
if(x=a[i])then begin k:=k+1; str:=str+' '+IntToStr(i); end;
i:=i+1;
end;
Form1.edt7.Text:=IntToStr(k);
if(k=0)then str :='Нет такого элемента';
Result:= str;
end;
procedure TForm1.btn1Click(Sender: TObject);
var range,i:Integer;
a:array of Integer;
d1: TDateTime;
begin
if((Length(edt1.Text)>0) and (Length(edt2.Text)>0)) then
begin
count := StrToInt(edt1.Text);
range := StrToInt(edt2.Text);
btn2.Enabled:=True;
SetLength(a,count+1);
Randomize;
strngrd1.ColCount := count;
strngrd2.ColCount := count;
strngrd3.ColCount := count;
for i := 1 to count do strngrd1.Cells[i-1,0] := IntToStr(Random(range));
for i := 1 to count do a[i]:= StrToInt(strngrd1.Cells[i-1,0]
d1:=Now;
SortToInc(a);
SortToDec(a);
edt3.Text:=FloatToStr(
end;
end;
procedure TForm1.btn2Click(Sender: TObject);
var
i :Integer;
a:array of Integer;
d1: TDateTime;
begin
if(Length(edt4.Text)>0)then
begin
SetLength(a,count+1);
for i := 1 to count do a[i]:= StrToInt(strngrd2.Cells[i-1,0]
d1:=Now;
edt5.Text:=FindInc(a);
for i := 1 to count do a[i]:= StrToInt(strngrd3.Cells[i-1,0]
edt8.Text:=FloatToStr(
edt6.Text:=FindDec(a);
end;
end;
end.
- ИНТЕРФЕЙС ПРОГРАММЫ
- ТАБЛИЦЫ РЕЗУЛЬТАТОВ
1) 10 – 300 элементов:
|
||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
2) 300-5000 элементов
Кол. Элементов |
время |
скорость |
300 |
0,48 |
625 |
1100 |
1,6 |
687,5 |
2000 |
3,1 |
645,1612903 |
2900 |
4,7 |
617,0212766 |
3800 |
5,6 |
678,5714286 |
4700 |
6,3 |
746,031746 |
5000 |
7,8 |
641,025641 |
3) 5000-10000 элементов
Кол. Элементов |
время |
скорость |
5000 |
7,8 |
641,025641 |
5900 |
9,4 |
627,6595745 |
6800 |
10,1 |
673,2673267 |
7700 |
13,9 |
553,9568345 |
8600 |
15,6 |
551,2820513 |
9500 |
20,3 |
467,9802956 |
10000 |
23,4 |
427,3504274 |
- ЗАКЛЮЧЕНИЕ
Важным свойством алгоритма является его сфера применения. Здесь основных позиций две:
- внутренние сортировки работают с данным в оперативной памяти с произвольным доступом;
- внешние сортировки упорядочивают информацию, расположенную на внешних носителях. Это накладывает некоторые дополнительные ограничения на алгоритм:
- доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим,
- объем данных не позволяет им разместиться в ОЗУ.
- Доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
Данный класс алгоритмов делится на два основных подкласса:
Внутренняя сортировка оперирует с массивами, целиком, умещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (сортировка файлов), т.е. в данный момент только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство.
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
количество присваиваний;
количество сравнений.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер с англ. – М.: Издательский дом “Вильямс”, 2001. – 832 с.: ил.
2. Марков А.С., Милов М.П.., Пеледов Г.В.: Программное обеспечение ЭВМ.кн.11, 1995. -356 с.: ил.
3. Фаронов В.В. Турбо-Паскаль (в 3 книгах). - М.: "МВТУ-ФЕСТО ДИДАКТИК", 1992-1993.
4. Прайс Д. Программирование
на языке Паскаль: