Course notes

Quick find, union

  1. Подходит для нахождения разделенных зон в пространстве

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

Stack and Queues

  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

Не стабильная.

Priority Queues

Priority Queues

Binary Heap

  1. Bottom-up reheapify (swim)

  2. Top-down reheapify (sink)

  3. Insert, remove max

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

and its variants are сache-efficient algorithms for sorting strings. They are variants of the traditional radix sort but faster for large data sets of common strings, first published in 2003, with some optimizing versions published in later years. Wikipedia.

Sort notes

Quicksort, как правило, считается самой эффективной и быстрой и поэтому используется в V8 как реализация Array.prototype.sort() для массивов с более чем 23 элементами. Для менее чем 23 элемента в V8 используется insertion sort2. 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

Задачи

Dutch national flag

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.

PreviousBig O notationNextBinary search (BST)

Last updated

Was this helpful?