Описание переменных размерностей

Массивы

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

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

type имя_типа = array [тип_индекса] of тип_элемента

Здесь array и of — ключевые слова, тип индекса задается в квадратных скобках. Примеры описания типа:

type mas = array [1.. 10] of real;

Color = array [byte] of mas;

Active = array [Menu] of boolean;

В первом операторе описан тип массива из вещественных элементов, которые нумеруются от 1 до 10. Во втором операторе элементами массива являются массивы типа mas, а нумеруются они в пределах, допустимых для типа byte, то есть от 0 до 255. В третьей строке в качестве индекса использовано имя типа из раздела 'Перечисляемый тип данных', а сами элементы могут принимать значения true или false.

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

ВНИМАНИЕ Размещение массива в памяти происходит до выполнения программы, поэтому при описании индекса можно применять только константы или константные выражения.

Обычно при описании массива верхняя граница его индекса задается в виде именованной константы, например:

const n = 6;

type intmas = array [1.. n] of integer;

После задания типа массива переменные этого типа описываются обычным образом:

var a, b: intmas;

С массивами в целом можно выполнять только одну операцию: присваивание. При этом массивы должны быть одного типа:

b:= a;

Все остальные действия выполняются с отдельными элементами массива. Для обращения к элементу массива после имени массива указывается номер элемента в квадратных скобках:

a[4] b[i]

С элементом массива можно делать все, что допустимо для переменных того же типа.

При обращении к элементу массива автоматический контроль выхода индекса за границу массива не производится. Для включения режима автоматического контроля необходимо добавить в любое место программы, предшествующее обращениям к элементу, ключ компиляции {$R+} или установить соответствующий режим в оболочке.

Инициализация массивов. Элементам массива можно присвоить значения до начала выполнения программы. Это делается так же, как и для простых переменных, — в разделе описания констант, например:

const a: intmas = (0, 5, –7, 100, 15, 1);

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

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

Сформулируем алгоритм поиска максимума.

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

2. Просмотреть массив, начиная со второго элемента.

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

Программа приведена в пример 3.1.

program max_elem;

const n = 20;

var a: array [1.. n] of real;

i: integer;

max: real;

begin

writeln('Введите ', n, ' элементов массива');

for i:= 1 to n do read(a[i]);

max:= a[1]; { принять за максимальный первый элемент массива }

for i:= 2 to n do { просмотреть массив, начиная со второго элемента }

if a[i] > max then max:= a[i]; { при необходимости обновить максимум }

writeln('Максимальный элемент: ', max:6:2)

end.

Листинг 3.1. Максимальный элемент массива из 20 вещественных элементов

Еще один простой пример работы с массивом приведен в пример 3.2.

program sum_num;

const n = 10;

var a: array [1.. n] of integer;

i, sum, num: integer;

begin

writeln('Введите ', n, ' элементов массива');

for i:= 1 to n do read(a[i]);

sum:= 0;

num:= 0;

for i:= 1 to n do begin

sum:= sum + a[i];

if a[i] < 0 then inc(num);

end;

writeln('Сумма элементов: ', sum);

writeln('Отрицательных элементов: ', num);

end.

Листинг 3.2. Сумма и количество отрицательных элементов целочисленного массива

 

Массивы

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

Описание массива

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

Общий вид описания (одномерного) массива:

array[<тип_индексов> ]³ of <тип_компонент>;

Чаще всего это трактуется так:

array[<левая_граница>..<правая_граница>] of <тип_компонент>;

Например, одномерный (линейный) массив, состоящий не более чем из 10 целых чисел, можно описать следующим образом:

var a1: array [1..10] of integer;

Нумерация

Нумерация компонент массива не обязана начинаться с 1 или с 0 - вы можете описывать массив, пронумерованный любыми целыми числами. Необходимо лишь, чтобы номер последней компоненты был больше, чем номер первой:

var a1: array [-5..4] of integer;

Собственно говоря, нумеровать компоненты массива можно не только целыми числами. Любой порядковый тип данных (перечислимый, интервальный, символьный, логический, а также произвольный тип, созданный на их основе) имеет право выступать в роли нумератора. Таким образом, допустимы следующие описания массивов:

type char = 'a','c'..'z'; (- отсутствует символ "b")

var a1: array[char] of integer; - 256 компонент

a2: array [char] of integer; - 256 целых компонент

a3: array [shortint] of real; - 256 вещественных компонент

Общий размер массива не должен превосходить 65 520 байт. Следовательно, попытка задать массив a4:array[integer]of byte; не увенчается успехом, поскольку тип integer покрывает 65 535 различных элементов. А про тип longint в данном случае лучше и вовсе не вспоминать.

Тип компонент массива может быть любым:

var a4: array[10..20] of real; - массив из компонент простого типа

a5: array[0..100] of record1; - массив из записей⁴

a6: array[-10..10] of ^string; - массив из указателей⁵ на строки

a7: array[-1..1] of file; - массив из имен файловых переменных⁶

a8: array[1..100] of array[1..100] of char; - двумерный массив (массив векторов)

Для краткости и удобства многомерные массивы можно описывать и более простым способом:

var a9: array[1..10,1..20] of real; - двумерный массив 10 х 20

a10: array[boolean, -1..1,char, -10..10] of word; - четырехмерный массив 2 х 3 х 256 х 21

Общее ограничение на размер массива - не более 65 520 байт - сохраняется и для многомерных массивов. Количество компонент многомерного массива вычисляется как произведение всех его "измерений". Таким образом, в массиве а9 содержится 200 компонент, а в массиве а10 - 32 256 компонент.

Описание переменных размерностей

Если ваша программа должна обрабатывать матрицы⁷ переменных размерностей (скажем, N по горизонтали и М по вертикали), то вы столкнетесь с проблемой изначального задания массива, ведь в разделе var не допускается использование переменных. Следовательно, самый логичный, казалось бы, вариант

var m,n: integer; a: array[1..m,1..n] of real;

придется отбросить.

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

Предположим, однако, что вам известны максимальные границы, в которые могут попасть индексы обрабатываемого массива. Скажем, N и М заведомо не могут превосходить 100. Тогда можно выделить место под наибольший возможный массив, а реально работать только с малой его частью:

const nnn=100;var a: array[1..nnn,1..nnn] of real; m,n: integer;

Задание массива константой

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

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

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

Исключение составляют только массивы, компонентами которых являются величины типа char. Такие массивы можно задавать проще: строкой¹⁰ символов.

Примеры задания массивов типизированными константами:

type mass = array[1..3,1..2] of byte;

const a: array[-1..1] of byte = (0,0,0); {линейный}

b: mass = ((1,2),(3,4),(5,6)); {двумерный}

s: array[0..9] of char = '0123456789';

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

Задача сортировки

Эта лекция посвящена сугубо алгоритмической проблеме упорядочения данных.

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

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

Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами)¹.

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

Простые сортировки

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N² действий, где С - некоторая константа.

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

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием "пропорционально", которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают "в среднем": как среднее арифметическое от сложности алгоритма "в лучшем случае" и "в худшем случае", то есть (Eff_best + Eff_worst)/2.

Алгоритм ПрВст

1. Первый элемент записать "не раздумывая".

2. Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:

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

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

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

Реализация алгоритма ПрВст

for i:= 2 to N do if a[i-1]>a[i] then {*} 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;

Пример сортировки

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

5 3 4 3 6 2 1

Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

Состояние массива Сдвиги Сравнения Пересылки данных0 шаг: 5343621 1 шаг: 5343621 1 1+ 1³ 1+ 2⁴ 2 шаг: 3543621 1 1+1 1+23 шаг: 3453621 2 2+1 2+24 шаг: 3345621 0 1 05 шаг: 3345621 5 5+1 5+26 шаг: 2334561 6 6+1 6+2Результат: 1233456 15 20 25

Реализация алгоритма БинВст

for i:= 2 to n do if a[i-1]>a[i] then begin x:= a[i]; left:= 1; right:= n-1; repeat sred:= (left+right) div 2; if a[sred]<x then left:= sred+1 else right:= sred-1; until left>right; for j:= i-1 downto left do a[j+1]:= a[j]; a[left]:= x; end;

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

Попробуем теперь сократить количество пересылок элементов.

Алгоритм ПрВыб

На каждом шаге (всего их будет ровно N-1) будем производить такие действия:

1. найдем минимум среди всех еще не упорядоченных элементов;

2. поменяем его местами с первым "по очереди" не отсортированным элементом. Мы надеемся, что читателям очевидно, почему к концу работы этого алгоритма последний (N-й) элемент массива автоматически окажется максимальным.

Реализация ПрВыб

for i:= 1 to n-1 do begin min_ind:= i; for j:= i+1 to n do if a[j]<=a[min_ind] {***} then min_ind:= j; if min_ind<>i then begin x:= a[i]; a[i]:= a[min_ind]; a[min_ind]:= x; end; end;

Пример сортировки

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

5 3 4 3 6 2 1

Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а квадратиком выделен ее минимальный элемент):

1 шаг: 53436212 шаг: 1343625 3 шаг: 1243635 {***}⁶ 4 шаг: 1233645{ничего не делаем}5 шаг: 12336456 шаг: 1233465результат: 1233456

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность ~N², к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным только при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.

Сортировка Шелла

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

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

1. вычленить все подпоследовательности, расстояние между элементами которых составляет k_t;

2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний k_t, k_t-1..., k₁ составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить ее обязательные свойства:

· k₁ = 1;

· для всех t k_t > k_t-1;

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

Дональд Кнут предлагает две "хорошие" последовательности расстояний:

1, 4, 13, 40, 121, _ (k_t = 1+3*k_t-1)1, 3, 7, 15, 31, _ (k_t = 1+2*k_t-1 = 2^t -1)

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для k_t)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т.д. между ее элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления k_t = 2^t-1.

Итак, длина нашего массива (N) должна попадать в такие границы:

k_t <= N -1 < k_t+1

или, что то же самое,

2^t <= N < 2^t+1

Прологарифмируем эти неравенства (по основанию 2):

t <= log N < t+1

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

t = trunc(log N))

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придется вспомнить знакомое из курса средней школы правило "превращения" логарифмов:

log_mx =log_zx/log_zm

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

t:= trunc(ln(N)/ln(2)).

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть - и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:

t:= trunc(ln(N)/ln(2))-1

Расстояние между элементами в любой подпоследовательности вычисляется так:

k:= (1 shl t)-1; {k= 2^t-1}

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

s:= N div k;

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких "удлиненных" подпоследовательностей совпадает с длиной "хвоста" - остатка от деления N на шаг k:

P:= N mod k;

Реализация алгоритма УлШелл

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

program shell_sort;const n=18; a:array[1..n] of integer =(18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1);var ii,m,x,s,p,t,k,r,i,j: integer;begin t:= trunc(ln(n)/ln(2)); repeat t:= t-1; k:= (1 shl t)-1; p:= n mod k; s:= n div k; if p=0 then p:= k else s:= s+1; writeln(k,'-сортировка'); for i:= 1 to k do {берем и длинные, и короткие подпоследовательности} begin if i= p+1 then s:= s-1; (для коротких - уменьшаем длину} for j:= 1 to s-1 do {метод ПрВст с шагом k} if a[i+(j-1)*k]>a[i+j*k] then begin x:= a[i+j*k]; m:= i+(j-1)*k; while (m>0) and (a[m]>x) do begin a[m+k]:= a[m]; m:= m-k; end; a[m+k]:= x; end; for ii:= 1 to n do write(a[ii],' '); writeln; end; until k=1;end.

Результат работы

Сортировки

4 17 16 15 14 13 12 11 10 9 8 7 6 5 18 3 2 1 4 3 16 15 14 13 12 11 10 9 8 7 6 5 18 17 2 1 4 3 2 15 14 13 12 11 10 9 8 7 6 5 18 17 16 1 4 3 2 1 14 13 12 11 10 9 8 7 6 5 18 17 16 15 4 3 2 1 7 13 12 11 10 9 8 14 6 5 18 17 16 15 4 3 2 1 7 6 12 11 10 9 8 14 13 5 18 17 16 15 4 3 2 1 7 6 5 11 10 9 8 14 13 12 18 17 16 15

Сортировки

1 3 2 4 7 6 5 11 10 9 8 14 13 12 18 17 16 15 1 3 2 4 7 6 5 8 10 9 11 14 13 12 18 17 16 15 1 3 2 4 7 6 5 8 10 9 11 14 13 12 15 17 16 18

Сортировка

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.

Просеивание

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах¹¹ последовательно задерживаются сначала крупные, а затем все более мелкие частицы.

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

a[1]
a[2]	a[3]
a[4]	a[5]	a[6]	a[7]
a[8]	a[9]	a[10]	a[11]	a[12]

Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].

При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:

for i:= (N div 2)downto 1 do begin j:= i; while j<=(N div 2) do begin k:= 2*j; if (k+1<=N) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Пример результата просеивания

Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).

Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):

	10 9
		9 10

 

11 4
4 11

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:

	12 5
			5 12
11 7
7 11

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1
	1 12
7 1
	8 1
		1 8

 

		6 1
				1 6

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

Алгоритм УлПир

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

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

· поменять местами очередной "рабочий" элемент с первым;

· просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Реализация алгоритма УлПир

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

for i:= N downto 2 do begin x:= a[1]; a[1]:= a[i]; a[i]:= x; j:= 1; while j<=((i-1)div 2) do begin k:= 2*j; if (k+1<=i-1) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12,11,8,7,10,6,5,4,2,9,3,1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:

1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12];2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12];3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12];4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12];5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12];6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12];7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12];8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12];9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12];10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12];11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12];12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12];13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12];14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12];15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12];16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12];17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12];18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12];19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12];20) Просеивать уже ничего не нужно;21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12];22) Просеивать ничего не нужно, сортировка закончена.

Быстрая сортировка

Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка¹². Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

 

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

Сортировку данным методом рассмотрим на примере. Дан массив (табл.), элементы которого необходимо отсортировать в порядке возрастания:

Рис. 4.1. Сортировка 'Пузырьком'

Программная реализация на Бейсике	Программная реализация на Паскале
... for j=n to 2 step -1 for i=1 to j-1 if a(i)>a(i+1) then swap a(i), a(i+1)next i, j…	... for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end;...

Краткие итоги

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

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

Набор для практики

Вопросы.

· Что происходит за один проход массива при сортировке "Пузырьком"?

· Объясните зависимость счетчика внутреннего цикла от счетчика внешнего цикла в типовом алгоритме сортировки одномерного массива "Пузырьком".

Упражнения.

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

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

· Найдите в тексте все гласные буквы и расположите их в порядке возрастания номеров алфавита, а все согласные буквы - в порядке убывания номеров алфавита.

· Ввести предложение. Измените порядок слов в предложении, расположив в алфавитном порядке (по первой букве каждого слова).

Задачи, сгруппированные по методам решения. Использование дополнительного массива "флажков"

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

Если условий несколько, то "флажки" принимают разное значение (например: "1" и "-1" и др.). Рассмотрим данный прием на практике.

Задача 1: Написать программу для поиска всех простых чисел (до числа N).

Дополнительные сведения: Рассмотрим алгоритм поиска простых чисел на диапазоне от 1 до N методом " Решето Эратосфена ". Проиллюстрируем этот метод:

· 1 шаг: берем "2", отмечаем серым цветом. Вычеркиваем все числа, кратные двум.

· 2 шаг: берем следующее за "2" невычеркнутое число ("3"), отмечаем серым цветом. Вычеркиваем все числа, кратные трем и т.д.

· В "решете" остались числа, отмеченные серым цветом. Это простые числа.

Рис. 6.1.

Идея решения:

· Заполняем одномерный массив А подряд идущими числами до N (например: N=22) включительно (таблица ниже):

· Заполняем элементы массива Flag флажками-единицами, если соответствующие элементы массива А кратны "2" (рис. 6.2):

Рис. 6.2.

· Затем заполняем элементы массива Flag флажками-единицами, если соответствующие элементы массива А кратны "3" (рис. 6.3):

Рис. 6.3.

· и т.д.

· В "решете" (массиве А) остались числа, отмеченные серым цветом (рис. 6.4):

Рис. 6.4.

Для сокращения количества шагов достаточно перебирать элементы массива А до половины (т.к. максимальный делитель n - этоn/2).

Решение задачи на Бейсике:

input "n="; n

dim a(n), flag(n)

for i=1 to n

a(i)=i

next

for i = 2 to n/2

if flag(i)=0 then

for j=i+1 to n

if a(j) mod a(i)=0 then flag(j)=1

next j

end if

next i

for i=1 to n

if flag(i)=0 then print a(i);

next

Решение задачи на Паскале:

Program pr;

Var a,flag:array [1..100] of integer;

I,j,n:integer;

begin

writeln ('n=');

readln (n);

for i:=1 to n do

a[i]:=i;

for i:=2 to n div 2 do

if flag[i]=0 then

for j:=i+1 to n do

if (a[j] mod a[i]=0) then flag[j]:=1;

for i:=1 to n do

if flag[i]=0 then writeln (a[i]);

end.

Тест:

Дано:
Результат:	1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 97

Задача 2: В одномерном массиве, заполненном целыми числами подсчитать число различных элементов.

Идея решения: сравнивая очередной элемент массива А с остальными элементами, заполняем единицей соответствующий повторяющемуся элементу элемент массива Flag. Количество нулевых элементов в массиве Flag и будет равно количеству различных элементов массива А.

Решение задачи На Бейсике:

input "количество чисел"; n

dim a(n), flag(n)

for i = 1 to n

input "введите число"; a(i)

next

for i = 1 to n - 1

if flag(i) = 0 then

for j = i + 1 to n

if a(i)=a(j) then flag(j)=1

next

end if

next

for i = 1 to n

if flag(i)=0 then k = k+1

next

print "k="; k

Решение задачи на Паскале:

Program pr;

var a,flag: array [1..100] of integer;

i,j,n,k: integer;

begin

writeln ('количество чисел');

readln (n);

for i:= 1 to n do

begin

writeln ('введите число');

readln (a[i]);

end;

{==========================}

for i:=1 to n-1 do

if flag[i]=0 then

for j:=i+1 to n do

if a[i]=a[j] then flag[j]:=1;

for i:=1 to n do

if flag[i]=0 then k:=k+1;

writeln ('k=', k);

end.

Тест:

Дано:	n=10 1, 4, 2, 2, 3, 1, 2, 3, 4, 1
Результат:	k=4

Задача 3: Вывести элемент, встречающийся в одномерном массиве чаще других.

Идея решения: При сравнении элементов массива А находим повторяющиеся элементы. Массив Flag заполняем количеством повторений элемента массива А. Затем, применив типовой алгоритм ПОИСКА МАКСИМАЛЬНОГО ЭЛЕМЕТА МАССИВА находим позицию элемента массива А, встречающегося чаще других.

Решение задачи на Бейсике:

input "количество чисел";n

dim a(n), flag(n)

for i = 1 to n

input "введите число"; a(i)

next

for i = 1 to n - 1

if flag(i) = 0 then

for j = i + 1 to n

if a(i) = a(j) then k = k + 1: flag(j) = k

next

k = 0

end if

next

for i = 1 to n

if flag(i) > max then max = flag(i): b = i

next

print "чаще встречается "; a(b);

Решение задачи на Паскале:

var a,flag: array [1..100] of integer;

i,j,n,k,max,b: integer;

begin

writeln ('количество чисел');

readln (n);

for i:= 1 to n do

begin

writeln ('введите число');

readln (a[i]);

end;

{===================}

k:=0;

for i:=1 to n-1 do

if flag[i]= 0 then

for j:=i+1 to n do

begin

if a[i]= a[j] then

begin

k:= k+1;

flag[j]:=k;

end;

k:=0;

end;

max:=flag[1];

for i:=1 to n do

if flag[i]>max then

begin

max:=flag[i];

b:=i;

end;

writeln ('чаще встречается ', a[b]);

end.

Тест:

Дано:	n=10 1, 4, 2, 2, 3, 1, 2, 3, 2, 1
Результат:	Чаще встречается 2

Ключевые термины

· Метод " Решето Эратосфена " - алгоритм поиска простых чисел на диапазоне от 1 до N.

Краткие итоги

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

В алгоритме " Решето Эратосфена " флажками отмечаются элементы, которые необходимо исключить из дальнейшего рассмотрения ("вычеркнуть").

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

Набор для практики

Вопросы.

· Продолжите фразу: "Для того, чтобы отметить элементы, удовлетворяющие условию, используют…".

· В чем заключается алгоритм поиска простых чисел на диапазоне от 1 до N методом " Решето Эратосфена "?

Упражнения.