Алгоритмы сортировки массивов

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

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

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

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

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю оперно для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

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

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

Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Метод Хoopа

Этот метод, называемый также быстрой сортировкой (QuickSort), был разработан в 1962 г. (его разработал Charles Antony Richard Hoare). Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.

Многомерные массивы

До сих пор мы рассматривали массивы, каждый элемент которых содержал один индекс. Такие массивы называют одномерными.

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

Описание матрицы 3 х 4:

1) Type T = Array [1..3,1..4] of Integer;

Var A:T;

2) Type T = Array [1..3] of Array [1..4] of Integer;

Var A:T;

Пример:

Type T1 = Array [1..4] of Integer;

T = Array [1..3] of T1;

Var A:T;

B: T1;

Здесь сначала описывается тип одной строки Т1, а затем, через тип строки Т1, описывается тип всей матрицы Т. В разделе переменных указывается, что А является двумерным массивом (т.е. матрицей), а В – одномерным массивом.

Пример: Найти сумму положительных элементов массива D(n,m)

n£10, m£20.

Program Summa;

Const n=10;

     m=20;

Var i, j:Integer;

     Sum: Real;

     D: Array [1..n,1..m] of Real;

Begin

     Sum: = 0;

     For i: = 1 to n do

              For j: = 1 to m do

              Begin

                        Read (D[i,j]);

                        If D[i,j] > 0 then Sum: = Sum + D[i,j];

              End;

     Writeln (‘Sum=’,Sum);

End.

Пример: Даны две матрицы: A[N*M], B[N*M].

Найти их сумму C[N*M]= A + B.

C_ij = a_ij + b_ij

Program Summa;

Const N=3; (*количество строк*)

     M=5; (*количество столбцов*)

Type Mat = Array [1..N,1..M] of Real;

Var A, B, C: Mat;

     I: Integer; (*индекс строки*)

     J: Integer; (*индекс столбца*)

Begin

     Writeln (‘Ввести А, В’);

     For I: = 1 to N do

     Begin

              For J: = 1 to M do

              Begin

                        Read (A[I,J],B[I,J]);

                        C[I,J]:= A[I,J] + B[I,J];

              End;

              Readln;

     End;

     Writeln (‘Матрица С’);

     For I: = 1 to N do

     Begin

              For J: = 1 to M do

                        Write (C[I,J]:3:1, ‘ ‘:2);

              Writeln;

     End;

End.

Упакованные массивы

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

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

Например, массивы А и АР описаны как

Var AP: Packed Array [1..3] of Boolean;

A: Array [1..3] of Boolean;

Обычнвй м упакованный массивы идентичны в смысле объема и характера хранимой информации, но различаются способами представления в памяти ЭВМ.

Упакованный массив можно описывать в разделе переменных или с использованием раздела типов.

Описание в разделе типов:

Type имя типа = Packed Array [имя индекса] of тип элемента;

Var имя переменной:имя типа;

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

К упакованным символьным массивам в языке программирования Паскаль относится строки символов, которые задаются либо в разделе операторов, либо в разделе констант (строки символов, а не символьные строки String, о которых речь пойдет дальше). Как известно, тип константы однозначно определяется ее записью. Поэтому если, например, в разделе констант определена константа S=’end’, то она принадлежит к типу: Packed Array [1..3] of Char.

Считается, что символьные константы имеют тип упакованных массивов:

Packed Array [1..n] of Char;

где n - длина строки.

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

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

Type Mas= Packed Array [1..7] of Char;

Var A:Mas;

Тогда, можно записать такой оператор:

A:=’ZADACHA’;

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

Пример: ‘String’ < ’Strong’, т.к. в алфавите символ ‘i’ стоит раньше, чем ’o’ и его код меньше, т.е. ’i’<’o’.

Пусть, например, имеется строка: “ABCDEFG”. Эту строку можно считать массивом символов, состоящим из 8 символов, включая пробел. Если этот массив символов обозначить именем Sim, то описание примет вид:

Type T = Packed Array [1..8] of Char;

Var Sim:T;

Один элемент массива принимает значение одного символа, например:

Sim[1]=’A’;

Sim[6]=’ ’.

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

Пример: ввода.

1) I: = 1;

While I<=10 do Begin   Read (A[I]); I:= I+1; End;

2) For I:= 1 to 46 do Read (A[I]);

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

Пример: Дана строка символов, обозначенная именем S1.

‘To be or not to be’

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

Program Hamlet;

Type Stroka = Packed Array [1..20] of Char;

Var S1, S2: Stroka;

     I: Integer; (*счетчик символов*)

     K: Integer; (*параметр цикла*)

Begin

     Write (‘Ввести S1=’);

     I; = 0;

     While I <= 18 do

     Begin

              I:= I+1;

              Raed (S1[I]); Readln;

     End;

     S2:= S1;

     S2[I+1]:= ‘?’;

     For K:= 1 to I+1 do Write (S2[K]);

End.

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

Пример: Даны два символьных массива: А₁= ‘Suvorov’ и А₂= ‘Suhanov’. Требуется поменять их местами.

Program Zamena;

Const N =12;

Type Mas = Array [1..N] of Char;

Var A1,A2,X: Mas;

Begin

Writeln (‘A1-Who?’);

Readln (A1); {Суворов}

Writeln (‘A2-Who?’);

Readln (A1); {Суханов}

Writeln (‘происходит замена’);

X:=A1;

A1:=A2;

A2:=X;

Writeln (‘A1=’,A1);

Writeln (‘A2=’,A2);

End.

Обратите внимание, что для ввода и вывода символьных массивов здесь не применяется цикл!

Строки

Тип String (строка) в Паскале широко используется для обработки текстов и во многом похож на одномерный массив символов Array [0..N] of Char. Однако в отличие от массива количество символов в строке – переменной может меняться от 0 до N, где N – максимальное количество символов в строке. Значение N определяется в разделе объявления типа String [N] и может быть любой константой порядкового типа, но не больше 255: N£ 255. Можно не указывать N, в этом случае длина строки принимается максимально возможной: N = 255.

Строка трактуется как цепочка символов. К любому символу в строке можно обратится точно так же, как к элементу одномерного массива Array [0..N] of Char.

Пример:

Var st: String;

- - - - - - - - - - - - - -

if st[5]= ‘A’ then …….

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

Пример:

Var st:String[10];

I:Integer;

- - - - - - - - - - - - - -

st[0]:=5;

Значение Ord (st[0]), то есть текущую длину строки можно получить с помощью функции length (st).

К строке можно применить операцию + (сцепление строк), например:

St:=’a’+’b’;{® ab}

St:=st+’c’; {® abc}

Если длина сцепленной строки превысит максимально допустимую длину N, то «лишние» символы отбрасываются.

Пример:

Var st :String [1];

Begin st:=’123’;

              Writeln(st); {® 1}

End;

Кроме сцепления строк, все остальные действия над строками (и символами) реализуются с помощью встроенных функций.

1) Concat (S1<, S2, S3,…SN>)– функция типа String, сцепление строк;

2) Copy (имя строки,№ нач. символа, кол-во символов)– функция копирования;

3) Delete (имя строки,№ нач. символа, кол-во символов)– функция удаления;

4) Insert (имя подстроки, имя строки, № нач. символа в строке)– вставка;

5) Length (имя строки)– функция типа Integer, вычисляет длину строки;

6) Pos (имя подстроки, имя строки)- функция типа Integer, отыскивает в строке первое вхождение подстроки и дает № позиции, с которой она начинается; если подстрока не найдена, значение функции будет = 0;

7) Str (число Real или Integer <: общая ширина поля<: кол-во симв. в дроб. части>>, имя строки) – процедура, преобразующая число типа Real или Integer в строку символов так, как это делает процедура Writeln перед вызовом; параметры, если они присутствуют, задают формат преобразования;

8) Val (имя строки, число Real или Integer, параметр) – процедура, преобразующая строку символов во внутреннее представление целое или вещественное числа; параметр = 0, если преобразование проведено успешно, в противном случае он содержит № позиции в строке, где обнаружен ошибочный символ;

9) Upcase (символ) – функция типа Char, возвращает символ в верхнем регистре, если он определен для него, либо сам символ, если для него нет верхнего регистра.

Пример: Upcase(‘a’) даст A,

Upcase(‘2’) даст 2.

Пример:

Var

x: Real;

y: Integer;

     st, st1: String;

- - - - - - - - - - - - - - - - -

st:= concat (‘12’,’345’); (*получится st ® 12345*)

st1:= copy (st, 3, lenght(st)-2); (*получится st1 ® 345*)

insert(‘-’,st1,2); (*получится st1 ® 3-45*)

delete(st, pos(‘2’,st),3); (*получится st ® 15*)

str(pi:6:2,st); (*получится st ® 3.14*)

st1:=’3.1415’; (*получится st1 ® 3.1415*)

val(st1,x,y); (*получится y=2, x – какой был*)

     Операции отношения

     = <> > < >= <=

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

Пример: Операции дают значение true:

‘turbo’<’turbo-pascal’;

‘A’<>’IFF’;

‘ПАскаль’<’Паскаль’;

МНОЖЕСТВЕННЫЕ ТИПЫ

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

Множеством называется совокупность объектов, обладающих некоторым общим свойством.

Множества могут состоять из любого числа объектов (элементов), но могут и не содержать элементов.

В математике под множеством понимается некоторый набор элементов. Например, множество плоских геометрических фигур:

[круг, ромб, квадрат, треугольник, прямоугольник].

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

Пример. [круг, ромб, круг] – неверная запись множества.

[круг, ромб, квадрат]=[ромб, круг, квадрат] – одинаковы и равны между собой.

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

Элементы множества заключаются в […].

Множество может не содержать ни одного элемента. В этом случае оно называется пустым [ ].

Если множества используются в программе, то они должны быть описаны либо с помощью раздела Type, либо непосредственно в разделе переменных.

Type имя_типа = set of t;

­ базовый тип элементов множества (любой простой кроме real и integer)

Var имя_множества: имя_типа;

Дело вот в чём. Размерность множества, то есть допустимое количество элементов множества обычно небольшое. Для большинства компьютеров оно не превышает 256 (то есть от 0 до 255). Поэтому объявление

Set of Integer         является недопустимым.

Вместе с тем запись  Type M = Set of Boolean является корректной, поскольку объявляется множество, содержащее два элемента со значениями True и False.

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

Byte,

Char,

перечислимые типы,

ограниченные типы.

Пример. Type Letters = Set of ‘A’..’Z’;

                Holidays = Set of 1..31;

                U = Set of Char;

                I = Set of Byte;

Пример. Type M = Set of (A, B, C, D);

       Var G, F: M;

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

G := [A, B, D];

F := [C, A, B];

Приведём примеры описания множеств непосредственно в разделе переменных:

Var M1, M2: Set of 1980..2008;

Var MS: Set of Char;

­Здесь элементами являются символьные константы, например:

MS:= [‘A’, ‘N’, ‘R’];

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

Свойства множеств

1. Все элементы базового типа, образующие множество, должны быть различны. Запись элементов множества (2, 2, 3, 4) некорректна, поскольку два элемента тождественны.

2. Порядок расположения элементов во множестве не фиксируется, то есть множества представляют собой неупорядоченные совокупности объектов (элементов). Множества (1, 3, 5, 6), (6, 1, 3, 5) и (5, 3, 1,6) одинаковы.

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

Операции над множествами

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

1) + объединение множеств;

2) * пересечение множеств;

3) – вычитание множеств;

4) =, < > проверка множеств на равенство, неравенство; множество А равно множеству В, если каждый элемент множества А является элементом множества В и наоборот, каждый элемент множества В является элементом множества А; иначе множества А и В неравны друг другу; результат операции будет логического типа: True или False;

5) <= проверка множества на включение; множество А включено в множество В, если элементы множества А являются также элементами множества В; результат операции А <= В – логический: True или False;

6) IN проверка на принадлежность какого-либо значения множеству; результат операции – логический: True или False; операция S IN A служит для проверки, принадлежит ли элемент базового типа S множеству А.

Пример. Решето Эратосфена. Составить программу, реализующую алгоритм определения набора простых чисел, не превышающих некоторого заданного числа, то есть алгоритм построения “решета Эратосфена”.

Program Resheto;

const N = 256; {Верхняя граница значений элементов множества}

var S: Set of 2..N;

C, M, P: integer;

begin writeln(‘Введите границу’);

read(P);

writeln(‘Простые числа до ‘, P: 3);

S := [2..N];

For C := 2 to P do

If C in S then

begin writeln(C: 3);

for M := 1 to (P div C) do

S := S – [C * M];

end;

end.

КОМБИНИРОВАННЫЕ ТИПЫ