Информатика на Python, лекция 5, ФБВТ МФТИ (2023)

Курс информатики для 1-го курса ФБВТ МФТИ (2023).
Лекция 5: алгоритмы сортировки
Таймкоды:
00:00 Что такое сортировка?
03:35 Упорядочивание значений
10:07 Количество перестановок
27:36 Что нельзя упорядочить?
39:11 Сортировка дурака
45:47 Сортировка пузырьком
53:19 Сортировка выбором
58:25 Сортировка вставкой
1:05:45 Алгоритмы сортировок
Плейлист с лекциями 1-го курса ФБВТ МФТИ (2023): • 2023 ФБВТ Информатика ...
Снял и смонтировал видео: ​⁠​⁠ youtube.com/@antonoreshkin?si...

[@maximfox8330]

Что делать во время бессонницы? Конечно же изучать языки программирования.

[@prometeypoduction]

Отличный преподаватель с отличной подачей информации. Спасибо за лекцию!

[@ms_Mar]

Тимофей Хириянов, вам нет равных в качестве подачи информации за единицу времени. Благодарю! Было бы интересно послушать вас по поводу практики оптимизации кода, оценки затрат по памяти и т.п.

[@user-hg3oi4qw2d]

Как всегда, прекрасная лекция. Спасибо большое

[@Juvelir97]

Сначала лойс,потом просмотр! Спасибо,что делитесь своими знаниями!

[@maximfdrv]

Давно закончил университет, в начале карьеры на каждом собеседовании спрашивали сортировки, и они очень хорошо запомнились. Но эта лекция просто отпад. Спасибо за отличное видео

[@iritaka]

таймкоды: сортировки, множество перестановок, алгоритм проверки упорядоченности, отношение порядка, fool sort, bubble sort, choice sort, insert sort 0:00 вступление 2:54 код фильтрация (сортировка, как в жизни) 3:32 в программировании сортировка - это упорядочивание 3:45 первым делом вопрос: Что упорядочивать. Должна быть структура данных, которая подразумевает наличие порядка. Например, список. Упорядочение по возрастанию, неубыванию, не строгому возрастанию, что равенства допускает 5:08 когда мы подаём в параметр функции массив (A), она его отсортировывает и возвращает отсортированный массив (A') - это новый массив или старый изменяется. Есть два варианта сортировок: 1) inplace мы должны обладать ссылкой на этот массив, передать по адресу ( по ссылке) и должно происходить действие ровно над этим самым объектом. 2) not inplace - старый массив остаётся в исходном состоянии, а сортировка выдаёт новый массив, новый объект с новым идентификатором. Если есть альтернативное имя подаваемого в функцию массива, то объект сам либо изменится либо нет 6:25 стандартная сортировка A.sort() меняет сам массив, inplace 6:38 B = sorted(A) - не сортирует массив А, создаёт новый B отсортированных значений. Т.е. sorted(A) ничего не делает с А, не меняет его. И получаемое значение нужно сохранить в другом массиве 7:00 сортировка подразумевает не заполнение новыми значениями, а некоторую перестановку старых 8:00 множество перестановок, теория групп 9:36 есть некоторые допустимые перестановки и возникает вопрос: какие состояния достижимы, какие нет 10:12 допустим все элементы разные, есть N шт. элементов, тогда существует перестановок N! факториал 13:08 генерация всевозможных перестановок в Питоне модуль itertools permutations 13:49 тождественная перестановка 15:33 алгоритм проверки упорядоченности быстрее поиска перестановки 17:26 поиск имеет комбинаторную структуру, мощность - N! Чтобы добраться до ответа, количество операций N! 18:04 оценка скорости алгоритма производится по наихудшему случаю 19:37 реализация поиск будет не систематический через permutations, а функция shuffle (случайный поиск) в библиотеке random 20:16 сортировка обезьяны bogosort неэффективный алгоритм 23:21 что нельзя отсортировать: 1) Объект неизменяемый кортеж tuple 2) структуры данных, в которых нет порядка двоичные деревья поиска, хэш таблицы, множества set 3) несравнимые типы 27:00 важно понимать какому множеству принадлежат элементы 27:20 мы должны понимать применимость. Списки могут содержать разные типы 28:05 4) оператор сравнения (==, > , b, b > c, то a > c (транзитивность по неравенству) и если a == b, b == c, то a==c (транзитивность по равенству) 31:46 пример не подходящего случая объектов А = ["камень", "ножницы", "бумага"]. Множества, где нет транзитивности: К > Н, Н > Б, Б > К => невозможно отсортировать принципиально, не важно каким алгоритмом сортировки 33:06 упорядочение подразумевает и ближний и дальний порядок 34:40 пример 2 сортировка неприменима 36:32 международный стандарт IEEE 754 - 2008 г. дробных чисел float, double. Вещественные числа тоже нельзя отсортировать 37:19 Универсальные Квадратичные Сортировки (3: bubble sort, choice sort, insert sort) 38:48 квадратичные сортировки: скорость сортировки O(N**2) 39:03 проверка факта отсортированности 39:10 fool sort сортировка дурака неквадратичная O(N**3). Локальный порядок означает глобальный (для чисел) 41:24 транзитивность (отношение порядка) работает для целых чисел, для множеств - нет, а для дробных не совсем 48:05 bubble sort сортировка методом пузырька 51:28 массив из одного элемента упорядочен всегда 51:31 сортировка пузырьком. На маленьких размерах является одной из самых оптимальных по количеству действий, она не требует рекурсии, вызова функций, стеков, она очень экономная 53:19 choice sort сортировка выбором. Неустойчивая сортировка 56:24 устойчивость - равные друг другу элементы не окажутся перепутанными относительно своего исходного порядка. Не всегда равенство с точки зрения упорядочения означает что элементы абсолютно одинаковы и неотличимы 57:24 пример устойчивости по ФИО и возрасту 58:24 insert sort сортировка вставкой ( еще существуют квадратичные сортировки: гномья gnome sort, шелла shell sort) 59:17 инвариантом называется некоторое условие, которое в цикле всегда остаётся истинным 59:37 те элементы, что слева - упорядочены 1:01:01 чтобы слева не выйти в ошибку. Устойчивая сортировка, требует довольно мало операций. Удобна, когда элементы поступают по одному 1:10:41 код проверка отсортированности is_ascending() по возрастанию 1:13:54 код test_asc() делает массивы и указывает их отсортированность или нет и test_sort 1:18:42 код fool_sort() bubble_sort() Разъяснение тем лекции (читать, скачать бесплатно в формате docx) в группе ВК "Основы Программирования (кодинг) на Python" (osnovyprogrammirovania)

[@rudolf_rozbergo9]

Чтобы сделать задачи надо сделать задачи, не надейся на удачу разделяй на под задачи

[@pe5ha]

чтобы сдееелать матреешку надо сдееелать матреешку :D

[@rudolf_rozbergo9]

@@pe5ha но кто сконструирует последнюю матрешку?

[@Vladimir_Kondratev.]

Спасибо огромное.

[@jamjam3337]

👏👍

[@user-fl7qv5zz2l]

А что не так с сортировкой дробных чисел?

[@lex_darlog_fun]

Если вкратце - ошибки округления. Во всём программировании флоты - это, ПО ОПРЕДЕЛЕНИЮ, не абсолютно точное представление числа. Любое сравнение флотов - это вообще глобальная проблема. Нерешаемая. Там ВСЕГДА есть какая-то погрешность. Просто погуглите float equality на stackoverflow - и откроется бездна страданий. Как следствие, не зная конкретной области использования для функции (не зная, какие вообще там данные ожидаются, каковы возможные значения) - невозможно написать универсальную сортировку. Вернее, универсальную-то написать можно. Но она ГАРАНТИРОВАННО будет отказывать в определённых эдж-кейсах.

[@tkhirianov]

Наличие в множестве дробных чисел с плавающей точкой состояния "Not a Number" ломает отношение порядка.

[@romanticroman11]

Просмотрел многое из выложенного , и для меня лично это выглядит так : посмотрите как это здорово и интересно . Вопрос : а что с этим делать ? Ответ : а хрен его знает . Раз это блог МФТИ то как мне думается должно быть видео с написанием очень полезной программы для какого то конкретного предприятия ( как пример ) .

[@user-wm4gv6wi4x]

Преподаватель чудак на букву 'М', пионерская организация уничтожена уже больше 30 лет, но нет, нужно всё равно бросить свои испоражнения в неё. Но всё таки хочу сказать спасибо за урок.

[@PetroUralov]

Фуххх ! Вас не закрыли как учёного который сотрудничает с иностранными агентами. Сейчас это в тренде. Тем более ваши ролики на ютуб, а он запрещён в РФ

[@ander1475]

ютуб запрещен? это что-то новенькое. Не выдумывайте.

[@user-gh8xc9gk5g]

Ахахахаха

[@PetroUralov]

@@ander1475 вообще то запрещён. запрещён и заблокирован разные слова если что