Программирование. Сортировка и поиск


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

Задачи сортировки и поиска План:1. Алгоритмы решения задач внутренней сортировки.1.1. Сложность алгоритмов.1.2. Постановка задачи сортировки данных.1.3. Прямые и быстрые методы внутренней сортировки.1.4. Сортировка вставками.1.5. сортировка с помощью прямого выбора.1.6. Сортировка с помощью прямого обмена (пузырьковым методом).2. Алгоритмы поиска информации.2.1. Постановка задачи поиска информации.2.2. Последовательный (линейный) поиск.2.3. Бинарный поиск. 1. 2. Постановка задачи сортировки данных Нахождение такой перестановки mp1, mp2, …, mpn, записей m1, m2, …, mn, после которой ключи будут располагаться в неубывающем (невозрастающем) порядке: kp1 ≤ kp2 ≤ … ≤ kpn (kp1 ≥ kp2 ≥ … ≥ kpn)/ Сортировка называется устойчивой, если она удовлетворяет дополнительному условию: записи с одинаковыми ключами остаются в прежнем порядке, т.е. pi < pj, если kpi =kpj и i < j. Методы внутренней сортировки :Сортировка вставками: элементы просматриваются по одному, и каждый новый элемент вставляется на подходящую позицию среди ранее упорядоченных элементов.Сортировка с помощью выбора: сначала выделяется наименьший (или наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся элементов и т.д.Сортировка с помощью обмена: если два элемента расположены не по порядку, то они меняются местами. Этот процесс продолжается до тех пор, пока элементы не будут упорядочены. 1.4. Сортировка вставками Машинная реализация сортировки вставками procedure sortirovka_vstavkami;beginfor i:=2 to n do {Начало процесса сортировки}begin x := a[i]; j := 1; {Поиск места для вставки элемента a[i]=x} while (x >= a[j]) and (j < i) do inc(j); {Если место найдено, то перемещение элементов на одну позицию вправо} for k := i – 1 downto j do a[k+1] := a[k]; a[j] := x; {Вставка элемента х на найденное место} end;end; 1.5. Сортировка с помощью прямого выбора procedure sortirovka_priamoi_vibor;begin{ Поиск минимального элемента в диапазоне от 1 до m (m – размер массива)}for i := 1 to m dobegin min := b[i]; j := i; for k := i + 1 to m do{Поиск минимального элемента} if b[k] <= min then begin min := b[k]; j := kend;{Обмен местами минимального и i-го элементов} b[j] := b[i]; b[i] := min;end;end; Машинная реализация сортировки с помощью прямого выбора 1.6. Сортировка с помощью прямого обмена (пузырьковым методом) procedure sortirovka_priamoi_obmen (var а: аггау[1 ..n] of real);var i, j: integer; x: real;beginfor I := 1 to n-1 dofor j:= 1 to n-i doif a[j] > a[j+1] then begin x := a[j];a[j] := a[j+1];a[j+1] := x;end;end; Машинная реализация сортировки с помощью прямого обмена 2.2. Последовательный (линейный) поискa: array [l..n] of integer for i := l to n do if a[i] = x then k := i;2.3. Бинарный поискprocedure binarnii_poisk;begini := 1; j:=n;while i < j do begin middle := (i+j) div 2; if a[middle] < x then i := middle + 1 else j := middle;end;if a[i] = x then k := i else k := 0;end;

Приложенные файлы