7.Типы внутренних сортировок:
• Простого выбора
For i := 1 to (n-1) do
Begin
k := i;
For j := i+1 to n do
if a[j] < a[k] then k := j;
запомнить его индекс в переменной k;
если i <> k поменять местами a[i] и a[k];
End;
• Прямого включения
For k := 2 to n do begin
x := a[k]; j := k-1;
{ вставить х на подходящее место в a[j], ...,
a[1]
для этого организуем цикл, который
выполняется, пока (j > 0 и X > a[j]) }
{ в цикле смещаем элементы массива на 1
позицию вправо }
{ по выходу из цикла вставляем X в позицию
j+1 массива }
end;
• Простого обмена
Как и предыдущий, этот алгоритм состоит из отдельных шагов. На каждом шаге
массив проходят от начала к концу, сравнивая пары соседних элементов. Если
очередная пара нарушает требуемый порядок, ее элементы меняют местами.
Шаги повторяют до тех пор, пока очередной проход не вызовет ни одного
обмена.
• Сортировка пузырьком.Наиболее известной (и наиболее "бесславной") является
сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых
худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень.
• Усовершенствованные методы сортировки:
1)Сортировка Шелла. Общий метод, который использует сортировку вставкой,
применяет принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
2)Быстрая сортировка. В основе быстрой сортировки лежит принцип разбиения. Сначала
выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение.
Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован.
7.Поиск. Поиск – процесс нахождения конкретной информации в ранее созданном множестве данных. Обычно данные представляют собой записи, каждая из которых имеет
хотя бы один ключ. Ключ поиска – это поле записи, по значению которого происходит
поиск. Ключи используются для отличия одних записей от других. Целью поиска
является нахождение всех записей (если они есть) с данным значением ключа. Поиск информации в не отсортированном массиве требует проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива. Этот метод должен использоваться для неотсортированных данных, но он также может
использоваться для отсортированных данных. Если данные отсортированы, то может
использоваться двоичный поиск, который выполняется значительно быстрее.
Алгоритм последовательного поиска: Алгоритм последовательного поиска имеет очень простой вид. Ниже представлена функция, которая выполняет поиск в символьном массиве заданной длины элемента с заданным значением ключа:
function SeqSearch(item: DataArray; count:integer; key:DataItem):integer;
Var t : integer;
begin
t:=1;
while (key<>item[t]) and (t<=count) do t:=t+1;
if t>count then SeqSearch:=0
else SeqSearch:=t;
end; { конец последовательного поиска }
Двоичный поиск. Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его
ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
8.Массивы. • Массив представляет собой фиксированное количество однотипных компонентов, снабженных индексами.
• Массивы соответствуют, например,векторам (одномерный массив), матрицам
(двумерный массив) и др. Тип статического массива объявляют следующим
образом: Type <Имя> = Array[<тип индекса>] of <тип элементов>; Разрешается объявлять и использовать многомерные массивы ( до семимерных включительно).
Начальные значения элементов массива Типизированные константы:
Const q: array[1..4] of real = (5.2, 6.0, -3.1, 0.8);
Начальные значения для двумерного массива:
Type Matr = array[1..2,1..3] of byte;
Var R: Matr = ((3,7,5),(8,11,6));
Массив символов как типизированная константа:
Const C: array[1..5] of char = ‘abcde’;
Присваивание массивов друг другу:
Type V = array[1..5] of real;
Var A,B : V;
Begin
A:=B;
End.
9.Динамические массивы. Динамический массив объявляется как ссылка на адрес, по которому будут размещаться данные. Например:
Var V = array of real;
V1= array of integer;
Каждая из объявленных переменных (V или V1) может иметь значение какого-то адреса.
Объявляется только тип элементов массива, но не их количество. Имя массива содержит адрес первогомэлемента. Прежде чем располагать данные, этот адрес переменная должна получить. Память под данные выделяется процедурой SetLength:
Var V = array of real;
V1= array of integer;
begin
SetLength(V,5);
SetLength(V1,10);
end.
Особенности использования динамических массивов.
1) Нумерация индекса начинается с нуля.
2) Правила выполнения операции присваивания:
Type Vekt = array of real;
Var V1, V2 : Vekt;
Begin
…
V1 := V2;
…
end.
V1 и V2 ссылаются на один и тот же участок памяти. Элементы V1 и
V2 равны, но потерялся адрес V1, соответственно потерялся и
выделенный участок памяти, начиная с адреса V1.
3) Освободить память, выделенную под V1, можно, вызвав перед операцией присваивания:
Type Vekt = array of real;
Var V1, V2 : Vekt;
Begin
…
Finalize(V1);
V1 := V2;
…
end.
10.Многомерные динамические массивы. • Начальный индекс динамического одномерного массива V можно определить функциями Low(V) - (равен 0);
• Конечный индекс динамического одномерного массива V можно определить функциями High(V)
For i := Low(V) to High(V) do … Целесообразно не указывать непосредственно верхнюю
границу для циклических вычислений, поскольку в программе можно неоднократно менять размерность динамических массивов.