# Course notes

### Quick find, union

1. Подходит для нахождения разделенных зон в пространстве
2. Есть наборы чисел, определять максимум/минимум из набора, тыкая в любое число набора. Определять к какому набору относится

### Stack and Queues&#x20;

1. Для оптимизации памяти под массив для стека - увеличиваем массив в 2 раза каждый раз когда массив достигает своего конца. И наоборот уменьшаем в 2 каждый раз когда данные в массиве уменьшаются в 4-ро.
2. Алгоритм Дейкстры по решению примеров с откр. и закр. скобками. Также подобный подход применим к задаче на поиск парности скобок

### Elementary Sorts

1. Selection Sort - находим минимальный и меняем с текущим. Сложность N^2. Проблема его в том, что не важно на сколько отсортирован алгоритм - он его будет проходить полностью. Даже если в процессе массив уже отсортирован - алгоритм будет пробегать (проверять) его до конца
2. Insertion Sort - берем каждый послед. элемент и сдвигаем его назад на свою позицию. Сложность в худшем случае N^2. Прелесть в том, что если массив отсортирован частично - то сложность сортировки начинает стремиться к O(n). Алгоритм заканчивает работу, когда массив отсортирован
3. Shell Sort - берем находим последовательность сегментов на кт. поделим массив (например, 13, 4, 1) - потом сортируем эти сегменты, делим на след. кол-во сегментов. В конце сортируем массив как единое целое. Особенность в том, что если мы для сортировки применяем Insertion Sort - то он будет сортировать быстро, когда сегмент частично отсортирован. Сложность N\*logN. Проблема этого алгоритма в нахождении последовательности сегментов. Есть разные подходы по поиску этих сегментов. Единого наиоптимальнейшего пока нет
4. Shuffling - чтобы достичь сложности O(n) - идем по массиву, генерируем случайное число от 0 до `i` и меняем местами элементы по полученному индексу
5. Complex Hull - алгоритм расчета фигуры которая будет проходиться по крайним точкам опр. множества точек на площади. Т.е. будет показывать границы данного множества. Алгоритм: берем крайнюю правую нижнюю как нулевую. От нее строим отрезки ко всем другим точкам. И начинаем идти против часовой стрелки и строить отрезки от одной до др. точки. Каждый раз мы должны при соединении с новой точкой поворачивать влево. Если мы поворачиваем вправо - то значит эта точка находится не на границе, а внутри фигуры и соединяем пред. точку со след. И так продолжаем пока достигнем нулевой точки

### Mergesort

Работает по принципу деления массива на 2 сегмента, и потом склеивания этих двух сегментов и так рекурсионно вниз, пока получим на сравнение по 1 элементу в сегменте, кт. соотв. будем сравнивать и склеивать воедино. Я взял алгоритм из курса и из статьи в Гугле. И они обе реализуют mergesort, но важна еще **Стабильность**. Которая означает, что если у нас есть табличные данные и мы их сортируем по одному столбцу, то когда потом будет пересортировывать по другому столбцу. Если его значения будут одинаковые, то должна у этих одинаковых сохраняться сортировка по предыдущему столбцу. Mergesort и Insertion sort выдерживают этот критерий.

Этот алгоритм не оптимален по памяти, так как создает доп массив длинной O(n) для своей работы.

### Quick sort

Не стабильная.&#x20;

![](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)

### Priority Queues

[Priority Queues](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D0%B8)

### Binary Heap

1. Bottom-up reheapify (swim)
2. Top-down reheapify (sink)
3. Insert, remove max

![](https://4251836425-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lnd5skvXnyJUQsGuNMc%2F-MT4KjphNjCoc7-08NXJ%2F-MT4Kui1uPFoh3_QsG7b%2Fimage.png?alt=media\&token=35023e6f-14a0-4d78-931a-3dd63f2a340c)

MaxPQ и MinPQ - приоритезированные очереди: быстрый доступ к min/max элементу,  быстрая вставка/удаление. Если нужно знать/менять позицию элемента в куче - для этого `IndexMinPQ` (max).

#### Применение

Prim’s algorithm and Dijkstra’s algorithm. Kruskal’s algorithm. Huffman compression. String-processing.

### Heap sort

Проводится при помощи MaxPQ.  Делается inplace. Сначала прогоняем полкучи через sink, а потом делаем delMax и запихиваем в конец. Просто и эффективно.

### Burstsort <a href="#firstheading" id="firstheading"></a>

and its variants are сache-efficient algorithms for sorting strings. They are variants of the traditional [radix sort](https://en.wikipedia.org/wiki/Radix_sort) but faster for large data sets of common strings, first published in 2003, with some optimizing versions published in later years. [Wikipedia](https://en.wikipedia.org/wiki/Burstsort).

### Sort notes

Quicksort, как правило, считается самой эффективной и быстрой и поэтому используется в V8 как реализация `Array.prototype.sort()` для массивов с более чем 23 элементами. Для менее чем 23 элемента в V8 используется insertion sort[2](https://www.nczonline.net/images/wp-content/uploads/2012/11/quicksort_21.png). Merge sort - конкурент quicksort, аналогично ему он также эффективный и быстрый, но имеет дополнительное преимущество - устойчивость. Поэтому Mozilla и Safari используют его для имплементации `Array.prototype.sort()`.

#### Time and Space Complexity Comparison Table :

| Sorting Algorithm  | Time Complexity | Space Complexity |                |                |
| ------------------ | --------------- | ---------------- | -------------- | -------------- |
|                    | Best Case       | Average Case     | Worst Case     | Worst Case     |
| **Bubble Sort**    | **Ω(N)**        | **Θ(N2)**        | **O(N2)**      | **O(1)**       |
| **Selection Sort** | **Ω(N2)**       | **Θ(N2)**        | **O(N2)**      | **O(1)**       |
| **Insertion Sort** | **Ω(N)**        | **Θ(N2)**        | **O(N2)**      | **O(1)**       |
| **Merge Sort**     | **Ω(N log N)**  | **Θ(N log N)**   | **O(N log N)** | **O(N)**       |
| **Heap Sort**      | **Ω(N log N)**  | **Θ(N log N)**   | **O(N log N)** | **O(1)**       |
| **Quick Sort**     | **Ω(N log N)**  | **Θ(N log N)**   | **O(N2)**      | **O(N log N)** |
| **Radix Sort**     | **Ω(N k)**      | **Θ(N k)**       | **O(N k)**     | **O(N + k)**   |
| **Count Sort**     | **Ω(N + k)**    | **Θ(N + k)**     | **O(N + k)**   | **O(k)**       |
| **Bucket Sort**    | **Ω(N + k)**    | **Θ(N + k)**     | **O(N2)**      | **O(N)**       |

#### Performance characteristics of sorting algorithms

![](https://4251836425-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lnd5skvXnyJUQsGuNMc%2F-MjcDbBrzjEEDyRdYFPJ%2F-MjcEIDG8B6iZVEtZ-xc%2Fimage.png?alt=media\&token=aa4b82fa-99cf-47ae-ba21-6fc76701214b)

### Задачи

[Dutch national flag](https://www.coursera.org/learn/algorithms-part1/quiz/cjwBY/interview-questions-elementary-sorts-ungraded/attempt)

```
Dutch national flag. Given an array of n buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are:
- swap(i,j): swap the pebble in bucket i with the pebble in bucket j.
- color(i): determine the color of the pebble in bucket i.
The performance requirements are as follows:
- At most n calls to color().
- At most n calls to swap().
- Constant extra space.

```
