Теорема о сложности сортировки

Теорема о сложности сортировки

Да
Нет
Нет
Нет
Нет
Нет
Да
Да
Да
Да

Теорема о сложности сортировки

Теорема о сложности сортировки

Для пересылок:
если мы определили требуемую перестановку
и имеем память для второй копии массива,
то достаточно сделать n пересылок.
На сегодняшний день
алгоритм, имеющий
n log2 n сравнений и n пересылок,
неизвестен.
Рассмотрим метод сортировки,
самый быстрый из известных.

Возьмем произвольный элемент массива, обозначим его через Х. Просматривая массив слева, найдем элемент ai ≥ x. Просматривая массив справа, найдем элемент aj ≤ x.
ai ≥ x i j aj ≤ x
≤x ≥x
Поменяем местами ai и aj. Будем продолжать процесс просмотра и обмена, пока i не станет больше j.
В результате массив окажется разделенным на две части: левую с элементами ≤x, и правую с элементами ≥x.
Затем к каждой части будем применять тот же алгоритм.
Метод Хоара (Hoare, 1962)
QuickSort

Метод Хоара (QuickSort)
Алгоритм на псевдокоде
L, R – левая и правая границы рабочей части массива
QuickSort ( L, R )
х := аL, i := L, j := R
DО ( i≤j )
DО ( ai < x) i := i+1 OD
DО ( aj > x) j := j-1 OD
IF ( i<=j ) ai↔aj,, i := i+1, j := j -1 FI
OD
IF ( L
IF ( i

К У Р А П О В А Е
Е У Р А П О В А К
Е А Р А П О В У К
Е А В А П О Р У К
Е А В А

А А В Е
А А В
А А В
А В

П О Р У К
К О Р У П
К О Р У П
П У Р
У Р
Р У
А А В Е К О П Р У

2) Х = med (aL ,…, aR) – медиана
Определение.
Элемент am называется медианой для элементов aL ,…, aR , если количество элементов меньших am равно количеству элементов больших am
(с точностью до одного элемента).
В примере буква К – медиана для КУРАПОВАЕ.
В этом случае массив разделяется на две равные части.
Определим наименьшее возможное количество сравнений.
Возьмем для примера n = 15 (степень двойки), затем массив делится на 7 и 7, затем на 3,3,3,3.
Всего потребуется 3 итерации.

Пример. X Х Х Х Х Х Х

Итак, количество сравнений C = n log n
Количество пересылок
зависит от расположения элементов,
но не может быть больше одного обмена (3 пересылки) на два сравнения.
Поэтому количество пересылок –
величина того же порядка, что и количество сравнений:
М = n log n.
Средняя трудоемкость QiuckSort: O (n log n), n?∞

Проблема глубины рекурсии
В теле подпрограммы доступны все объекты, описанные в основной программе, в том числе и имя самой подпрограммы. Это позволяет внутри тела подпрограммы осуществлять вызов самой подпрограммы.
Определение. Процедуры и функции, организующие вызовы «самих себя» называются рекурсивными.
Многие математические алгоритмы используют рекурсию, поэтому рекурсия широко используется в программировании.
Пример: Известный алгоритм вычисления факториала неотрицательного целого числа: 0! = 1, 1! = 1, n! = (n-1)! n.
long fact (int n) {
if (n<0) return 0;
if (n==0) return 1;
return (n*fact(n-1));
}

Вычисление 4!
fact (4) (((1*1)*2)*3)*4
fact(3) ((1*1)*2)*3
fact(2) (1*1)*2
fact(1) 1*1
fact(0) 1
Рекурсивное выполнение программы более компактно и наглядно, но существует опасность переполнения стека.

Фрейм:
При выходе из подпрограммы эта память (фрейм) освобождается.
Но если подпрограмма вызывает другую подпрограмму или саму себя,
то в дополнение к существующему фрейму
создается новый.
n вложенных вызовов ->
выделение n фреймов в памяти

Вместо двух рекурсивных вызовов
(для левой и правой части массива)
будем использовать только один рекурсивный вызов,
а другой заменим новой итерацией цикла.
Вопрос:
Для какой части массива нужно делать рекурсивный вызов,
чтобы уменьшить глубину рекурсии?
Ответ:
Для меньшей по размеру части массива.
!-------------!--------------------------------!
L J I R

Примеры рекурсии
Преподаватель всегда прав.
Если преподаватель не прав, смотри пункт 1.
Бюрократия разрастается, чтобы удовлетворить нужды разрастающейся бюрократии.
Смысл жизни – в достижении её цели, цель жизни – в наполнении ее смыслом.
Если у вас украли кредитную карту, позвоните по телефону указанному на оборотной стороне кредитной карты.
Для выхода в Интернет, скачайте нашу программу из Интернета.
Keyboard not found. Press F1 to continue.
Салат : помидоры, огурцы, салат.