-
-
4.4.2 Сортировка массивов
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которой вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
Количество присваивания;
Количество сравнений;
Все методы сортировки можно разделить на две большие группы:
Прямые методы сортировки;
Улучшенные методы сортировки;
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три группы:
1) сортировка вставкой (включением)
2) сортировка выбором (выделением)
3) сортировка обменом (‘пузырьковая’ сортировка )
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива или особом расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы.
Сортировка вставкой
Принцип метода:
Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочерёдно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части – все остальные элементы.
Таким образом, алгоритм будет состоять из n-1-го прохода (n- размерность массива), каждый из которых будет включать четыре действия:
Взятие очередного i- го не отсортированного элемента и сохранение его в дополнительной переменной;
Поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
Сдвиг элементов массива от i- 1- го до j- 1- го вправо, чтобы освободить найденную позицию вставки;
Вставки взятого элемента в найденную j- ю позицию.
Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличатся способом поиска позиции вставки.
Рассмотрим схему реализации одного из возможных алгоритмов.
Схематично описанные действия одного прохода можно представить следующим образом
Схема сортировки методом вставки. Слева в кружке указан номер прохода
Программа, реализующая рассмотренный алгоритм, будет иметь следующий вид:
Демонстрация
Program InsertionSort;
Uses Crt;
Const
N= 20; {длина массива}
Type
Tvector= array [1..n] of real;
Var
Vector : Tvector;
B : Real;
I, j, k : integer;
Begin
ClrScr;
Writeln (‘Введите элементы массива:’);
For i:=1 to n do Read (Vector[i]); Readln;
{-----------------------------------------------------------------}
for i:= 2 to n do
begin
B:= Vector[i]; {Взятие не отсортированного элемента}
{Цикл поиска позиции всиавки}
j:= 1;
while (B> Vector[j]) do
j:= j+1; {После окончания цикла индекс j фиксирует позиции вставки}
{Цикл сдвига элементов для освобождения позиции вставки}
for k:= i-1 downto j do
Vector[k+1] := Vector [k];
{Вставка взятого элемента на найденную позицию }
Vector[j] := B;
End;
{--------------------------------------------------------------------------}
writeln(‘Отсортированный массив:’);
for i := 1 to n do write (Vector[i]:8:2);
writeln;
end.
Сортировка выбором
Принцип метода:
Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1- го элемента до n- го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2- го до n –го элемента и меняем местами со вторым элементом.
И так далее для всех элементов до n-1- го.
Рассмотрим схему алгоритма прямого выбора.
Программа, реализующая метод выбора, будет иметь следующий вид:
Демонстрация
Program SelectionSort;
Uses Crt;
Const
N= 20 ; {длина массива}
Type
Tvector = array [1..n] of real;
Var
Vector : Tvector;
Min : Real;
Imin, S : Integer;
I: Integer;
Begin
ClrScr;
Writeln (‘Введите элементы массива:’);
For i:= 1 to n do Read (Vector[i]); Readln;
{----------------------------------------------------------------------}
for S:=1 to n-1 do
begin
{Поиск минимального элемента в диапазоне}
{от S- го элемента до n- го}
min := vector[S];
Imin := S;
For i := S+1 to n do
If vector[i] < min then
Begin
Min:= vector[i];
Imin := i;
End;
{Обмен местами минимального и S –го элементов}
vector[imin] := vector[S];
vector[S] := Min;
end;
{--------------------------------------------------------------------------}
writeln(‘Отсортированный массив:’);
for i:= 1 to n do write (vector[i] :8:2);
writeln;
end.
Сортировка обменом (‘пузырьковая’ сортировка)
Принцип метода:
Слева направо поочерёдно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n- ой позиции массива будет стоять максимальный элемент(‘всплыл’ первый ‘пузырёк’). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1- го элемента. И так далее. Всего требуется n-1 проход.
Рассмотрим схему алгоритма сортировки методом прямого обмена по не убыванию.
Программа, реализующая метод обмена(‘пузырька’ ), будет иметь следующий вид:
Program BubleSort;
Uses Crt;
Const
N= 20; {Длина массива}
Type
Tvector = array [1..n] of real;
Var
Vector : Tvector ;
B : Real;
I, k: integer;
Begin
ClrScr;
Writeln {‘Введите элемент массива:’};
For i:= 1 to n do Read (Vector[i]); Readln;
{-------------------------------------------------------------}
for k:= n downto 2 do
{‘Всплывание ’ очередного максимального элемента на k- ю позицию }
for i:= 1 to k-1 do
if Vector[i] > Vector[i+1] then
begin
B:= Vector[i];
Vector[i+1] :=B
End;
{------------------------------------------------------------------}
writeln {‘Отсортированный массив:’};
for i:= 1 to n do write (Vector[i]:8 :2);
writeln;
end.
Сравнение прямых методов сортировки
Теоретическиеи практические исследования алгоритмов прямых методов сортировки показали, что как по числу присваивания они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.
Принцип двоичного поиска:
Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается . Если же средний элемент меньше искомого, т овсе элементы левее его также будет меньше искомого. Следовательно, их можно исключить из зоны дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остаётся левая.
На втором этапе выполняется аналогичные действия над оставшейся половине массива.
И так далее, пока элемент не будет найден, или длина зоны поиска станет равной нулю. В последнем случае искомый элемент найден не будет.
Рассмотрим схему алгоритма двоичного поиска.
Одно из возможных вариантов программы, реализующей метод двоичного поиска, имеет следующий вид:
Program BinSearch;
Uses Crt;
Const
N= 20; {Длина массива}
Type
Tvector = array [1..n] of real;
Var
Vector : Tvector; {Исходный массив}
X : Real; { Искомый элемент}
L, R: Integer; {Текущие границы зоны поиска}
I : Integer;
Begin
ClrScr;
Writeln {‘Введите элементы массива:’};
For i:= 1 to n do Read (Vector[i]); Readln;
Write(‘Введите искомый элемент:’);
Readln(x);
{---------------------------------------------------------------------}
L:= 1; R:= n;
While(L<=R) do (Покане пересекутся границы )
Begin
I:=(L+R) div 2;{Индекс среднего элемента}
If Vector[i] = X then
Break{Выход из цикла поиска т.к элемент найден}
Else
If Vector[i]< X thenL :=i+1
Else R:=i- 1;
End;{while}
If Vector[i]= X then
Writeln (‘Искомый элемент найден на позиции’, i:3)
Else
Writeln (‘Искомый элемент не найден’);
{-----------------------------------------------------------------------}
end.
-
-
4.4.3. Записи
Запись - это структура данных,
состоящая из фиксированного числа
компонентов, называемых полями
записи. В отличие от массива,
компоненты (поля) записи могут быть
различного типа. Чтобы можно было
ссылаться на тот или иной компонент
записи, поля именуются.
Структура объявления типа записи
такова:
<имя типа» - RECORD <сп.полей> END
Здесь <имя типа> - правильный
идентификатор;
RECORD, END - зарезервированные слова (запись,конец);
<сп.полей> - список полей;
представляет собой
последовательность разделов записи,
между которыми ставится точка с
запятой.
Каждый раздел записи состоит из
одного или нескольких
идентификаторов полей, отделяемых
друг от друга запятыми. За
идентификатором (идентификаторами)
ставится двоеточие и описание типа
поля (полей), например:
type
Birthday - record day,month : byte; year : word end; var
a,b : Birthday;
В этом примере тип BIRTHDAY (день
рождения) содержит три поля с именами
DAY, MONTH и YEAR (день, месяц и год);
переменные А и В содержат записи типа
BirthDay.
Как и в массиве, значения переменных
типа записи можно присваивать другим
переменным того же типа, например
а := b; К каждому из компонентов записи
можно получить доступ, если
использовать составное имя, т.е.
указать имя переменной, затем точное
имя поля:
a.day := 27;
b.year := 1939; Для вложенных полей
приходится продолжать уточнения:
var
с : record
name : string;
bd : Birthday
end;
if c.bd.year - 1939 then ...
Чтобы упростить доступ к полям
записи, используется опеатор
присоединения WITH:
WITH <переменная> DO <оператор>
Здесь WITH, DO - ключевые слова (с, делать);
<переменная> - имя переменной типа
запись, за которым, возможно следует
список вложенных полей;
<оператор> - любой оператор Турбо
Паскаля.
Например:
with c.bd do month := 9;
Это эквивалентно
with с do with bd do month := 9;
или
with c, bd do month := 9;
или
c.bd.month := 9;
Турбо Паскаль разрешает
использовать записи с так называем
вариантными полями, например:
type
forma = record
name : string;
case byte of
0 : (BirthPlace : string[40] );
1 : (country : string[20];
EntryPort : string[20];
EntryDate : 1..31;
ExitDate : 1..31)
end;
В этом примере тип FORMA определяет
запись с одним фиксированным полем NAME и вариантной частью,
которая задается предложением
CASE...OF. Вариантная часть состоит из
нескольких вариантов (в примере - из двух вариантов: 0 и 1). Каждый
вариант определяется конец
выбора, за которой следует двоеточие
и список полей, заключенный в
круглые скобки. В любой записи может
быть только одна вариантная
часть, и, если она есть, она должна
располагаться за всеми
фиксированными полями.
Замечательной особенностью
вариантной части является то обстоятельство, что все заданные в ней
варианты как бы "накладываются"
друг
на друга, т.е. каждому из них
выделяется одна и та же область
памяти. Это
открывает дополнительные
возможности преобразования типов,
например:
var
mem4:record
case byte of
0 : (by array [0..3] of byte);
1 : (wo array (0..1] of word);
2: (lo : longint);
end;
var
mem4:record
case byte of
0 : (by array [0..3] of byte);
1 : (wo array (0..1] of word);
2: (lo : longint); end;
В этом примере запись МЕМ4 имеет три
варианта, каждый из которых занимает
в памяти один и тот же участок из 4
байт. В зависимости от того, к какому
полю записи мы обращаемся в
программе, этот участок может
рассматриваться как массив из 4 байт (поле
ВУ), массив из двух целых типа WORD (поле
WO) или, наконец, как одно целое число
типа LONGINT (поле LO). Например, этой
записи можно сначала присвоить
значение как длинному целому, а затем
проанализировать результат по
байтам или словам:
var
x : word;
xb: byte;
хi: longInt;
with m do begin
lo := trunc(2*pi*x); If wo[1]=0 then
If by[1]=0 then xb := x[0] else x := wo[0] else xi := lo
end;
Предложение CASE...OF, открывающее
вариантную часть, внешне похоже на
соответствующий оператор выбора, но
на самом деле лишь играет роль
своеобразного служебного слова,
обозначающего начало вариантной
части. Именно поэтому в конце
вариантной части не следует ставить
END как пару к СA SE... OF. (Поскольку
вариантная часть - всегда последняя в
записи, за ней все же стоит END, но лишь
как пара к RECORD). Ключ выбора в
предложении CASE... OF фактически
игнорируется компилятором:
единственное требование,
предъявляемое к нему Турбо Паскалем,
состоит в том, чтобы ключ определял
некоторый стандартный или
предварительно объявленный
порядковый тип. Причем сам этот тип
никак не влияет ни на количество
следующих ниже вариантных полей, ни
даже на характер констант выбора. В
стандартном Паскале в качестве ключа
выбора необходимо указывать
некоторую переменную порядкового
типа, причем в исполняемой части
программы можно присваивать
значение этой переменной и таким
образом влиять на выбор лей. В Турбо
Паскале также можно в поле ключа
выбора указывать переменную
порядкового типа и даже присваивать
ей в программе значение, что однако
не влияет на выбор поля: значения
констант выбора в Турбо Паскале
могут быть произвольными, в том числе
повторяющимися,
например:
type
rec=record
a: byte;
b: word;
end;
rec2 = record
с : longint;
case x : byte of
1 : (d : word);
2 : (e : record
case Boolean of
3 :(f: reс1);
3 :(g: single);
'3':( с: word)
end)
end;
var
r : rec2;
BEGIN
r.x :=255:
if r.e..g=0 then wrIteln('O.K.')
else writeln(r.e.g)
END.
В этом примере предложение
case Boolean of
в записи, определяемой в поле Е,
объявляет ключом выбора логический
тип, который, как известно, имеет лишь
два значения - TRUE и FALSL Константы же
выбора следующих далее вариантов не
только содержат совершенно не
свойственные этому типу значения, но
и две из них повторяются, а общее
количество вариантов - три, а не два,
как следовало бы ожидать.
Имена полей должны быть уникальными
в пределах той записи, где они
объявлены, однако, если записи
содержат поля-записи, т.е. вложи. одна
в другую, имена могут повторяться на
разных уровнях вложенной (см. поле С в
последнем примере).
Вверх
-
-
-
4.4.4.
Множества
Множества - это наборы
однотипных логически связанных
друг с другом объектов. Характер
связей между объектами лишь
подразумевается программистом и
никак не контролируется Турбо
Паскалем. Количество элементов,
входящих в множество, может
меняться в пределах от 0 до 256 (множество,
не содержащее элементов,
называется пустыми. Именно
непостоянством количества своих
элементов множества отличаются
от массивов и записей.
Два множества считаются
эквивалентными тогда и только то
когда все их элементы одинаковы,
причем порядок следования
элемента в множестве
безразличен. Если все элементы
одного множества входят также и
в другое, говорят о включении
первого множества во второе
пустое множество включается в
любое другое.
Пример определения и задания
множеств:
Type
DigitChar= set of ‘0’..’9’;
Digit = set of 0..9;
Var
S1,s2,s3: digitChar;
S4,S5,S6:digit;
S1:=[‘1’,’2’,’3’];
S2:=[‘3’,’2’,’1’];
S3:=[‘2’,’3’];
S4:=[0..3,6];
S5:=[4,5];
S6:=[3..9];
В этом примере множества
SI и S2 эквивалентны, а множество S3
включено в 52 , но не эквивалентно
ему. Описание типа множества
имеет вид:
<имя типа> - SET OF <баз.тип>
Здесь <имя типа> - правильный
идентификатор;
SET, OF - зарезервированные слова (множество,
из);
<баз..тип> - базовый тип
элементов множества, в качестве
которого может использоваться
любой порядковый тип, кроме WORD,
INTEGER, WNGINT.
Для задания множества
используется так называемый
конструктор множества: список
спецификаций элементов
множества, отделяемых друг от
друга запятыми; список
обрамляется квадратными
скобками (см. предыдущий пример).
Спецификациями элементов могут
быть константы или выражения
базового типа, а также - тип-диапазон
того же базового типа.
Над множествами
определены следующие операции:
- - пересечение множеств;
результат содержит элементы,
общие для обоих множеств;
например, S4*S6 содержит [3], S4*S5 -
пустое множество (см. выше);
+ - объединение множеств;
результат содержит элементы
первого множества, дополненные
недостающими элементами из
второго множества:
S 4+S5 содержит [0, 1, 2, 3, 4, 5, 6];
S5=S6 содержит [3, 4, 5, 6, 7, 8, 9];
n разность множеств ; результат
содержит элементы из первого
множества, которые не
принадлежат второму:
S6-S5 содержит [3, 6, 7, 8, 9];
S4-S5содержит [0, 1, 2, 3, 6];
= - проверка эквивалентности;
возвращает TRUE, если оба
множества эквивалентны;
<> - проверка
неэквивалентности; возвращает
TRUE, если оба множества
неэквивалентны;
<= - проверка вхождения;
возвращает TRUE, если первое
множество включено во второе;
>= - проверка вхождения;
возвращает TRUE, если второе
множество помещено в первое;
In - проверка принадлежности; в
этой бинарной операции первый
элемент - выражение, а второй -
множество одного и того же типа;
возвращает TRUE, если выражение
имеет значение, принадлежащее
множеству:
3 in S6 возвращает True
2*2 in S1 возвращает False
- В примере 12,
иллистрирующем приёмы работы с
множествами, реализуется
алгоритм выделения из первой
сотни натуральных чисел всех
простых чисел. Алгоритм с
небольшими изменениями
заимствован из [3] . В его основе
лежит прием, известный под
названием «решето Эратосфена». В
соответствии с этим алгоритмом
вначале формируется множестве)
BEGINSET, состоящее из всех целых
чисел в диапазоне от 2 до N. ц
множество PRIMERSET (оно будет
содержать искомые простые числа)
помещается 1. Затем циклически
повторяются следующие действия:
. взять из BEGINSET первое входящее в
него число NEXT и
поместить его в PRIMERSET;}
• удалить из BEGINSET число NEXT и все
другие числа, кратные
ему, т.е. 2*NEXT, 3*NEXT и т.д.
Цикл повторяется до тех
пор, пока множество BEGINSET не
станет пустым.
Эту программу нельзя
использовать для произвольного N,
так как в
любом множестве не может быть
больше 256 элементов.
Пример 12.
{Выделение всех простых чисел из
первых N целых}
Const
N=100 ; {Количество элементов
исходного множеств}
Type
SetOfNumber= Set of 1…N;
Var
N1,next, i: Word; {Вспомогательные
переменные}
BeginSet, {Исходное множество}
PrimerSet ; SetOfNumber; {Множество
простых чисел}
Begin
BeginSet:=[2..N]; {Создать исходное
множество }
PrimerSet:=[1]; {Первое простое
число}
Next :=2; {Следующее простое
число}
While BeginSet <> [] do {Начало
основного цикла}
Begin
N1:= next; {N1-число, кратное
очередному простому(next)}
While N1<=N do {Цикл
увеличения из исходного
множества из непростых чисел:}
Begin
BeginSet :=BeginSet-[N1];
N1:=N1+next; {Следующее
кратное}
End {Конец цикла
удаления}
PrimerSet:= PrimerSet+[Next];
Repeat {Получить
следующее простое, которое есть
первое не вычеркнутое из
исходного множества}
Inc(Next);
Until (Next in BeginSet) or (next<N);
End; {Конец основного цикла}
{Вывод результата }
for i:= 1 to N do
If i in PrimerSet then write (i:8);
Writeln;
End.
