Алгоритмы на Python 3. Лекция №6

[@iritaka]

Тайм-коды: Сортировки, объект list 1:10 в языке Python список list не является массивом. У массива с фиксированным размером надо самостоятельно отслеживать его уровень заполнения 3:43 A = [] # создаем list 4:18 у списка не надо самостоятельно отслеживать количество элементов 4:34 метод A.append(x) # добавление элемента x в конец списка A. 5:05 список - динамический массив, модифицируемого размера 5:20 функция n = len(A) # длина текущего массива, сколько элементов в массиве, его заполненность 5:59 метод A.pop() # удаление элемента с конца 7:35 Списковые включения (list comprehensions) # A = [x**2 for x in range (10)] 10:42 цикл for в Питоне спискового характера 14:28 if в list comprehension 17:10 тернарный оператор 19:00 квадратичные сортировки: количество операций, которое требуется на обработку массива, чтобы его отсортировать равно примерно N**2, где N - длина массива. Асимптотика алгоритма - O (N**2) 20:28 Сортировка вставками (insert sort) 26:16 Сортировка выбором (choice sort) 29:40 инвариант цикла 34:02 N-1 проход в квадратичных сортировках 34:19 Сортировка методом пузырька (bubble sort) 40:49 количество итераций 44:39 мастер-класс по TDD (test-driven development). тестирование 46:18 передача функции как параметра в функцию 52:02 списки в Питоне можно конкатенировать(складывать) 53:15 A = list(range(10, 20)) # создание списка генератором 57:33 sort_algorithm.__doc__ # получить документ-строку 58:05 функцию, когда передаем как объект в параметр, пишем без скобок 59:35 алгоритм insert_sort(A) 1:02:44 while k > 0 and A[k-1] > A[k]: # логическое "и" в Питоне Ленивое, т.е. он не будет вычислять второе условие, если первое ложное 1:05:11 return из этой функции не требуется, потому что список изменяемый (даже изнутри функции), он уже и так изменится 1:05:59 алгоритм choice_sort(A) 1:08:03 алгоритм bubble_sort(A) 1:11:53 Сортировка подсчётом (count sort), По времени - O(N), по памяти -O(M), где М - количество различных элементов 1:13:50 для маленького диапазона значений. Однопроходный алгоритм 1:18:16 частотный анализ

[@konst2087]

спасибо!

[@novikovjekas]

До чего же крутой преподаватель. Глаза горят, как у ребёнка в начт на 31 декабря. Мысли порой путаются от возбуждения. Хочет все и сразу рассказать, а пара всего 1.20 и не уместить все то, что так хотелось. Рад, что спустя 20 лет после окончания университета есть подобные видео, с такими профессионалами, с которыми учиться стало интересно, чего увы не было на моих парах.

[@ИльяКрасняк-ц8б]

Спасибо вам, Тимофей, за возможность поприсутствовать на лекции в МФТИ. То что вы делаете очень ценно.

[@8888UNIVERSE8888]

Великое вам спасибо за ваш труд!

[@volhak4519]

Присоединяюсь

[@Pupy2ru]

С удовольствие смотрю! Спасибо за лекции, за запись и монтаж! Нас этим алгоритмам и оптимизации кода учили на детском кружке Информатики и Вычислительной техники в советском "Дворце пионеров и школьников" в отношении популярных в 80-х Фокала, Паскаля и Бейсика. Алгоритмы и понимание работы ЭВМ первичны. Синтаксис - вторичен )

[@kurchiparchi]

Аплодирую стоя!!! Спасибо Вам, Тимофей Фёдорович! Еще ни раз пересмотрю Вашим суперские лекции!!! Всех Вам благ!!!!

[@SYVEX_IS_DEAD]

Во def count_sort(N): """"Сортировка подсчетом""" F = [0] * 10 A = [] for i in range(N): x = int(input()) F[x] += 1 for t in range(10): A += [t] * F[t] print(*F) return A print(count_sort(9))

[@shokoladnyysaray8149]

Мой вариант сортировки подсчетом: def counting_sort(A): """ Sorting list A of digits by counting """ # Frequency analysis F = [0]*10 for digit in A: F[digit] += 1 # Overwriting the initial list A *= 0 for digit in range(len(F)): A += [digit]*F[digit] A = [1, 2, 3, 5, 2, 7, 6, 0, 9, 9, 2, 8, 6, 3, 4, 1, 5, 2, 3, 7, 6, 6, 1] counting_sort(A)

[@SergeyChernetsky]

Тимофей, ваши лекции доставляют мне великую радость!)) Смотрю взахлёб! Спасибо вам огромное!

[@aleksandrpanibratenko5581]

Тимофей, спасибо вам за ваше, не побоюсь этого слова, "искусство" преподавания!

[@FedoskinYuriy]

Благодарю от души за ваш труд!!! Понятно, просто и по-человечески объясняете!!!

[@Alex-hh5oe]

B = [жесть * жесть for жесть in A if жесть % 2 == 0]

[@ИванДьяченко-ю5т]

Смотрю лекции и вижу, что человеку не хватает 1:20 что бы рассказать всё что он хочет. Видно что обладает большими знаниями и хочет ими делиться

[@alexanderkalinin1631]

Поправка в английских терминах: insert sort -> insertion sort choise sort -> правильно будет selection sort

[@gunfoogunfoo2287]

Просто у него не английский, это рунглиш. Так что всё верно. ChoiSe :)) «Чойси» это видимо кликуха прапорщика.

[@webkoth6105]

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

[@maisonmargiela7901]

просто надо меньше пить)

[@lotrand3880]

Как в аудитории "начали пропадать последние ряды", так и здесь: чем дальше, тем меньше просмотров. :D Мало людей вытягивает поток.

[@maxsergeevic1610]

людишки хотят кодить без понимания сути программирования ))

[@radunov.a]

@@maxsergeevic1610 может просто есть понимание, что там большой объем информации дается где-то за кадром, и тут вы получается смотришь не владея информацией. Даже в этом видео, там люди прошли массивы, не списки питона, а именно массивы как структура данных, а тут люди не получают этой информации и неизвестно какой еще. Вот и смысл смотреть по кусочкам пропуская базу?

[@chcklc]

Потрясающие уроки! огромное спасибо Тимофей!

[@Masya812]

Здраствуйте!!!Ваши лекции очень позновательны и легко воспринимаются!!!Спасибо за возможность их смотреть и питать информацию!

[@pavel_zosim]

Спасибо за великолепные лекции! Очень вдохновляют.

[@antontkachev4747]

в примере про солдат надо добавлять маленький комментарий "кто будет плохо учиться, тот скоро будет участвовать в такой сортировке вживую" :-)

[@AlexZener_66]

Кто в институт пролез, тот и армейку прокрутит на оси X.

[@maisonmargiela7901]

Чувак ты сначала ценники посмотри обучения в МФТИ , а теперь задай себе вопрос , будет ли для них проблемой твоя армия ? На бюджет тоже абы кого не берут...

[@SkromnyParen1]

@@maisonmargiela7901 около 300000руб в год. Для кого-то много, для кого-то мало

[@nskslant9304]

@@SkromnyParen1 у меня з.п в год 360к Так что много)

[@SkromnyParen1]

@@nskslant9304 у меня даже чуть меньше, чем у тебя, получается)

[@igor_karpov]

Тимофей Фёдорович, какой же вы умный преподаватель!)

[@ravabat5841]

Красава! Здоровья вам Тимофей!

[@searlasdeveloper7190]

18:00 начало обсуждения сортировок. Для тех кому пайтон не так важен, а важно само понимание алгоритмов.

[@АрсенКушнір-в2т]

Searlas Developer спасибо

[@vladivas5846]

Как интересно! Об алгоритмах: методами вставки и выбора. Интересные принципиальные подходы. Вставки: то, что отсортировано - это белый ящик(в фокусе/во внимании), не отсортировано - эдакий чёрный ящик (не в фокусе/не во внимании). Выбора: наоборот. То, что отсортировано - не нужно/не в фокусе/не во внимании, а то, что не отсортировано - во внимании.

[@nikiforvernidub7312]

Четко, классно, только вроде в англ литературе сортировка выбором это selection sort. Ну или хотя бы choiCe тогда. Спасибо за интересные лекции еще раз)

[@UTElistan]

Лектор настолько гениальный что небольшие ошибки в произношении и написании английских слов не имеют никакого значения. Simple вместо prime numbers, и т.п. не имеет никакого значения когда материал подается настолько хорошо.

[@StRanGerManY]

Да, уровень владения английским у этого преподавателя явно не Advanced, уже не первый раз это подмечаю. Тот же самый "аппенд", или "Инсерт", улыбнулся на этих моментах. Но это, безусловно, никоим образом не умаляет его как преподавателя! Главное, что он отлично знает свой материал, а что еще важнее, умеет его преподать так, чтобы даже самые ленивые или неодаренные студенты его восприняли - у него есть харизма. Смотрю паралеллельно лекции из MIT, там индус читает лекции, уже без такого энтузиазма и вовлечения аудитории. Правда, там и материал сложнее. Здесь все же на уровне 10-11го класса материал преподается

[@ulianaeskina9646]

Уважаемый Тимофей Фёдорович, большое спасибо Вам за этот проект и его доступность здесь! Ваши лекции -- это сплошное удовольствие, а продуманность задач (например, их автоматическая проверка и т.п.) вызывает особое восхищение. На всякий случай сообщу также, что (возможно) перестала корректно работать проверяющая система в заданиях к этой (6-й) неделе, для групп 737-738. Суть в том, что в условиях задач A и B указано, что формат входных данных -- три целых числа и три натуральных числа, соответственно; но, судя по данным проверяющей системы (которые можно посмотреть после отправки решения), после нескольких тестов с корректным форматом входных данных идут тесты с некорректным форматом входных данных. В итоге мои решения этих задач проходят лишь все тесты с верным форматом данных, и общий балл в таблице становится низкий. Впрочем, суть не в наборе максимального числа баллов (спасибо, что контесты с задачками и проверкой вообще доступны нам!..)), просто в идеале хотелось бы понять, почему сломалась часть тестов и насколько это затронуло дальнейшие задачи и контесты.

[@funtorm]

У тебя есть аккаунт?

[@bengurion3938]

Подскажите пожалуйста, как получить доступ к контесту?

[@левуспенский-ф7к]

У меня тоже некоторые ответы не засчитывает

[@РускийРапер]

Посещаемость не падает, а вот просмотри от лекции к лекции...))))

[@digitalfloret]

ну не узнают 0:52

[@ArtemBatalov]

Осмелюсь завить, но сортировка выбором не совсем верна. Результат конечно верный, но действия не те. Вы меняете каждый раз элементы местами, если они меньше текущего. Да в итоге минимальный будет на месте, но перелопатили мы весь список. Это замедляет работу алгоритма. Наша задача найти минимальный и потом только поменять его местами с текущим. for i in range(0, len(a) - 1): minimum = i for j in range(i, len(a)): if a[j] < a[minimum]: minimum = j a[i], a[minimum] = a[minimum], a[i]

[@titovcg]

Спасибо, очень интересно смотреть ваши лекции.

[@frost1437]

Спасибо за ваш огромный труд!

[@AnyKeySkywalker]

в названиях видосов было бы полезно добавлять тему лекции

[@МаринаЗиброва-с5с]

Тимофей Фёдорович - Лютик от программистов 🥰

[@akravchuk]

44:10 в сортировке выбором спадающая, а не возрастающая арифметическая прогрессия

[@w4keupneo]

Спасибо Вам еще раз!)

[@Discipline.Sanity.Liberty.]

Благодарю за лекцию!

[@mrSvob75A]

попытался воспроизвести в pythonista пример с сортировками. При попытке запуска, выдало ошибку на строке где описание второго теста. Это какая-то магия. Поменял местами условия для 2го и 3го тестов и все заработало!!!

[@СотникСотников-в1м]

1:03:07 Тимофей сейчас излагает ровно противоположный алгоритм, то есть ставит в начало строя самых высоких.

[@Леонид-с5з]

1:18:24 Я не понял, что будет если массив счётчиков заполнится (число заполненных элементов дойдёт до 10)? Как на практике данная функция продолжит выполнять поставленную на 1:16:02 задачу после переполнения массива? То есть как обеспечить, чтобы после того как ячейки счётчиков заполняться в первый раз, к ним же потом снова приплюсовывались новые значения, а не происходила перезапись?

[@adbln1]

Я реализовал это в коде следующим способом: from random import randint A = [0]*randint(50, 100) for k in range(0, len(A)): A[k] = randint(0, 9) print('Рандомный массив длинной {}: '.format(len(A)), A) F = [0]*10 for k in range(0, len(A)): F[A[k]] += 1 print('Количество одинаковых элементов: ', F) A = [0]*F[0] + [1]*F[1] + [2]*F[2] + [3]*F[3] + [4]*F[4] + [5]*F[5] + [6]*F[6] + [7]*F[7] + [8]*F[8] + [9]*F[9] print('Отсортированный массив длинной {}: '.format(len(A)), A) Сначала создаю массив А рандомной длинной (от 50 до 100). Потом пробегаюсь по нему и заполняю рандомно числами от 0 до 9. Далее делаю массив-счётчик F, длинной 10 и заполненный нулями. Далее - до этого допёр методом проб и ошибок - пробегаю по массиву А и каждому элементу F с индексом соответствующим значению A[k] прибавляю единичку. Это, собственно строчка F[A[k]] += 1 , допёр рисуя в тетради. Потом идёт некрасивая длинная строка создания нового массива А, по способу из начала лекции. Тут наверняка можно сделать красивее, но сейчас уже башка не варит) Ну и проверял я это визуально, что, конечно, неграмотно.

[@antonrosen5786]

Спасибо за труды!

[@kbkb5634]

Возможно неточность в реализации сортировки выбором. Здесь за один проход внутреннего цикла могут происходить обмены нескольких элементов. А должен быть только один обмен с минимумом.

[@user-ut1nc1ug2g]

и, правда, ошибка

[@AlexizDG]

Не согласен с 1:17:45 . Сортировка подсчетом может применяться на массивах с любыми значениями и любым их количеством даже заранее неизвестным, просто нужно массив частот сделать динамическим (точнее два массива частот для символов и самих частот) и при появлении нового элемента сортируемого массива добавлять его в массив частот. Да потом придется разбирать сам массив частот, но это не препятствие.

[@phibonacchi]

В питоне это проще сделать при помощи словаря, чтобы не создавать два массива, если я правильно вас понял. Либо увеличивать динамический массив частот сразу на число пропущенных номеров между новым и последним известным символами.

[@alexeybukach282]

Тимофей Федорович is The Best!

[@СотникСотников-в1м]

Замечания можно конечно сделать любому, но это лучший лектор, которого я видел. А замечания на самом деле простые. Мне кажется, что навык слушателя, к которому апеллирует лектор не успевает формироваться, и как следствие разрыв между лектором и слушателем наращивается. Если совсем просто, то лектор читает лекцию не для того, чтобы похвалиться своими знаниями, что бесспорно в случае с Тимофеем Хирьяновым, а для того, чтобы выработать практические навыки у слушателей. Но всё равно Тимофей отличный лектор.

[@violettafedotova7668]

In English these ones are correct: Insertion sort, Selection sort and Bubble sort.

[@nurlanbaliev5126]

я только учусь прог-ию и самое смешное, что вроде понятно и в тоже время ничего не понятно, а когда Тимофей обращается к залу с вопросом понятно ли им и они все молчат, я тоже сижу с квадратными глазами

[@lftf-beats]

"Тимофей Федорович мог налажать, но не налажал" )) а все благодаря тестирующей функции.

[@optimusprime9456]

Спасибо) P.s. ура! 6-я лекция, а я не среди отсеившихся!)

[@adbln1]

Последний метод сортировки смог реализовать в коде?

[@optimusprime9456]

@@adbln1 Ну как-то так) >>> arr = [1,2,3,5,2,7,6,0,9,9,2,8,6,3,4,1,5,2,3,7,6,6,1,3,5,2] >>> def sort(arr): result = [0]*10 for x in arr: result[x] += 1 for k in range(10): print("Number: ", k, ". Found: ", result[k], sep="") >>> sort(arr) Number: 0. Found: 1 Number: 1. Found: 3 Number: 2. Found: 5 Number: 3. Found: 4 Number: 4. Found: 1 Number: 5. Found: 3 Number: 6. Found: 4 Number: 7. Found: 2 Number: 8. Found: 1 Number: 9. Found: 2

[@MechTZ]

@@optimusprime9456 А отсортированный список то где?:)

[@salovafidi8913]

@@adbln1 def sort(arr,max_val): m = max_val+1 F = [0]*m for x in arr: F[x]+=1 i=0 for a in range (m): for c in range (F[a]): arr[i] = a i+=1 arr = [1,2,3,5,2,7,6,0,9,9,2,8,6,3,4,1,5,2,3,7,6,6,1,3,5,2] sort(arr,9) print(arr) подсмотрел решение, но полностью проанализировал и понял алгоритм. не сложно, но сам бы я не знаю сколько над этим думал(я про вторую часть)

[@ritsu133]

@@salovafidi8913 а почему без return? мне кажется как-то глупо писать функцию без этого, они для того и существуют, чтобы применять их в программном коде

[@СотникСотников-в1м]

1:08:07 Ошибка. Нужно вывести на print результаты тестирования и всё станет очевидным. Но Тимофей получает результат ОК , не подтверждённый визуальным подтверждением.

[@evaleks]

Так а в чем ошибка?

[@kvl5478]

Алгоритмы сортировки в танце. Шедевр :)))) kzbin.info

[@viewer_evgeniy]

Сортировка выбором (методом выбора) - selection sort. И не choise, а choice.

[@МихаилАлександрвич]

Сортировки kzbin.info/www/bejne/emLYZHtvlNygi7c Фёдорыч явно человек хороший, поэтому предположу что он не обидится если оставлю тут ссылку на его коллегу из Гарварда.

[@СергейСабуров-р9ж]

if __name__ == "__main__" - используется для того чтоб заснуть туда подпрограммы, которые выполняются при прямом компилировании файла библиотеки, но при импорте файла в другкю программу - эти подпрограммы не будут запущены автоматически. Не проверял еще можно ли импортить их принудительно типа from scriptname.py import test_sort

[@3405-j2w]

явно человек хороший! = Respect !!!

[@kneejerkreactor9100]

В "selection/choice sort" в позицию k можно просто ставить минимумы массивов [k+1, N], не нужно делать swap для каждой пары, где arr[k] > arr[j]

[@ВолодимирМороз-ш7с]

@up4k свап для каждой пары - это не метод вставки

[@h4rd1son]

очень хотелось бы походить на живые лекции к этому преподавателю, пока что лучше уроков на ютубе не встречал

[@kelavr8961]

Спасибо большое, очень интересно, Тимофей Федорович ❤

[@neverBsad]

List Comprehension можно было бы называть коллектором списка, по аналогии с Прологом.

[@СергейБыковский-ъ1ъ]

До 6й лекции не дошло и 10% тех, кто посмотрел первую...)

[@savel2work]

Как в жизни!

[@jointmeister]

Считай, что кто-то просто случайно зашел, кто-то просто из интереса, кто-то просто посчитал это скучным или не то, чего он ожидал. Посмотри на последние лекции по данной программе, там только 3-4% от тех, кто посмотрел 1 лекцию, из этого числа отними тех, кто просто случайно нажал и получишь очень маленькое количество.

[@rddimafaliush802]

@@jointmeister и это создаёт иллюзию переполненого рынка ИТ для многих

[@ritsu133]

@@jointmeister Заметил много комментариев, типа лектор говорит слишком много лишнего А что эти люди хотели, попав на лекцию для 1-курсников и даже не про программирование, а про АЛГОРИТМЫ? Считаю, что все правильно, информация должна быть разложена хоть и объемно, но ясно. Выучить синтаксис Python можно и зайдя на их офф. сайт, только вот толку от этого маловато

[@SergeyNicolayevich]

Не только дошел, но и много интересного законспектировал, хотя много лет работаю unix сисадмином и пишу на перле, баше и golang

[@digitalpetor]

20:15 роняет мел, 20:18 берет новый! Absolute MAD LAD!

[@Ольга-ж5к4й]

Ну тот скорее всего маленький был. Он оценил затраты/полезность поднятия старого мела и решил что взять новый - более рационально. Че тут MAD то?

[@6598335]

Так уже не первый раз! А зачем корчиться и мел поднимать, если это можно сделать потом?!

[@re0ista9ce]

Кто-нибудь смог запустить сортировку подсчетом со считыванием "х" с клавиатуры как это показано на 1:17:30, корректным циклом подсчета и выводом далее сортированного списка на экран? Как ни бился, у меня это сделать по примеру лектора на доске так и не получилось. Додумался я в конце концов сам, может вышло и не очень красиво, но в итоге массив сортируется и не просто выводится на экран, а формируется новый массив А, в котором цифры расположены упорядоченно, вот мой код: F = [0] * 10 # initial counters list = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for i in A: # unsorted A = [4, 2, 4, 2, 1, 3, 6, 7, 9, 3, 2, 5, 5, 5, 8, 0] F[i] += 1 # complete counters list = [1, 1, 3, 2, 2, 3, 1, 1, 1, 1] count = 0 index = 0 for digit in F: index += 1 for mult in range(digit): A[count] = index - 1 count += 1 return A # sorted A = [0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 7, 8, 9] Буду признателен, если кто-то покажет как это можно было сделать короче, но простыми функциями, НЕ используя методы!

[@zubrdens]

Задачи в практикуме вообще разноуровневые - есть на 5 минут, а есть и на 2 дня.

[@4INA_TTV]

почему бы не протестировать скорость выполнения сортировки с каждым методом ? в данном случае , естественно считать тысячные

[@ВладимирАндреев-ф6т]

Сортировка подсчётом, можете выложить решение? А, если на JavaScript сразу, было-бы супер)))

[@sorinrusu5311]

Важное замечание на счет скорости. Меня задело что прапорщик туповат и не помнит каких солдат сортировал и решил написать свой алгоритм. Спустя несколько часов пришел к хорошей (как я думал) формуле. Алгоритм оказался действительно быстрее. Но потом решил опробовать метод .sort() из стандартной библиотеки. Так вот он оказался на много милионов раз быстрее (такое ощущение что его писали на асемблере). Я обалдел. Есть над чем серьёзно задуматься. Результаты: buble_sort() 812 millisec. insert_sort() 703 millisec. choice_sort() 468 millisec. my_sort() 203 millisec. .sort() 0 nanosec. Это на списке из 2000 рандомных целых чисел. Каждая функция запускалась на отдельной копии этого списка. А вот моё блёклое творение def my_sort(A): N = len(A) for x in range(N-1): next_min = A[x] next_min_idx = x for y in range(x + 1, N): if A[y] < next_min: next_min_idx = y next_min = A[y] A[x], A[next_min_idx] = A[next_min_idx], A[x]

[@pand5461]

Это у вас та же сортировка выбором алгоритмически - нашли в подмассиве [i:len(A)] минимальный элемент, поставили на i-e место. Стандартная сортировка написана не на Python, поэтому очень много накладных расходов интерпретатора убирается, вот и быстрее. Ну и стандартный sort() работает по алгоритму со сложностью O(n*log n), а не O(n^2).

[@ImmortalBest]

начал читать книгу грокаем алгоритмы и случайно увидел данные лекции, само собой начал смотреть ) только все алгоритмы проецирую в языке C#

[@evergreenmouse7275]

та же история)) только на Swift вместе с питоном :)

[@SergeyFominVL]

Как книга?

[@lumeondatrackbeatstore1803]

Sergey Fomin Книга хороша,очень классно оформлена в плане визуала

[@Insidepointg]

Подскажите пожалуйста: Для чего в первом методе сортировки нужна переменная top? можно просто написать : for k in range(1, N): while k > 0 and A[k-1] > A[k]: A[k-1], A[k] = A[k], A[k-1] k -= 1 И все будет работь. Так для чего нам top не пойму. спасибо

[@golokwen7622]

Top указывает на индекс. Чтобы понять это я сделал это def insert_sort(A): N = len(A) for top in range(1, N): k = top print(k, 'цикл пошел') while k > 0 and A[k - 1] > A[k]: print(k, 'до отнятия') A[k], A[k - 1] = A[k - 1], A[k] k = k - 1 print(k, 'после отнятия') a = insert_sort([3, 2, 1])

[@vitek5660]

Сортировка вставками: в цикле while мы уменьшаем k(k-=1). Какой в этом смысл,если в цикле for k=top?

[@ДмитрийБогданов-б4я]

Вопрос возник 50:50 - последняя строка if name == "__main__": - что это? в программе не задано имя name. Достаёт какой то доп файл с функцией*? Вот учусь на программиста с дипломом техник технолог хлебопекарных производств))... Надеюсь за пол года осилю сие...

[@konstantinkozlov8086]

rtfm.co.ua/python-zachem-nuzhen-if-__name__-__main__/

[@Werumag]

Немного не понял, почему сортировка Insert делали через while, её же тоже можно сделать через два for, количество итераций всё равно таким же будет, но зато куда нагляднее.

[@Vlad-hk7ge]

Я конечно в этом не понимаю, первый раз вылетело новых видео.... Вот сейчас интересно- какое действие можно наблюдать на компе ...от этих действий которые описываются в этом видео?

[@BoldBass24]

Коммент в поддержку контента.

[@danbaal7242]

а можно как то решить задания,которые в контесте? Почему их скрыли(

[@nikberezovskiy]

У меня предложенный код сортировки вставками не работает с while k>-0, перекидывает в -1 эелемент. Все работает если k>=1 for top in range (1, n): k=top while k>=1 and a[k-1]>a[k]: a[k-1], a[k]=a[k], a[k-1] k-=1

[@ВолодимирМороз-ш7с]

Потому что это не метод вставки. В методе вставки соседние элементы местами не меняются. for i in range(0, n-1): ins = a[i] k = i while k >0 and a[k-1] > ins: a[j] = a[j - 1] #мы сдвигаем вправо, а не меняем местами j = j - 1 a[j] = ins # а теперь вставляем перед сдвинутой вправо часть массива

[@KananMammadli]

Забыл в сортировке пузырьком проверять если на каком-то значении bypass не было ни одной замены, то можно выходить из цикла.

[@development_edu]

Здравствуйте спасибо вам большое. Нет возможности получать логин и пароль для прохождения практики на сайте?

[@MrTimson85]

запускаю в визуал студио, ни чего не работает. в первой строке что-то еще наверное должно быть, пишет с def не может начинаться, синтаксическая ошибка

[@АшотКалайджян-н4я]

подскажите, пожалуста, в сортировке методом выбора, если убрать переменную N, а вместо нее везде подставить len(A), почему список не получается отсортированным?

[@БарноАбдуазимова-м4ж]

очень нужна помощь, смотрю ваши лекции, но пока не увидела раздела по тому, что мне не понятно, проблемы с пониманием счетчиков, counter(подсчет кол-ва) и total(вычисление суммы и произведения) и сигнальные метки (flag), можете посоветовать какую-то литературу, где я как новичок, смогу разобраться с этими вопросами???

[@bryanpantera]

связка топчик, спасибо

[@Feelosov]

Подскажите, я не понял. На 59:00 в сортировке вставкой вводится строка "for top in range(1,N):". Почему здесь "top" равен 5? Отсчет проходов идет в обратную сторону?

[@ignattalitskikh8104]

top не равен 5, N равен 5. top будет равен элементам арифметической прогрессии, генерируемой range(1,N), т.е.: 1, 2, 3, 4

[@Feelosov]

def insert_sort(A): """сортировка списка А вставками""" N = len(A) for top in range(1,N): k = top while k > 0 and A[k-1] > A[k]: A[k-1], A[k] = A[k], A[k-1] k -= 1 Тогда по вашим словам. Входные 4,2,5,1,3. На первой итерации while если top = 1, значит k = 1, значит меняются местами 4 и 2. Потом k -= 1, значит на второй итерации k = 0, тогда должна меняться местами 2 и [-1]-й элемент.... ааа все понял. Вот, когда начал отвечать увидел, что -1 не пройдет в while. Спасибо, Игнат. В общении рождается ответ.

[@Asylum_M]

Если ли тут кто-то осиливший задачку с шоколадкой из контеста? " Саша, не сделал домашнюю работу, зато купил шоколадку. И, по глупости, начал распечатывать ее прямо на уроке... Шелест золотинки услышала учительница. Она хотела вызвать в школу родителей, но Саша уговорил ее не вызывать их, а дать дополнительное задание. Учительница внимательно посмотрела на шоколадку (она была размером 3х4 плиток), разделила на кусочки по две плитки и угостила всех, кто сделал домашнюю работу. А Сашу попросила написать программу, которая определяет, сколько существует способов деления шоколадки размером 3×N плиток на кусочки по две плитки. Для выполнения задания Саше нужна помощь. Примечание: все плитки в шоколадке пронумерованы, поэтому способы деления, симметричные относительно точки или оси могут будут разными." Уже мозг себе сломал пытасясь вычислить алгоритм для расчёта

[@Asylum_M]

@@БакытжанАйса так они все тут есть: judge.mipt.ru/mipt_cs_on_python3/

[@bocik2854]

Ну как, справились?)Я решал без использования списков.

[@guideland1]

Тимофей, спасибо

[@frolovskii_v]

Эх попасть бы к вам на информатику... Учусь на geekbrains, но там и половины не понял того, что понял у вас. О comprehension вообще молчали

[@talivik]

Я тоже начинал учить на geeke. Очень плохо и скудно объясняют. Поэтому отказался от их услуг и вернул деньги.

[@frolovskii_v]

@@talivik ну сейчас у меня начинается основное обучение и информации куча, не знаю насколько она ценна и полна от лица профессионалов, но для меня очень много

[@antonvolkov8982]

Я чет не понял: чем сортировка вставками отличается от пузырьковой кроме направления движения по массиву?

[@vovach-m3b]

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

[@mikhailv1458]

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

[@adbln1]

Я реализовал это в коде следующим способом: from random import randint A = [0]*randint(50, 100) for k in range(0, len(A)): A[k] = randint(0, 9) print('Рандомный массив длинной {}: '.format(len(A)), A) F = [0]*10 for k in range(0, len(A)): F[A[k]] += 1 print('Количество одинаковых элементов: ', F) A = [0]*F[0] + [1]*F[1] + [2]*F[2] + [3]*F[3] + [4]*F[4] + [5]*F[5] + [6]*F[6] + [7]*F[7] + [8]*F[8] + [9]*F[9] print('Отсортированный массив длинной {}: '.format(len(A)), A)

[@dnssm7074]

A = [1,8,4,6,9,3,2,0,8,7,4,5,6,1,8,5,6,4,3,7,0,6,3,2,4,5,8,6,7,1,9,4,0,4,2,8,6,3,7,8,8,1] print(A) n = len(A) F = [0]*10 for i in range(n): x = A[i] F[x] += 1 A = [] for i in range(10): A =A + [i]*F[i] print(A) Получилась небольшая игра в гольф, но если добавить комментарии, то всё станет понятно. Хотя мне так больше нравится ;-)

[@dnssm7074]

А вот в виде готовой функции. Пользуйтесь кому надо ;-) def counting_sort(A): F = [0]*10 for i in range(len(A)): F[A[i]] += 1 A = [] for i in range(len(F)): A = A + [i]*F[i] print(A)

[@Maguar83]

@@dnssm7074 А тест показывает Fail, хотя выглядит 1 в 1 и типы одинаковые (int). Начал разбираться выяснил, что внутри функции сортировки массив А выглядит отсортированным, а внутри функции теста - нет. При том, что для других функций сортировки массив А внутри функции теста выглядит отсортированным. Т.е. функции сортировки передают отсортированный массив А, а функция сортировки подсчетом сортирует массив А, но возвращает исходный.

[@Maguar83]

вместо A=[] сделал A.clear() и всё заработало.

[@arustik7]

17:50 Я не понял откуда это следует. Почему 0 if x

[@kirrvin]

там должно быть b = [0 if x%2 != 0 else x**2 for x in a]

[@DaniilKustov]

У нас задача поставлена, если x меньше нуля, то вместо возведения в квадрат, писать 0, оттуда и пошло

[@igorbabyuk]

Огромное спасибо!

[@user-yi3px4rq6v]

Возможно как-то получить доступ к заданиям из контеста? Или обязательно надо быть студентом МФТИ?

[@pro100SOm]

Вначале удивился, почему Вы начали с сортировки вставками для квадратичных сортировок. Я обычно этой сортировкой закрываю "квадратичные" из тех соображений, что она при очень простом коде таки еще и применимая в некоторых задачах (или подзадачах). Но это вполне норм - различный порядок может быть уместен. Вопрос в другом: зачем Вы "гномика" назвали "сортировкой вставками"? Это очень похожие сортировки, но все же довольно значительно отличаются... Причем в некоторых моментах весьма принципиально отличаются...

[@lelelele1746]

Сортировка вставками показана верно, гномик может запустить счетчик назад, а здесь в приведенном алгоритме этого нет. Тимофей Федорович показал именно вариант сортировки вставками, а если вы не согласны, ждем ясных аргументов, ведь еще в первом вашем сообщении можно было избежать многозначительности, дав пояснение

[@Сергей_Петров_85]

t=32m42s choise sort По итерациям: 0 = [2, 4, 5, 1, 3]. Смотрим на 2. Минимальный из следующих = 1. Меняем местами. 1 = [1, 4, 5, 2, 3]. Смотрим на 4. Минимальный из следующих = 2. Меняем местами. 2 = [1, 2, 5, 4, 3]. Смотрим на 5. Минимальный из следующих = 3. Меняем местами. 3 = [1, 2, 3, 4, 5]. Конец В лекции по указанному таймингу почему-то на 3 итерации меняются местами 5 и 4, хотя должны были меняться 5 и 3. Или это я чего-то не понял, и лектор всё верно написал?

[@Cnd2Mn]

Алгоритм не идет дальше, встречает первое число меньше нужного и меняет сразу. Для вашего варианта нужно сначала отметить все числа меньше нужного, потом еще их между собой сравнить, чтобы определить наименьшее, и только потом менять, а это уже какой-то другой способ, возможно неэффективный.

[@tle4ajlbka375]

Можно ли увидеть задания из контеста?

[@stennick1237]

не факт то что вы искали, но тут есть практические работы judge.mipt.ru/mipt_cs_on_python3/

[@vasiliykosarev8473]

@@stennick1237 Супер!!! Спасибо огромное за ссылку!

[@dizogdizog2591]

@@stennick1237скажите пожалуйста а как туда попасть. Логин и пароль я вроде получил... Но не пускает (((

[@vladimirmashkov5194]

@@dizogdizog2591 смогли зайти? Меня тож не пускает

[@dizogdizog2591]

@@vladimirmashkov5194 нет (( с заданиями что то все туго. Может написать Тимофею. Он вроде не жадина

[@PimenovMA]

Ктонить пробовал это повторить? У меня выдает ошибку. Он в первую ячейку списка вставляет всё, что написано в квадратных скобках в виде текста.

[@_coffee42_]

Можно ли где-нибудь найти таблицу с планом?

[@osintervalproject5636]

но ведь последний элемент никуда не пропадает он остаётся в списке по сравнению с методом pop() A = [1, 2, 3, 4, 5, 7] n = len(A) n -= 1 x = A[n]

[@Berseny]

Total fail! =)) Это была мощная реализация! =)) Кодинг уровня "Бог". Нет, кроме шуток, очень любопытно.

[@denvanrain8793]

Обьясните пожалуйста, что означает sort_algoritm(A)? Это функция ,которая выступает в качестве параметра функции test_sort? Мы же ее не создавали.Никак не могу понять.Помогите разобраться откуда это взялось и что означает.

[@aargh95]

Это параметр для функции test_sort. И этим параметром является другая функция - одна из трёх сортировок. test_sort(insert_sort) #тут на вход функции test_sort поступает функция insert_sort То есть в этом вызове у нас вместо sort_algoritm будет insert_sort

[@psvvrn]

Это не функция, а имя функции. Интерпретатор питона по этому имени находит соответствующую функцию, и подставляет её при вызове sort_algoritm(A).

[@SkromnyParen1]

Почему у меня не доконца работает код на 17:24?

[@SkromnyParen1]

А именно, не возвращает нули в место отрицательных чисел(я добавлял в массив отрицатедьные числа)

[@mrSvob75A]

@@SkromnyParen1 у вас отрицательные цисла четные? Сейчас проверил. Все работает

[@SkromnyParen1]

@@mrSvob75A блин, уже не помню) Сейчас еще раз посмотрю

[@АлександрГаврилин-н3з]

Первый раз слышу мнение, что конструкция типа l = [x for x in seq] не является генератором... Изучал Python по Лутцу, так там чёрным по белому написано, что это самый простой генератор, применяющий метод __next__ к последовательности, производящий заданные вычисления и добавляющий значения в новый список.

[@OleksandrOmyshev]

более чем уверен что там были другие скобки (круглые), тогда это генераторное выражение. А конструкция типа l = [x for x in seq] не является генератором

[@АндрейАлексеев-х3д]

конструкция l = [x for x in seq] является присваиванием. конструкция [x for x in seq] является списком конструкция x for x in seq является генератором. Без круглых скобок она работать не будет, но эти скобки легко опускаются при наличии других скобок.

[@Ivan27a5]

Только что обратил внимание, что я тоже бородат и с длинными волосами, хотя у меня облысение посильнее выражено, кажется, не то, чтобы я на что-то конкретное указывал о Тимофее, просто, все мы лысеем так или иначе

[@ножикакхобби]

Прапорщик вставил новому солдату😂

[@pirat_ruda_makitra9500]

Глупо, наверно, но я хотел спросить правильно ли работает мой вариант сортировки методом пузырька. Может быть кто-то захочет посмотреть. Думал сам. def bubble_sort(A): """ сортировка списка А методом пузырька """ counter=0 #это счетчик, который проверяет, сколько раз прошли список N = len(A) while counter < N: for i in range(1, N): if A[i] < A[i-1]: A[i], A[i-1] = A[i-1], A[i] counter+=1 print(A)

[@Roiser101]

А ты сам-то его запускал? Сортировать он сортирует, только половину итераций делает впустую, т.к. уже все отсортировано - см. 43:20.