Skip to content

Latest commit

 

History

History
188 lines (111 loc) · 10.8 KB

quicksort.md

File metadata and controls

188 lines (111 loc) · 10.8 KB
Raw

Куча

Подвешенное дерево - дерево, у которого есть корень.

Двоичная Куча - такое подвешенное дерево, для которого выполнены три условия:

  1. Значение в любой вершине не меньше, чем значения её потомков.

  2. У любой вершины не более двух сыновей.

  3. Слои заполняются последовательно слева направо сверху вниз.

Правильная куча

Давайте обозначим как h высоту кучи.

Куча также умеет 3 основные операции :

  1. найти минимум за $O(1)$

  2. удалить минимум за $O(h)$

  3. добавление нового ключа в кучу за $O(h)$

Так как куча всегда состоит из нескольких слоев заполненых полностью и одного частично и каждый слой содержит в два раза больше вершин, чем предыдущий, то можно понять, что высота дерева будет не больше $O(log(N))$.

Теперь давайте поговорим о том, как же реализовать такую структуру.

Хранить кучу мы будем в виде массива, где у корня индекс равен $1$, и у вершины $n$ индексы ее потомков - $2 n$ и $2 n + 1$. Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией Up.

Запускаемся из элемента $i$. Если элемент больше своего отца, то больше ничего делать не нужно. Иначе, мы меняем местами его с отцом и запускаемся от отца. В результате такой функции мы исправим случаи, когда первое условие кучи не соблюдается. Так как каждый раз мы только поднимаемся, то работать функция будет за количество предков вершины, а оно максимум равно высоте дерева.

void Up(int i) {
    while (i > 1 && a[i] < a[i / 2]) {    // i = 1 — корень
        swap(a[i], a[i / 2]);
        i = i / 2;
    }
}

Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией Down. Запускаемя от элемента $i$, если $i$-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами $i$-й элемент с наименьшим из его сыновей, после чего выполняем Down для этого сына. Так как каждый раз мы спускаемся только в одного сына, то работать функция будет за высоту дерева.

void Down(int i) {
    while (2 * i < size) {    // size — количество элементов в куче
        left = 2 * i;             // left — левый сын
        right = 2 * i + 1;            // right — правый сын
        j = left;
        if (right < size && a[right] < a[left]) {
            j = right;
        }
        if (a[i] <= a[j]) {
            break;
        }
        swap(a[i], a[j]);
        i = j;
   }
}

Красивая визуализация: https://visualgo.net/en/heap

1 операцию мы умеем выполнять, просто спросив про корень.

Для 2 операции мы меняем последний элемент кучи и корень, а затем уменьшаем размер кучи и вызываем Down для корня.

3 операция - просто добавление элемента конец в кучи, а затем вызываем для него Up.

Теоретическое задание

Дана куча из рисунка сверху, вам даны 3 запроса, нарисуйте как выглядит куча после каждого запроса:

  • добавить число 125
  • удалить максимальное
  • вывести максимальное

В с++ куча реализована в STL в библиотеке <queue> :

priority_queue<type> Q;
Q.pop();
Q.push();
Q.top();

Практическое задание

В контесте на информатиксе на эту тему первые 5 задач.

Сортировка

На самом первом занятии вы ознакомились с квадратичными алгоритмами сортировки и сортировкой слияниями, а сейчас я вам расскажу гораздо более интересные сортировки.

Сортировка кучей

Только что мы с вами познакомились с кучей. Благодаря ей можно отсортировать числа по возрастанию: просто вставить все числа в кучу, а затем $N$ раз достать минимум. Работает это за $O(NlogN)$ (так как мы $N$ раз вставляем и удаляем элемент, а обе эти операции работают за логарифм).

Практическое задание

(6 задача)

Быстрая сортировка

Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент, все элементы, которые меньше его кидаем в левую часть, остальные в правую, а затем рекурсивно спускаемся в обе части.

https://visualgo.net/en/sorting

void quicksort(int l, int r){
    if (l < r){
        int index = (l + r) / 2; /* index - индекс опорного элемента для 
        начала сделаем его равным середине отрезка*/
        index = divide(l, r, index); /* divide - функция разбивающие элементы 
        на меньшие и больше/равные a[index], 
        при этом функция возвращает границу разбиения*/
        quicksort(l, index);
        quicksort(index + 1, r);
    }
}

Давайте оценим асимптотику данной сортировки. На случайных данных она работает за $O(NlogN)$ , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна - одинаковые числа, а вторая - если вдруг середина - минимум или максимум.

Существуют несколько выходов из этой ситуации :

  1. Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за $NlogN$.

  2. Давайте делить массив не на две, а на три части(меньше, равны, больше).

  3. Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент.

###Теоретическое задание

Вывести оптимальные числа (при которых алгоритм работает быстрее всего) на всех этапах массива (8, 3, 2, 5, 4, 6, 7, 1).

Поиск $k$-ой порядковой статистики за $O(N)$

Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.

Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая

  1. количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.

  2. количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.

  3. количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.

За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму $\sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}$ что в нашем случае это максимум равно $2 * N - 1$, то есть $O(N)$.

Также в с++ эта функция уже реализована :

nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);

Теоретическое задание

Рассказать, как работает алгоритм при k = 5 и массиве - (1, 8, 4, 6, 7, 5, 3, 2), опорный элемент - середина

Практическое задание

3 задачи на еджадже. В 2 из них у вас будет проверяться код.

Также нужно порешать практический контест на codeforces.

Ссылка на контесты

Куча: https://informatics.msk.ru/mod/statements/view.php?id=33379

Быстрая сортировка: http://ejudge.algocode.ru/cgi-bin/new-client?contest_id=5001

Практический контест: https://codeforces.com/group/g92L0id9Yb/contest/237751