Описание типа учебного массива

Описание этого типа массива дадим в интерфейсной части модуля. Оно может выглядеть так.

unit UnitArrayDop;

 

Interface

type TArray100= array [1..100] of integer;

 

Процедуры создания, ввода и вывода массивов

Несмотря на различие задач, решаемых этими процедурами, у них будет две одинаковых особенности.

Первая состоит в том, что в каждую из этих процедур будет передаваться имя массива. В тех случаях, когда процедура используется для создания массива, его следует передавать через var, то есть «по имени». Если же массив передается для вывода, то его следует передавать через const.

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

7.2.2.1 Процедура создания случайного массива

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

procedure createRandomArray(var a:TArray100; count, modul: integer);

var i:integer;

Begin

randomize;

for i:=1 to count do a[i]:=random(modul);

end;

7.2.2.2 Процедура ввода массива из строки текста

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

//Считывание массива из строки символов

procedure getArrayFromStr(var a:TArray100; var count: integer; const s: String);

var wordEndPos: integer; w: String [20];

Begin

count:= 0;

while length(Trim(s))>0 do

Begin

// Удаляем пробелы

s:=Trim(s);

// Находим позицию конца очередного слова

wordEndPos:=Pos(' ',s); // Ищем пробел

if wordEndPos = 0 // Пробела не нашли,

then // значит конец слова это конц строки

wordEndPos:= length(s)

else // Конец слова левее пробел а

wordEndPos:= wordEndPos -1;

// Копируем слово в переменную w

w:= Copy (s,1,wordEndPos);

// и удаляем его из строки

Delete (s,1,wordEndPos);

// Увеличиваем счетчик слов на 1

count:= count + 1;

//Преобразуем слово в число и записываем в массив

a[count]:=strToInt(w);

end; // Конец цикла поиска слов и формирования массива

end; // Конец цикла поиска слов и формирования массива

7.2.2.3 Процедура ввода массива из компонента TMemo

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

//Считывание массива из Memo

procedure getArrayFromMemo(var a:TArray100; var count: integer;

mem: TMemo);

var i: integer;

Begin

//Узнаем количество строк

count:= Mem.Lines.Count;

// Поочередно обрабатываем строки

for i:= 0 to count - 1 do a[i+1]:= strToInt(Mem.Lines[i]);

end;

7.2.2.4 Процедура ввода массива с помощью функции InputBox

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

//Считывание массива из InputBox

procedure getArrayFromInputBox(var a:TArray100; var count:integer);

var i:integer; w: String;

Begin

w:= InputBox('Ввод массива типа TArray100',

'Сколько элементов ввести', '5');

count:= strToInt(w);

for i:= 1 to count do

Begin

w:= InputBox(format('Ввод массива из %d элементов', [count]),

'Введите элемент № '+intToStr(i), '0');

a[i]:= strToInt(w);

end;

end;

7.2.2.5 Функция преобразования массива в строку символов

Функция формирует из чисел массива строку, в которой числа разделены пробелами. Эта строка может быть выведена в showMessage, компоненты TEdit, TLabel, и другие подобные компоненты.

Для работы функции передается ссылка на массив и его размер. Возвращает функция – строку.

 

//Преобразование массива в строку

function ArrayToStr(const a:TArray100; count: integer): string;

var i: integer;

Begin

result:= '';

for i:=1 to count do result:= result + ' ' + intToStr(a[i]);

end;

7.2.2.6 Процедура вывода массива в компонент TMemo

В эту процедуру передается ссылка на массив, количество элементов массива, и ссылка на компонент типа TMemo, в котором в виде последовательности строк будут записаны элементы массива. В результате массив расположится вертикально.

 

//Вывод массива в MEMO

procedure showArrayInMemo(const a:TArray100; count: integer; mem:TMemo);

var i: integer;

Begin

mem.clear;

for i:= 1 to count do

Begin

mem.Lines.Append(intToStr(a[i]));

end;

end;

 

Обработка массивов

Операции с массивами также целесообразно оформить в виде процедур и функций. Эти подпрограммы добавлены в модуль UnitArrayDop.

7.2.3.1 Функция вычисления суммы элементов массива

В функцию передается ссылка на массив и его размер. Возвращает функция сумму элементов массива.

//Вычисление суммы элементов

function sumArray(const a:TArray100; count: integer): integer;

var i: integer;

Begin

result:=0;

for i:=1 to count do result:= result + a[i];

end;

 

7.2.3.2 Процедура определения минимального, максимального, и их индексов в массиве

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

//Вычисление максимального и минимального и их индексов

procedure minMax(const a:TArray100; count: integer;

var min, max, iMax, iMin: integer);

var i: integer;

Begin

min:= a[1]; max:= a[1];

for i:= 1 to count do

if a[i] > max

Then begin

max:= a[i];

iMax:= i;

End

else if a[i] < min

Then begin

min:= a[i];

iMin:= i;

end;

end;

7.2.3.3 Функция определения позиции элемента в массиве

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

 

//Определение позиции элемента

function posInArray(element: integer; const a: TArray100; count: integer): integer;

var i: integer;

Begin

Result:= 0;

For i:= 1 to count do

if a[i] = element

Then begin

result:= i;

exit;

end;

end;

7.2.3.4 Процедура удаления элементов из массива

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

 

//Удаление элемента из массива

procedure delElem(element: integer; var a: TArray100; var count: integer);

var i, j: integer;

Begin

i:= 1;

while i <= count do

Begin

if a[i] = element then

Begin

count:= count - 1;

for j:= i to count do a[j]:= a[j+1];

End

else i:= i + 1;

end;

end;

 

7.2.3.5 Процедура переворота массива

В этой процедуре элементы массива, симметрично расположенные относительно середины, меняются местами.

//Переворот массива

procedure trans(var a: TArray100; count: integer);

var tmp, i: integer;

Begin

for i:= 1 to count div 2 do

Begin

tmp:= a[i];

a[i]:= a[count – i + 1];

a[count – i + 1]:=tmp;

end;

end;

7.2.3.6 Процедура циклического сдвига части элементов массива влево

В этой процедуре элементы массива с индексами от i1 до i2 сдвигаются влево на 1 элемент, а элементы с индексами i1 и i2 меняются местами. Если i1 =1, а i2 равно размеру массива, то сдвигается весь массив.

 

//Сдвиг массива влево

procedure shiftLeft(var a: TArray100; count, i1, i2: integer);

var tmp, i: integer;

Begin

if i2 > count then i2:= count;

tmp:= a[i1];

for i:= i1 + 1 to i2 do a[i-1]:= a[i];

a[i2]:= tmp;

end;

 

7.2.3.7 Процедура формирования массива накопленных значений

Эта процедура создает новый массив, такой же длины, как и исходный, но в этом массиве каждый элемент равен сумме элементов в исходном массиве от первого до текущего элемента.

 

//Формирование массива накопленных значений

procedure accum(const a: TArray100; var b: TArray100; count: integer);

var i: integer;

Begin

b[1]:= a[1];

for i:= 2 to count do b[i]:= b[i-1] + a[i];

end;

7.3 Задание для самостоятельной работы

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

Главное меню проекта должно включать следующие пункты:

– создание массива,

– числовые характеристики,

– формирование нового массива.

На форме должны быть поля для ввода количества элементов массива и модуля для элементов массива (ограничителя величины числа).

Вывод числовых характеристик на усмотрение разработчика.

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

Глобальные переменные для хранения массива и количества данных в нем использовать не следует.

При выполнении каждого пункта меню всю необходимую информацию считывать с формы.

При разработке проекта можно использовать процедуры и функции модуля UnitArrayDop.

 

Таблица 7.1 – Задания на лабораторную работу
№	Создание исходного массива	Хранение исходного массива	Числовые характеристики	Получение нового массива	Вывод нового массива
	Random	TEdit	Размах элементов (max-min)	Удаление четных элементов из массива	TMemo
	InputBox	TMemo	Разность сумм элементов в четных и нечетных позициях	Оборот массива	TEdit
Продолжение таблицы 7.1
	Random	TEdit	Определение позиций четных элементов	Вставка элемента в заданную позицию	TLabel
	InputBox	TLabel	Определение позиций элементов, которые меньше среднего арифметического	Удаление заданного элемента из массива	Show Message
	Random	TMemo	Разность сумм четных и нечетных элементов	Заданное число циклических сдвигов влево	Show Message
	InputBox	TLabel	Количество четных и нечетных элементов	Вставка суммы элементов в начало массива	TMemo
	Random	TMemo	Средние арифметические четных и нечетных элементов	Заданное число циклических сдвигов вправо	TEdit
	InputBox	TMemo	Поиск позиции заданного элемента	Вставка среднего арифметического значения в середину массива	TLabel
	Random	TLabel	Количество элементов больше и меньше среднего	Вначале нечетные, затем четные	Show Message
	InputBox	TEdit	Сумма элементов больше и меньше среднего	Минимальный в начало, макси-мальный в конец	TMemo

7.4 Содержание отчета.

– Наименование работы

– Цель работы

– Краткое описание основных понятий, связанных с массивами

– Тексты процедур и функций, написанных самостоятельно

– Контрольные примеры работы пунктов проекта

– Результаты выполнения пунктов проекта в виде копий экранов

– Выводы

Контрольные вопросы

– Определение понятия массив

– Объявление статических массивов

– Операции с массивами и алгоритмы их выполнения.

– Написать реализацию одного из вариантов из таблицы 7.1

8 ЛАБОРАТОРНАЯ РАБОТА № 8. СОРТИРОВКА МАССИВОВ

Цели работы:

– Познакомиться с понятием сортировки массивов.

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

– Познакомиться с сортировкой обменом (метод пузырька).

– Познакомиться с сортировкой массива методом вставки.

– Познакомиться с операцией – вставка элемента в отсортированный массив.

– Создать приложение, в котором наглядно выполняется сортировка одномерного массива различными методами, а также вставка элемента в отсортированный массив. Обеспечить выбор операции над массивом с помощью компонента MainMenu. Используя знакомые уже компоненты Memo или Edit осуществить возможность обмена данными между массивом и экраном.

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

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

Сортировка массива – процесс перестановки элементов массива с целью размещения элементов массива в определенном порядке.

Например, если сортируется массив А чисел по возрастанию, то после сортировки этого массива будет выполняться условие:

 

A[1] < A[2] < A[3] < …….< A[n]

 

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

Существуют различные методы сортировки массивов.

Самыми простыми методами сортировки являются:

– сортировка выбором;

– сортировка обменом (метод пузырька);

– сортировка вставкой (или включением).

 

 

Сортировка выбором.

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

1. Среди всех элементов массива, начиная с первого, каким либо способом отыскивается минимальный элемент.

2. Найденный минимальный элемент помещается на место первого элемента.

3. Просматривается массив от второго элемента, находится минимальный среди оставшихся и помещается на место второго элемента.

4. И так далее до последнего элемента.

Рисунок 8.1 - Алгоритм сортировки по возрастанию методом выбора

Анализ описанных выше действий при сортировке выбором показывает, что для программной реализации этого метода сортировки потребуется два цикла for.

Во внешнем цикле должен изменяться номер изменяемого элемента от первого до предпоследнего. Этот цикл будет определять количество проходов по массиву.

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

В теле внутреннего цикла производится сравнение элементов, индексы которых задаются параметрами внешнего и внутреннего цикла. Если при сравнении оказывается, что порядок следования элементов нарушен, то сравниваемые элементы меняются местами.

Схема алгоритма сортировки массива методом выбора показана на рисунке 8.1.

Исходными данными для алгоритма являются: сортируемый массив mas и количество элементов в этом массиве count.

8.1.1.1 Пример сортировки массива по возрастанию методом выбора

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

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

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

Проиллюстрируем алгоритм этой сортировки рисунками. Исходное расположение элементов массива показано на рисунке 8.2.

Рисунок 8.2 – Исходная схема сортируемого массива

После обмена местами A[1] и A[2] массив будет иметь вид, показанный на рисунке 8.3.

Рисунок 8.3 – Схема сортируемого массива после первого обмена элементов

Далее будут сравниваться элементы A[3] и A[1], но так как A[3]не меньше A[1], то A[3] остается на месте.

Анализ элемента A[4] показывает, что он меньше, чем A[1], поэтому его следует поменять местами с A[1]. Результат изменений показан на рисунке 8.4.

 

Рисунок 8.4 – Схема сортируемого массива после второго обмена элементов

Далее будут сравниваться элементы A[5] и A[1], но так как A[5]не меньше A[1], то A[5] остается на месте.

На этом первый проход сортируемого массива заканчивается. В результате этого прохода в первой позиции массива оказался наименьший элемент.

Теперь необходимо осуществить второй проход по массиву, но в качестве изменяемого берется уже второй элемент массива. Со вторым элементом будут сравниваться элементы, начиная с третьего. В результате чего на второе место будет поставлен минимальный элемент среди элементов со 2-го по 5-й. Результаты второго прохода по массиву представлены на рисунке 8.5.

Рисунок 8.5 – Схема второго прохода при сортировке массива методом выбора

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

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

Рисунок 8.6 – Схема последних проходов по массиву при сортировке методом выбора

8.1.1.2 Процедура сортировки массива методом выбора

procedure SortChoise (var a: TArray100; count: integer);

var i, j, x: integer;

Begin

for i:= 1 to count - 1 do

Begin

for j:= i + 1 to count do

if a[j] > a[i] then

Begin

x:= a[i];

a[i]:= a[j];

a[j]:= x;

end;

end;

end;

8.1.2 Сортировка обменом (метод пузырька)

Алгоритм основан на принципе сравнения и обмена пары соседних элементов.

Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами.

Рисунок 8.7 - Алгоритм сортировки по возрастанию методом обмена

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

Затем все повторяется заново и наибольший среди оставшихся элементов оказывается на предпоследнем месте.

Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут). Этот метод получил название метод пузырька, что, очевидно, если располагать массивы вертикально.

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

Схема алгоритма сортировки массива методом обмена показана на рисунке 8.7.

Сортировка реализуется с помощью двух циклов. Внешний цикл выполняется до тех пор, пока при завершении очередного прохода по массиву не окажется, что перестановок элементов делать не пришлось. В этом случае переменная ok сохранит значение true, и это будет означать, что массив отсортирован. Так как условие отсутствия перестановок элементов при проходе по массиву можно проверить только после завершения прохода, то очевидно, что в данном случае следует использовать цикл repeat... until.

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

8.1.2.1 Пример сортировки массива по возрастанию методом обмена

На рисунках 8.8 – 8.12 подробно показаны изменения массива в процессе сортировки обменом во время первого прохода по массиву.

Рисунок 8.8 – Массив перед сортировкой обменом

 

Рисунок 8.9 – Массив после первого обмена элементов

 

Рисунок 8.10 – Массив после второго обмена элементов

Рисунок 8.11 – Массив после третьего обмена элементов

 

Рисунок 8.12 – Массив после первого прохода

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

Второй проход по массиву рассмотрим менее детально. Его результаты представлены на рисунке 8.13.

Рисунок 8.13 – Второй проход по массиву

Во втором проходе понадобился только один обмен, и в результате не только A[4], но и A[3] оказались на своих местах.

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

Результаты последнего прохода по массиву показаны на рисунке 8.14.

Рисунок 8.14 – Результаты третьего проход по массиву

8.1.2.2 Процедура сортировки массива методом обмена

procedure SortBubl(var a: TArray100; count: integer);

var last, i, x: integer; ok: boolean;

Begin

last:= count;

Repeat

ok:= true;

for i:= 1 to last - 1 do

if a[i] > a[i+1] then

Begin

x:= a[i];

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

a[i+1]:= x;

ok:= false;

end;

last:= last - 1;

until ok;

end;