Паскаль (Pascal) разрабатывался, как учебный язык выского уровня, структурного программирования. Относится к 3-му поколению языков программирования. На основе ALGOL.
Составные типы данных – типы данных базирующиеся на простых. Важна однотипность элементов и способ доступа, позволяющие выделить главные представители сложных типов.
Массив - набор однотип переменных, каждому эл-ту которого присвоен некот поряд номер, что обеспечивает простоту доступа к каждому эл-ту.
Массивы могут быть одномерными и многомерными
Описание при помощи слова array в разделе описания типов
Алгоритм сортировки - алгоритм упорядочения элементов в списке
Сортировка массива - процесс перестановки его элементов в опред порядке
Основ требов к методам сортировки - экономия использования памяти
Быстрая сортировка — широко извест алгоритм сортировки, разработ англ информатиком Чарльзом Хоаром. Самый быстрый из извест универс алгоритмов сортировки массивов (в среднем O(n log n) обменов).
Разделяй и властвуй — в информатике важная парадигма разработки алгоритмов. Основана на рекурсивном разбиении решаемой задачи на 2 или более подзадач. Разбиения выполняются до тех пор, пока все подзадачи не станут элементарными.
Рекурсия - ситуация, когда какой-то алгоритм вызывает себя прямо или через другие алгоритмы в качестве вспомогательного.
Любая рекурсия содержит 2 условия:
1.вычисление результата через другие значения, не влечет нового рекурсивного вызова;
2.вычисление значения с помощью самовызова функции (рекурс вызов).
Идея быстрой сортировки (по возраст) Массив разделяется на 2 равные части, каждая сортируется и они сливаютсяя в одну. Эта процедура выполняется, пока не останется отсортировать массивы длины 1 и 2.
Шаг 1. Выбираем в массиве элемент, кот назовем опорным. Обычно средний или последний по положению или вообще любой.
Шаг 2. Разделение массива: элементы <=опорному слева, а > справа.
Шаг3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента
Шаг 4. Базой рекурсии являются наборы, состоящие из 1 или 2 эл-тов. Если 1, то возвращается в исход виде, если 2: при необходимости меняем местами.
"+" Самый быстродействующий из всех алгоритмов обмен сортировки
Простая реализация
Хорошая работа на "почти отсорт" данных
"-" Требует в худшем случае много доп памяти. Но вероятность худшего случая ничтожна
Не является устойчивым
Пример type list = array[1..20] of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var i,j,x,y: integer;
begin
i:=l; j:=r; x:=a[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента }
repeat
while a[i]
while x
if i<=j then begin
if a[i] > a[j] then begin
y:=a[i]; a[i]:=a[j]; a[j]:=y; end;
i:=i+1; j:=j-1;end;
until i>j;
if l
if i
end;
begin {quicksort};
sort(Lo,Hi); end;
13.
