Сортировка подсчетом (Counting sort)

[Все сортировки]

Теория: Wikipedia

Практика: acmp.ru

Реализация:

1. void counting_sort(vector<int> &mas) {
2.   vector<int> amount(MAX_VALUE,0);
3.   for (int i=0;i<mas.size();i++)
4.     amount[mas[i]]++;
5.   int pos = -1;
6.   for (int i=0;i<MAX_VALUE;i++)
7.     for (int j=0;j<amount[i];j++)
8.       mas[++pos] = i;
9. }

* This source code was highlighted with Source Code Highlighter.

Занятие №4. Алгоритмы сортировки

Теория: Лекция                                                                                           [Все занятия]

Практика:                                         [Официальная страница]
Учебные задачи:
   Задача A. 
   [Пузырьковая сортировка: количество обменов]
   Классическая задача на пузырек. 
   Задача B.  
   [Разные]
   Еще одна классическая задача, для которой нужно применить квазилинейную сортировку. 
   Задача С. 
   [Объединение последовательностей]
   Задача на слияние двух отсортированных массивов. 
Олимпиадные задачи:
   Задача A. 
   [Ожерелье]  
   Довольно занятная задача. Пришлось подумать. Пока думал настрогал прожку, которая bfs’ом находит оптимальную стратегию. Только после этого решение стало очевидно).
   Задача B.
   [Головоломка] 
  Очень любопытная задача. Интересно всегда наблюдать за тем, как люди(и я в том числе) пишут симулятор разгадывания головоломки с помощью DFS или BFS, а потом с криками матерного содержания переписывают решение за 3 минуты и получают законные Accepted.  
  Задача С. 
  [НГУ-стройка]
  Задача кажется с первого взгляда неприступной. Но если хорошенько присмотреться, то все не так страшно. Первое что нужно понять, как будет выглядеть сечение блоков, если зафиксировать конкретное значение Z. Это будет набор взаимно непересекающихся прямоугольников. Чтобы проверить покрывают ли эти прямоугольники всю область достаточно найти сумму их площадей. Общая идея решения изложена в лекции п.9. Сканирующая прямая.
Дополнительные олимпиадные задачи:
   Задача A.  
   [Эльфы и олени] 
   Одна из тех задач, где жадность приводит к правильному ответу. Сортируем в порядке неубывания массив эльфов и оленей. Бинарным поиском подбираем K - количество оленей, которые попадут в упряжку. Чтобы проверить можно ли запрячь K оленей применяем следующую эвристику. Выбираем K минимальных эльфов и K максимальных. Группируем этих 2K эльфов по парам, чтобы обеспечить максимальное покрытие диапазона, которые занимают эльфы. Получаем: (1, N – K + 1), (2, N – K + 2) и т.д., где N – количество эльфов. С учетом выбранных пар утверждаем, что никакое другое деление на пары не увеличит количество оленей в ответе. Далее необходимо фиксировать выбранную пару эльфов и искать для него минимально возможного оленя.
Приведенное решения полностью идентично разбору Александра Чистякова с одним отличием, что для фиксированной пары эльфов можно находить оленя за O(logM) с помощью функции lower_bound, а не за O(M).
   Задача B.
   [Субботник]
   Сортируем человечков по росту. Бинарным поиском по ответу подбираем ответ на задачу, а именно наименьшее возможное значение максимального числа неудобства. Для того, чтобы проверить корректность выбранного ответа последовательно перебираем слева направо группы из подряд идущих С человечков. Считаем количество групп, которые удовлетворяют выбранному ответу. Если их количество не меньше заявленного в условии R, то выбранный ответ является корректным. Такая жадность дает корректный ответ.
   Задача С.
   [Палиндром]
   Довольно простая задача на сортировку подсчетом.

Быстрая сортировка (Quick Sort) за O(NlogN) в среднем случае

[Все сортировки]

Теория: k-ая порядковая статистика 

Практика: informatics.mccme.ru

Визуализатор: youtube.com [Adobe Flash Player]

Реализация:

1. int partition(vector<int> &mas, int l, int r) {
2.   int pos = l-1;
3.   for (int i = l; i <= r; ++i) {
4.     if (mas[i] <= mas[r] )
5.       swap(mas[++pos], mas[i]);
6.   }
7.   return pos;
8. }
9. void quick_sort(vector<int> &mas, int l, int r) {
10.   if (l >= r) return;
11.   int pivot = partition(mas,l,r);
12.   quick_sort(mas,l,pivot-1);
13.   quick_sort(mas,pivot+1,r);
14. }

* This source code was highlighted with Source Code Highlighter.

Данная реализация на предложенной задаче работает в 2 раза быстрее(0.059 c), чем heap_sort(0.122 c).

K-ая порядковая статистика за O(N) в среднем случае

Потратил значительное время на поиск красивой реализации данного алгоритма. Как и следовало ожидать она лежала прямо под носом

1. int partition(vector<int> &mas, int l, int r) {
2.   if (l!=r)
3.     swap(mas[l + rand() % (r - l)], mas[r]);
4.   int x = mas[r];
5.   int i = l-1;
6.   for (int j = l; j <= r; j++) {
7.     if (mas[j] <= x)
8.       swap(mas[++i],mas[j]);
9.   }
10.   return i;
11. }
12. int nth(vector<int> mas, int n) {
13.   int l = 0, r = mas.size() - 1;
14.   for(;;) {
15.     int pos = partition(mas,l,r);
16.     if (pos < n)
17.       l = pos + 1;
18.     else if (pos > n)
19.       r = pos - 1;
20.     else return mas[n];
21.   }
22. }

* This source code was highlighted with Source Code Highlighter.

Немного проанализируем представленный код.
Функция nth принимает на вход массив и номер порядковой статистики, которую нужно найти. После выполнения функция возвращает значение порядковой статистики.
Но куда большее значение имеет функция partition. Суть ее заключается в том, что она выбирает произвольный элемент массива mas, индекс которого находится в интервале [l,r] и ставит его на “свое место”, т.е. на то место, на котором находился элемент, если бы массив был упорядочен.
В строке 3 как раз и происходит выбор этого произвольного элемента. После чего выбранный элемент меняется местами с последним элементом рассматриваемого интервала.
Если в качестве произвольного элемента брать всегда последний элемент или какой-нибудь фиксированный, то при желании можно легко подобрать тест, на котором представленная реализация будет иметь квадратичную сложность. Кстати если исходный массив будет упорядочен и в реализации функции partition будут отсутствовать 2 и 3 строки, то в каждой итерации функции nth на “свое место” будет становится только последний элемент и это будет повторяться SIZE раз, где SIZE – размерность массива.
На произвольном массиве данная реализация работает в среднем за O(N). Реализацию данного алгоритма при которой он будет работать за O(N) на любом массиве мы рассмотрим позже.

Обратите внимание, что в приведенной реализации массив передается по значению. Это следует делать, если мы незаинтересованы в частичном упорядочивании массива. В противном случае массив следует передавать по ссылке.

P.S: Если исходный массив будет состоять из одинаковых элементов, то приведенный алгоритм будет работать за O(N*N).

Летняя школа “Комбинаторная математика и теория алгоритмов” 14-25 августа 2011

Мы с Сагуновым Данилом посетили это мероприятие, куда нас пригласил Алексей Чернов. За что ему БОЛЬШОЕ спасибо. Мы жили в лагере “Алый парус”, хотя по другим источникам он называется “Алые паруса”. Лагерь находится в лесной местности неподалеку от речки. Природа просто отличная! Прикладываю видосик, который подтвердит мои слова.

В программу мероприятий входили лекции по разным направлениям комбинаторной математики, а также занятия, направленные на изучение алгоритмов. Мне предложили прочитать небольшой курс, который мы назвали “Классические комбинаторные алгоритмы”. Он состоял из 4 занятий: 
1. Генерация перестановок
2. Битовые операции
3. Подсчет количества инверсий в перестановке
4. Подсчет значения арифметического выражения. 

Каждое занятие было снабжено практическими задачами, которые проверялись в полевых условиях на тестах.
Полный архив с материалами занятий(лекции+задачи+тесты)

P.S: на обратной дороге были сделаны следующие забавные кадры, которые я думаю уместно разместить здесь