Практика языка C (МФТИ, 2023-2024). Семинар 3.3. Цифровые сортировки.
Вставка
- Опубліковано 13 чер 2024
- Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом занятии мы займёмся цифровыми сортировками и поиском. Начнём с интересной задачи определения большинства, рассмотрим сортировку подсчётом и поразрядную сортировку. Также в конце обсудим двумерные массивы.
Семинарист: Константин Владимиров.
Дата: 10 ноября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Majority element.
13:14 Пределы сортировки сравнением.
22:00 Сортировка подсчётом и поразрядная.
35:00 Решаем задачи.
38:20 Двумерные массивы.
46:24 Домашнее задание: timsort.
53:50 Ревью кода и завершение.
Errata:
* Пока пусто
В сортировке подсчётом по идее нужно ещё и минимальное значение искать, тогда и размер массива для подсчёта количества одинаковых значений будет оптимальным и отрицательные числа можно сортировать.
31:26 Если я правильно понял, то в сортировке по младшему разряду, после вычисления b[], содержащего "инклюзив скан", можно бежать от i=0 по исходному массиву a[i] и, например, формировать из его элементов стабильно сортированный массив a2[].
Допустим, так: k=b[a[i]%10]++; a2[k-1]=a[i]; i++;
Можно ещё сформировать "инклюзив скан", сразу на 1 меньше, (уже равным индексу, накапливая его содержимое от -1), тогда сэкономим по одной операции "k-1" на каждый сортируемый элемент.
И ещё я заметил, что в домашней работе для этой сортировки (в декларации функции), правильнее дать указатель типа const unsigned int *parr, а то с индексом баскетов может нехорошо получиться для отрицательных значений элементов.
33:26 выглядит так что конечный b[1] должен хранить b[0] старого b[] а не b[0] + b[1] иначе все элементы из a[] заканчивающиеся на 1 перескочат вперед слишком сильно по индексам. пример: изначально b[0] = 2, b[1] = 2; новый b[0] будет равен 0, а b[1] = 4. первая еденица по модулю 10 перейдет сразу на 4 индекс вместо нужного второго индекса. следовательно возможное решение изменения b[] это b[j] += b[j - 1] в цикле с j = 1 а потом второй цикл b[j] = b[j -1] где j идет с конца массива до первого индекса сдвигая все значения на один элемент вправо чтобы не потерять нужный нам конечный b[1]. потом можно сделать b[0] = 0; тогда и адресация по новому b[] будет правильная и не нужно будет вычитать еденицу от индекса и делать исключение для нулевого индекса с вычетом еденицы
По идее, radix sort будет эффективней, если по степеням двойки брать разряды, нет? Маску наложить дешевле, особенно если на машине нет целочисленного деления.
Да хорошая идея для оптимизации. Я про неё забыл.
Не могли бы Вы немного подробнее написать по этой теме?
Здравствуйте, хотел бы внести пункт в errata, на 34:00 когда вы объясняете radix_sort, элементы массива, содержащие позиции необходимо декрементить, т.к. каждый из них содержит сумму предыдущих с добавлением количества элементов для текущего разряда, т.е. позиция элемента исходного массива в новом, равная b[j] - 1 будет крайней правой, а следовательно и обходить исходный массив нам нужно справа налево, чтобы получить стабильную сортировку.
То что вы предлагаете это просто другой алгоритм. Есть right-to-left radix, есть left-to-right. То что у меня на слайдах если починить баг, который я проговариваю словами тоже будет работать в т.ч. стабильно.
12:17 а если вот такой массив: 2 3 2 3 2. Здесь i всегда будет равно 0. И нужен будем еще один проход по массиву, т.к. в конце m = 2.
56:00 -fsanitize=address работает быстрее, чем valgrind, а ошибки ловит те же самые.
Доступ к неинициализированной памяти asan не ловит. Пытается ловить msan, но там есть нюансы.
А если отсортировать массив поразрядной сортировкой за о(n) , а потом за 1 проход найти то, которое чаще встречается. Тогда проблема me решена за о(n) и щадяще к памяти
Да вполне возможный выход. Если речь о целых числах. А если это произвольные объекты?
59:28 в 35 строке разве не ошибка инициализация temp в теле цикла ?
Нет, имеем право. Она же в начале блока.