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

 

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

Пример 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-ая итерация								92;
2-ая итерация								92;
3-ая итерация								92;
4-ая итерация								92;
5-ая итерация								92;
6-ая итерация								92;
7-ая итерация								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.

 

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

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

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

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

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

 

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.

 

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

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

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

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 элементами и т.д., пока не останется один, самый малый по значению элемент.