- •Введение
- •Фундаментальные структуры данных:
- •Последовательные файлы
- •Буферизованная последовательность.
- •Стандартные ввод и вывод.
- •Рекурсия в алгоритмах
- •Алгоритмы поиска
- •Поиск деления пополам, бинарный поиск
- •Поиск в таблицах
- •Алгоритмы сортировки
- •Сортировка массивов
- •Сортировка прямым выбором
- •Сортировка с помощью прямого обмена
- •Оптимизация алгоритмов пузырьковой сортировки
- •Улучшенный метод сортировки
- •Сортировка с помощью дерева.
- •Эффективная организация дерева из n элементов.
- •Сортировка с помощью разделения.
- •Медианы и порядковые статистики
- •Использование QuickSort
- •Сортировка последовательности Метод прямого слияния
- •Организация динамических списков.
- •Поиск и включение в упорядоченном списке
- •Топологическая сортировка.
- •Деревья
Сортировка с помощью разделения.
Улучшенный метод основанный на методе пузырька. Автор Хоар. Сортировка Quick Sort. Алгоритм исходит из соображений, что для достижения наилучшей эффективности сначала лучше произвести перестановки на большие расстояния.
i<=j
I=1,
j=n
-
Случайно
выбранный х
aiaj
просмотр
слева пока не найду ai<x
i=i+1
j=J-1
i>j
Просмотр
справа, пока aj>x разделение
завершено
Необходимо применить этот процесс, и к получившимся 2-м частям до тех пор, пока каждая из частей не будет состоять из 1-го элемента.
По структуре алгоритма напрашивается применить рекурсивное обращение программы самой к себе при сужении границ массива до единичного расстояния между ними.
Procedure QuickSort (var a:array of integer);
Procedure Soft (L,R:integer);
i:=L;
j:=R
L<j
Soft
(L,i)
X=a[(L+R)div2]
i<R
Попарное
разделение массива на две части
Soft
(i,R)
End
Sort
i>j
-
Begin {Quick Soft}
Soft(0,n);
End;
Медианы и порядковые статистики
: порядковые статические множества состоят из n элементов : элементы в порядке возрастания
Медианы неформально означает середину такого множества.
Если n-нечетное, то медиана единственна и ее индекс i:=(n+1)div 2. Если n-четное, то нижняя медиана iн=n/2, iв=n/2+1
Обычно выражение медиана относится к нижней Медиане. Задача состоит в выборе I порядковой статистики в множестве из n чисел .
An 1<=i<=N вх.
Вых: x A превышает по величине (i-1) других элементов массива А.
Задачу выбора можно решить за время пропорциональное О(n*lgn)
Выполняется сортировка и берем элемент с номером i.
Существует более быстрые алгоритмы. Алгоритм выбора с линейным временем работы в нужный случай. Алгоритм будет находить нужный элемент путем разбития вх массива.
Все n элементы Вх массива разбираются на [n/5] и одна группа будет содержать остаток n mod 5
Метод вставок сортирует каждую группу и в каждой группе выбранную медиану
Путем рекурсивного использование??? этой процедуры выдает медиана Х множества из медианы найденных на 2 шаге. Если четное количество медиан, то х нечетное.
Использование QuickSort
Медианой из n элементов называется элемент значения, которого <=половины элементов или => другой половины n элементов.
16 12 99 95 18 87 10: Сортируем и ищем.
Использует алгоритм Хоара. L=1; R=n; В результате получаем индексы i и j
Ah<x, Ɐh<i
Ah>x, Ɐh>j
i<j
Каждый раз работает один из трех случаев
Разделяем элемент х слишком мал и граница принадлежит [i;R] и разделяем этот промежуток
Граница слишком велика и разделяется от L до j [L;j]
Процесс повторяется до тех пор, пока не получим 3 случай
L=1 R=n
j<R
Procedure Find (k:integer)
-
L<R
L=i
Окончание поиска
while +
j>k
x=ak
+
разделяем aL ÷ aR
end
R=i