Практика языка C (МФТИ, 2023-2024). Семинар 3.1. Линейный поиск и простые сортировки.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

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

Семинарист: Константин Владимиров.
Дата: 20 октября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.

Timeline
00:00 Константность
09:25 Typedefs
16:30 Поиск в массивах
23:20 Тасование Фишера-Йетса
28:30 Сортировка: мозговой штурм и наращивание инварианта
36:55 Время решать задачи
40:00 Пузырёк
47:20 Cdecl
52:35 Указатели на функции и qsort
01:03:10 Практикуемся в qsort
01:12:40 Ревью кода и завершение

Errata:
* Слайд 16: опечатка, вместо ++j надо --j
* 5:50 const int * const cpca можно инициализировать и &a, и &b - ошибки не будет

[siarheimarozau]

На рисунке на 52 минуте мне кажется что логичнее написать в первой строчке
int *arr[3]; int *pa = &arr[0];
вместо int *arr[3]; int *pa = &arr3[0];

[ddvamp]

51:10 Константин, как заметили ниже, здесь что-то не так. Во-первых, &arr3[0] это указатель на массив, а &arr3 это указатель на указатель на массив (int (**) [3]). Вероятно вы имели в виду &arr[0] и &arr. Во-вторых, адрес массива нельзя записать в int *, там должен быть как раз int (*parr3)[3]

[vdalart]

5:50 const int * const cpca можно инициализировать и &a, и &b - ошибки не будет

[МаксимРябцев-пс]

Спасибо за уроки! Где вы делаете презентации?

[antonzhurba]

как для практической части не раскрыта тема const для первого курса, когда всё таки его писать и когда его стоит упустить? Также упомянул бы основные проблемы что связанные (потеряна константности, "const poisoning").

[ДенисСомин]

Спасибо большое за лекцию, было, хоть и не сложно, но интересно.
Осталась правда пара вопросов:
1) можно ли написать свою обёртку над qsort, принимающая последним аргументом int (*)(), таким образом нам для каждого компаратора не пришлось бы писать эти явные преобразования из void * в TYPE *? (Вопрос, конечно, почему разработчики qsort так не сделали (скорее всего из-за ухудшения читаемости прототипа функции))
2) вы рассказали о расстановке квалификатора const и его смысл, однако не объяснили семантику выражения const void *ptr, правда это больше не вопрос, конечно, а придирка)
3) касательно сидекл и динамических массивов, что вы думаете по поводу указателя на vla в роли матрицы? т.е. int (*matrix)[m] = malloc(sizeof *matrix * n); это хорошая практика или же нет?

[ivankrutov]

Слайд 16. Кажется нужно заменить ++j на --j.

[ShtrikeBirb]

Кстати, а пузырек не выиграет у других в плане утилизации кэша?

[victormustya]

На 17 слайде косяк: следующий минимальный элемент 3, хотя в массиве есть 2 не на своём месте.