Лекция 6 структурированные типы данных. Массивы План лекции

• Понятие массива. Способы описания массивов

• Действия над элементами массивов

• Примеры обработки массивов

• Сортировка массивов

• обменные сортировки

• сортировки выбором

• сортировка «вставками»

• сортировка «слияниями» (алгоритм фон Неймана)

Понятие массива. Способы описания массивов

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

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

Тип элементов массива называется базовым. Число элементов массива фиксируется при описании и в процессе выполнения программы не меняется. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа, кроме вещественного. Тип индекса определяет границы изменения значений индекса. Например, массив A состоит из элементов a₁, a₂, a₃, . . . a_n. Здесь а – имя элемента массива, n – его индекс, т.е. порядковый номер в массиве, по которому можно определить (найти) каждый элемент.

Для описания массива в языке Паскаль предназначено словосочетание ARRAY OF (массив из...). Описание массива возможно двумя способами.

Способ 1. Используя раздел описания типов

Type <имя типа> = array [тип индекса] of <тип компонент>;

Var <идентификатор>: <имя типа>;

Например, Type Mas = array[1..100] of real;

Var M1,M2:Mas;

Способ 2. Используя раздел описания переменных (Var) без представления типа в разделе описания типов данных.

Var

<идентификатор>: array [тип индекса] of <тип компонент>;

Например, Var M1, M2: array[1..100] of real;

V1: array[1..50] of integer;

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

Например, Type Vector = array [1..4] of integer;

Massiv = array [1..4] of Vector;

Var M1:Massiv;

Ту же структуру можно получить, используя другую форму записи:

Var M1: array[1..4,1..4] of integer;

Таким образом, многомерный массив задается при помощи индексированных выражений, следующих друг за другом. Если индексное выражение одно, то массив называется одномерным, если два – двумерным (матрица), если n – n-мерным. Одномерные массивы в Паскале обычно используются для представления векторов, двумерные – для представления матриц.

Например, Var Vector = array [1..5] of real;

{одномерный массив-вектор из 5-ти элементов типа real}

Matr = array [1..4,1..3] of integer;

{матрица из 4-х строк и 3-х столбцов с элементами типа integer}

При описании массивов для задания границ индексов можно использовать предварительно определенные константы. Например,

Const G1=4;G2=5;

Var Matr = array [1..G1,1..G2] of integer;

Элементы массива располагаются в памяти последовательно, по строкам. Для массива Matr:

Matr[1,1] Matr[1,2] Matr[1,3]

Matr[2,1] Matr[2,2] Matr[2,3]

Matr[3,1] Matr[3,2] Matr[3,3]

Matr[4,1] Matr[4,2] Matr[4,3]

При обращении к элементам массива на Паскале индекс указывается в квадратных скобках: А[i], B[i,j].

При работе с массивами необходимо помнить следующее:

массив – это структура данных, представляющая собой совокупность элементов одного типа;

при объявлении массива указывается количество элементов массива;

доступ к элементу массива осуществляется путем указания индекса (номера) элемента массива.

Тип индекса элемента массива может быть только скалярным. Наиболее часто в качестве типа индекса используется ограниченный тип [1], причем в большинстве случаев это ограниченный целый тип.

Так, например, массив из 100 компонент вещественного типа может быть задан как array [1..100] of real.

Ограниченный целый тип 1..100 определяет количество компонент – 100 и их упорядоченность – от 1-ой до 100-ой.

В большинстве задач нумерация компонент начинается от 1 и ограничивается положительным целым числом. Но это необязательно. Если, например, представить в виде массива численность г. Москвы [1] в отдельные годы, то нумерацию удобно начинать с 1147 – года основания Москвы и до 2006 , т.е. такой массив можно задать как array[1147..2006] of integer;, а для Рима, основанного в 754 г. до н.э. – array[-754..-1] of integer;.

Здесь –1 –последний год до н.э.

Каждый из рассмотренных массивов может быть задан двояко:

1. используя описание типа:

Type vector = array[1..100] of real;

ch_M = array[1147..2006] of integer;

ch_R = array[-754..-1] of integer;

Var a, b: vector;

c: ch_M; d: ch_R;

Обращение к элементам массивов с и d: с[1147], c[1999] и т.п., то есть с[i], d[i];

2) непосредственно при описании переменной:

Var a,b: array[1..100] of real;

c: array[1147..2006] of integer;

d: array[-754..-1] of integer;

Использование ограниченного целого типа для индексов дает достаточно широкие возможности для описания массивов.

Множество значений перечисляемого типа также образует ограниченное перенумерованное множество. Следовательно, перечисляемый тип также может быть использован в качестве типа индексов [1]. Значения перечисляемого типа упорядочены (порядок задается порядком перечисления имен, являющихся значениями этого типа), и число их конечно (определяется количеством имен в этом типе).

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

Type Month = (Jan, Feb, Mar, Apr, … , Deс);

Тогда переменные, являющиеся векторами среднемесячных температур, можно определить следующим образом: Var t,r: array[Month] of real;

Частичные компоненты массива, обозначающие температуру каждого месяца, запишутся следующим образом: t[Yan], t[Feb], t[apr] и т. п. Если ввести переменную m типа Month (m: Month), то можно обращаться t[m], где m меняется от Jan до Deс.

В качестве типа индексов могут использоваться также стандартные типы Boolean и Char. Например,

Type priznak = array[Boolean] of integer;

kod_s = array[Char] of integer;

Var k: priznak; s: kod_s;

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

k[False], k[True]; s[‘d’], s[‘h’].

Для работы с массивом как с единым целым используется идентификатор массива без указания индекса в квадратных скобках. Если массивы описаны одинаково, то с ними можно проводить следующие операции [5]:

Проверка на равенство: А=В. Результатом является значение «истина», если каждый элемент массива А равен соответствующему элементу массива В.

Проверка на неравенство: А<>В. Результатом является значение «истина», если значение хотя бы одного элемента массива А не равно значению соответствующего элемента массива В.

Присваивание. А:=В. Все значения элементов массива В присваиваются элементам массива А. Значения элементов массива В остаются без изменения.

Действия над элементами массивов

После объявления массива каждый его элемент можно обработать, указав идентификатор массива и индекс элемента в квадратных скобках. Рассмотрим типичные ситуации, возникающие при работе с массивами. Для этого опишем четыре одномерных массива: два (A и B) из элементов целочисленного типа, два (C и D) из элементов вещественного типа и два двумерных массива (V и W), содержащих элементы вещественного типа.

Var A, B: array[1..5] of integer;

C, D: array [1..10] of real;

V, W: array [1..4,1..4] of real;

Инициализация массива

Инициализация – это присваивание каждому элементу массива какого-либо (или одного и того же) значения типа. Например, A[1]:=0; A[2]:=0; ... A[5]:=0 или V[1,1]:=0; V[1,2]:=0; и т.д. Но при большом количестве элементов такой способ инициализации нерационален. Гораздо удобнее получить такой же результат, используя оператор FOR:

For I:=1 To 5 Do A[I]:= 0;

For I:=1 To 4 Do For J:=1 To 4 Do V[I,J]:=0;

Ввод элементов массива

Паскаль не имеет средств ввода-вывода элементов массива сразу, поэтому ввод и вывод значений производится поэлементно. Чаще всего они вводятся с помощью оператора Read (Readln) с использованием оператора цикла For:

For I:=1 To M Do Begin W Writeln(‘Введите ’,I,’ элемент массива’); Read(A[I]); End;

For I:=1 To M Do Begin Writeln(‘Введите ’,I,’строку’); For J:=1 To N Do Read(V[I,J]); End;

Вывод элементов массива

производится аналогично, но с использованием оператора Write (Writeln).

Writeln(‘Вывод массива A’); For I:=1 To M Do Write(A[I]:4:2,' ':2); Writeln;

Writeln(‘Вывод массива V’); For I:=1 To M Do Begin For J:=1 To N Do Write(V[I,J]:4:2,' ':2); Writeln; End;

Копирование элементов из одного массива в другой

Для выполнения этого действия необходимо, чтобы массивы, участвующие в этой операции, были описаны одинаково. Например, В:=А; - верно, так как В и А имеют одинаковый тип компонент; А:=С; – неверно, т.к. С имеет компоненты типа real, а А – типа integer и массивы А и С разной длины). Или, используя цикл:

For I:=1 To M Do Begin B[I]:=A[I]; C[I]:=B[I] End;

For I:=1 To M Do For J:=1 To N Do W[I,J]:=V[I,J];

Поиск в массиве элементов, удовлетворяющих некоторым условиям

Пусть надо выяснить, сколько элементов в массивах С и W имеют нулевое значение.

K:=0; For I:=1 To M Do If C[I]=0 Then K:=K+1;

K:=0; For I:=1 To M Do For J:=1 To N Do If W[I,J]=0 Then K:=K+1;

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

Поиск минимального (максимального) элемента массива рассмотрим на примере поиска минимального элемента в одномерном массиве С и максимального – в двумерном массиве W.

Min:=C[1]; For I:=1 To M Do If C[I]<Min Then Min:=C[I];

Max:=W[1,1]; For I:=1 To M Do For J:=1 To N Do If W[I,J]>Max Then Max:=W[I,J];

Вычисление суммы (произведения) элементов массива

Найти сумму (S) и произведение (P) элементов массивов С и W.

S:=0; P:=1; For I:=1 To M Do Begin S:=S+С[I]; P:=P*С[I]; End;

S:=0; P:=1; For I:=1 To M Do For J:=1 To N Do Begin S:=S+W[I,J]; P:=P*W[I,J]; End;

Перестановка элементов массива

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

Поменять местами первый и четвертый элемент массива А	Поменять местами первый, первый и четвертый, четвертый элемент массива W
Per:=А[1]; A[1]:=A[4]; A[4]:=Per;	Per:=W[1,1]; W[1,1]:=W[4,4]; W[4,4]:=Per;

Суммирование элементов матриц по строкам или столбцам

По строкам	По столбцам
For I:=1 To M Do Begin Str[I]:=0; For J:=1 To N Do tr[I]:=Str[I]+V[I,J]; End;	For J:=1 To N Do Begin Stl[J]:=0; For I:=1 To M Do Stl[J]:=Stl[J]+V[I,J]; End;

Поиск минимального (максимального) элемента строки(столбца)

Результатом этого поиска является одномерный массив длиной М (для строк) или N (для столбцов).

For I:=1 To M Do Begin MIN[I]:=V[I,1]; For J:=2 To N Do If V[I,J] < MIN[I] Then MIN[I]:=V[I,J]; End;

For J:=1 To N Do Begin MIN[J]:=V[1,J]; For I:=2 To M Do If V[I,J] < MIN[J] Then MIN[J]:=V[I,J]; End;

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

Рассмотрим основные действия над элементами массивов на примерах.

Пример 1. Обработка одномерного массива.

Вычислить % дней в месяце, когда температура опускалась ниже 0⁰С.

Решение

Для упрощения вычислений введем следующие обозначения:

all_d – всего дней в месяце (примем значение all_d =31);

cold_d – количество холодных дней;

t – массив температур за месяц;

pr – процент дней с отрицательной температурой.

Текст программы Cold на языке Паскаль

Program Lk_6_1;

{$APPTYPE CONSOLE}

uses

SysUtils,

Windows;

Type days = array[1..31] of real;

Var t: days;

pr: real;

cold_d,all_d:integer;

i: integer;

Begin

SetconsoleoutputCP(1251);

Writeln('Введите количество дней в месяце');

Readln(all_d);

Writeln('Введите массив температур за месяц - t');

For i:= 1 to all_d do

Read(t[i]);

cold_d:=0;

For i := 1 to all_d do

If t[i]<0 Then cold_d:=cold_d+1;

pr:=cold_d/all_d*100;

Writeln('Холодных дней',cold_d:2,' это ',pr:5:2,' %');

Sleep(10000)

End.

Пример 2. Обработка двумерного массива.

Найти след матрицы А(MxM).

Program Sled;

Var A:array[1..10,1..10] of real;

Sl:Real;

Begin

Writeln('Введите размер матрицы А -- M');

Readlm(M);

Writeln('Введите матрицу А');

For i:= 1 to M do

For j:= 1 to M do

Readln(A[I,j]);

Sl:=0;

For I:=1 To M Do

Sl:=Sl+A[I,I];

Writeln('След матрицы А=',Sl:0:2);

End.

Сортировка массивов

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

Сортировкой называется процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака [1].

Массив, например, массив А={a₁, a₂, …, a_n}, является отсортированным (упорядоченным) по возрастанию, если для всех индексов i из интервала выполняется условие .

Сортировка строк – это ранжирование данных строкового типа по алфавиту. Фактически символы, составляющие строку, упорядочиваются по их номеру в кодовой таблице ASCII. Наиболее часто сортировку строк выполняют при выводе различных списков (фамилий, названий).

Различают обменные сортировки, сортировки выбором, сортировку вставками, сортировку слиянием.

Предположим, что имеется исходный массив А={a₁, a₂, …, a₁₀}, который необходимо упорядочить по возрастанию.

Обменные сортировки

Суть обменных сортировок заключается в следующем. Сначала последовательно просматриваются элементы a₁, …, a_n и находится наименьшее i, такое, что a_i>a_i+1. Затем элементы a_i и a_i+1 меняются местами, и просмотр возобновляется с a_i+1 элемента, и т.д. Тем самым, наибольшее число передвигается на последнее место. Следующие просмотры начинаются опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы. Процесс сортировки по убыванию будет аналогичен.

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

Для сортировки методом «пузырька» массив последовательно просматривается несколько раз. Каждый просмотр состоит из сравнения каждого элемента массива a_i с элементом a_i+1 и обмена этих двух элементов, если они расположены не в нужном порядке.

Пример 1 . Пусть задан массив А, состоящий из элементов: А={25; 57; 48; 37; 12; 92; 86; 33}. Упорядочить его по возрастанию значений элементов.

Решение

На первом просмотре делаем следующие сравнения:

а₁ с а₂ (25 и 57) – нет обмена;

а₂ с а₃ (57 и 48) – обмен;

а₃ с а₄ (57 с 37) – обмен;

а₄ с а₅ (57 с 12) – обмен;

а₅ с а₆ (57 с 92) – нет обмена;

а₆ с а₇ (92 с 86) – обмен;

а₇ с а₈ (92 с 33) – обмен.

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

25 48 37 12 57 86 33 92.

После первого просмотра наибольший элемент 92 находится в нужной позиции. В общем случае элемент а_(n-i+1) будет находиться в нужной позиции после i-той итерации. Этот метод называется «методом пузырька» потому, что каждое число, словно пузырек, медленно всплывает вверх в нужную позицию.

После второго просмотра получим последовательность:

25 37 12 48 57 33 86 92. Элемент 86 на нужном месте.

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

1-ая итерация	25	48	37	12	57	86	33	92;
2-ая итерация	25	37	12	48	57	33	86	92;
3-ая итерация	25	12	37	48	33	57	86	92;
4-ая итерация	12	25	37	33	48	57	86	92;
5-ая итерация	12	25	33	37	48	57	86	92;
6-ая итерация	12	25	33	37	48	57	86	92;
7-ая итерация	12	25	33	37	48	57	86	92.

Метод улучшенной «пузырьковой» сортировки основан на методе «пузырька» с той лишь разницей, что количество итераций меньше. Рассмотрим его на примере.

Пример 2. Упорядочим по возрастанию методом «пузырька» массив А, представленный в примере 13.1, а также проиллюстрируем метод улучшенной «пузырьковой» сортировки на примере упорядочивания данного массива по убыванию.

Решение

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

Program Sort1;

Uses CRT;

Type Mas=Array[1..50] Of Integer;

Var A,B,C:Mas;

i,j,p,N:integer;

{Процедура вывода элементов массива}

Procedure Vyvod(M:Integer; Var V:Mas);

Begin

For i:=1 to M do

Write(V[i]:2,' ':2);

Writeln

End;

Begin

Writeln('Введите количество элементов массива А');

Readln(N);

Writeln('Введите массив А');

For i:=1 to N do

Readln(A[i])

Writeln('Исходный массив');

Vyvod(N,A);

{Сортировка массива по возрастанию методом «пузырька»}

C:=A;

For i:=1 to N do

For j:=1 to N-1 do

If C[j]>C[j+1] Then

Begin

P:=C[j];

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

C[j+1]:=P

End;

Writeln('Отсортированный по возрастанию массив А');

Vyvod(N,C);

{Сортировка массива по убыванию методом улучшенной «пузырьковой» сортировки. При использовании метода улучшенной «пузырьковой» сортировки i изменяется от 1 до n-1, j от 1 до n-i}

B:=A;

For i:=1 to N-1 do

For j:=1 to N-i do

If B[j]<B[j+1] Then

Begin

P:=B[j];

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

B[j+1]:=P

End;

Writeln('Отсортированный по убыванию массив А');

Vyvod(N,B);

Readln

End.

Сеанс работы с программой:

Введите количество элементов массива А

8

Введите массив А

25 57 48 37 12 92 86 33

Результаты:

Исходный массив А

25.0 57.0 48.0 37.0 12.0 92.0 86.0 33.0

Отсортированный по возрастанию массив А

12.0 25.0 33.0 37.0 48.0 57.0 86.0 92.0

Отсортированный по убыванию массив А

92.0 86.0 57.0 48.0 37.0 33.0 25.0 12.0

Метод быстрой сортировки является еще одной реализацией обменных сортировок. Пусть имеется массив А, состоящий из N элементов. Для обозначения индексов элементов воспользуемся двумя переменными – i и j. Полагаем i=1, j=n. Если a_i меньше a_j, то j уменьшаем на единицу и снова сравниваем a_i и a_j. После первой перестановки i увеличивается на единицу, и выполняется еще одна перестановка. Затем j уменьшаем на единицу. Процесс сравнения продолжается до тех пор, пока исходный набор не будет упорядочен по возрастанию.

Рассмотрим этот метод на примере сортировки строк.

Пример 3. Имеется список бригады рабочих из 10 человек. Упорядочить его по возрастанию методом быстрой сортировки и вывести на экран.

Решение

Обозначим через переменную w строку длиной не более 20 символов (фамилия рабочего), v – массив из 10 элементов (количество рабочих), p – вспомогательная переменная строкового типа для перестановки элементов, i и j – индексы строк в массиве. Программа на языке Паскаль представлена ниже.

Program Sort_String;

Uses Crt;

Type W=String[20];

V=Array[1..10] Of W;

Var Fio:V;

I,J:Integer;

P:W;

Begin

Clrscr;

Writeln('Ввод списка бригады');

For I:=1 To 10 Do

Begin

Write(i,' рабочий - ');

Readln(FIO[I])

End;

For I:=1 To 10 Do {Метод быстрой сортировки}

For J:=10 Downto 1 Do

If (FIO[I]>FIO[J]) And (I<=J) Then

Begin

P:=FIO[I];

FIO[I]:=FIO[J];

FIO[J]:=P;

End;

Writeln(‘Отсортированный список бригады’);

For I:=1 To 10 Do

Writeln(Fio[I]);

Readln

End.

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

Наиболее распространены следующие методы этого вида сортировки: с поиском минимального значения; с использованием бинарных деревьев; с использованием метода «турнира с выбыванием»; «пирамидальная» сортировка.

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

Пример 4. Отсортировать по возрастанию массив элементов 1 3 0 9 2.

Решение

Процесс сортировки выбором по методу поиска минимального значения пройдет через следующие шаги:

0:	1	3	0	9	2	min=a[3]=0	переставляем a[1] < -- > a[3]
1:	0│	3	1	9	2	min=a[3]=1	переставляем a[2] < -- > a[3]
2:	0	1│	3	9	2	min=a[5]=2	переставляем a[3] < -- > a[5]
3:	0	1	2│	9	3	min=a[5]=3	переставляем a[4] < -- > a[4]
4:	0	1	2	3	9	Готово

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

Program Sort2;

Uses Crt;

Var A: Array[1..50] Of Real;

I,J,N,K: Integer;

Min,W: Real;

{Процедура вывода элементов массива}

Procedure Vyvod(M:Integer; Var V:Mas);

Begin

For i:=1 to M do

Write(V[i]:2,' ':2);

Writeln

End;

Begin

Clrscr;

Writeln('Введите количество элементов массива А');

Readln(n);

Writeln('Введите массив А');

For i:=1 to n do

Read(a[i]);

Writeln;

Writeln('Исходный массив А');

Vyvod(N, A);

{Сортировка массива выбором}

For i:=1 to n do

Begin

min:=a[i]; k:=i;

For j:=i+1 to n do

If a[j]<=min then

Begin min:=a[j]; k:=j end;

{Перестановка i-го и min элементов}

w:=a[i];

a[i]:=a[k];

a[k]:=w;

End;

Writeln('Отсортированный массив А');

Vyvod(N, A);

readkey

End.

Сеанс работы с программой:

Введите количество элементов массива А

5

Введите массив А

1 3 0 9 2

Исходный массив А

1.0 3.0 0.0 9.0 2.0

Отсортированный массив А

0.0 1.0 2.0 3.0 9.0

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

Сортировка «вставками»

Наиболее распространены такие методы этого вида сортировки, как сортировка «простыми» вставками; сортировка «бинарными» вставками; сортировка Шелла; сортировка с вычислением адреса.

Суть сортировки «простыми» вставками заключается в последовательном переборе массива a₂, …, a_n с тем, чтобы каждый новый элемент a_i вставлять на подходящее место в уже упорядоченной совокупности a₁, …, a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами a₁, …, a_i-1.

При сортировке «бинарными» вставками место, на которое надо вставить элемент a_i в уже упорядоченную совокупность a₁, …, a_i-1, определяется алгоритмом деления пополам. Таким образом, получается алгоритм сортировки «бинарными» вставками, который понимается как «вставка делением пополам».

Пример 5. Вставить в упорядоченный по возрастанию массив А = {3; 4; 7; 9} новый элемент, равный 5, таким образом, чтобы сохранилась упорядоченность.

Решение

Алгоритм решения задачи следующий:

1. Найти в массиве элемент, больший вставляемого. Для этого следует просмотреть все элементы, начиная с первого. Это элемент а[3] = 7.

2. Увеличить длину массива на 1. Результат – массив А = {3 4 7 9 X}.

3. Все элементы, стоящие справа от найденного, включая его самого, то есть от 3-го, сдвинуть вправо. Результат – массив А = {3 4 7 7 9}.

4. На освободившуюся позицию, то есть на место элемента а[3], вставить новый элемент, то есть 5. В итоге получаем массив А = {3 4 5 7 9}.

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

Ниже приведена программа Sort3, реализующая данный алгоритм:

Program Sort3;

Uses CRT;

Var a: array[1..50] of real;

i,j,n,k: integer;

g:real;

{Процедура вывода элементов массива}

Procedure Vyvod(M:Integer; Var V:Mas);

Begin

For i:=1 to M do

Write(V[i]:2,' ':2);

Writeln

End;

Begin

Clrscr;

Writeln('Введите количество элементов массива А');

Readln(n);

Writeln('Введите массив А');

For i:=1 to n do

Read(a[i]);

Writeln;

Writeln('Введите число, которое нужно вставить');

Readln(g);

Writeln('Исходный массив А');

Vyvod(N, A);

{1. Ищем элемент больше вставляемого}

k:=1; {k - индекс сравниваемого элемента}

While (k<=n) and (g>=a[k]) do {если k не превышает n и вставляемый элемент меньше или равен a[k]}

k:=k+1;{то переходим к следующему элементу}

{2. Увеличиваем длину массива на 1}

n:=n+1;

{3.Сдвигаем элементы, начиная с k-го вправо}

For i:=n downto k+1 do

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

{4.В a[k] заносим g}

a[k]:=g;

Writeln('Новый массив А');

Vyvod(N, A);

readkey

End.

Сеанс работы с программой:

Введите количество элементов массива А

4

Введите массив А

3 4 7 9

Введите число, которое нужно вставить

5

Исходный массив А

3.0 4.0 7.0 9.0

Новый массив А

3.0 4.0 5.0 7.0 9.0

Сортировка «слияниями» (Алгоритм фон Неймана)

Суть заключается в упорядочении массива a₁, …, a_n по неубыванию. Метод основан на многократных слияниях уже упорядоченных групп элементов массива. Сначала весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждом. Слиянием соседних групп получаются упорядоченные группы, каждая из которых содержит два элемента (кроме последней группы, которой не нашлось парной). Далее полученные группы укрупняются тем же способом и т.д. Здесь приходится использовать вспомогательный массив b₁, …, b_n.