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

Практика: judge.mipt.ru/m...
Telegram-группа: t.me/tkhiriano...
Спонсировать: / tkhirianov или www.paypal.me/...
курс: Информатика. Алгоритмы и структуры данных на Python 3.
лектор: Хирьянов Тимофей Фёдорович
10.10.2017
Темы, рассмотренные на лекции №6:
- Методы append(), pop() и функция len() для списка.
- Списковые включения.
- Мастер-класс по TDD.
- Сортировка вставками.
- Сортировка выбором.
- Сортировка методом пузырька.
- Сортировка подсчётом.

[@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 лет после окончания университета есть подобные видео, с такими профессионалами, с которыми учиться стало интересно, чего увы не было на моих парах.

[@lotrand3880]

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

[@maxsergeevic1610]

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

[@radunov.a]

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

[@8888UNIVERSE8888]

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

[@volhak4519]

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

[@user-mr1ii2wn2w]

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

[@antontkachev4747]

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

[@AlexZener_66]

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

[@maisonmargiela7901]

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

[@SkromnyParen95]

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

[@nskslant9304]

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

[@SkromnyParen95]

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

[@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)

[@Pupy2ru]

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

[@Alex-hh5oe]

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

[@webkoth6105]

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

[@maisonmargiela7901]

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

[@SergeyChernetsky]

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

[@tL0n_ExZ]

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

[@alexanderkalinin1631]

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

[@gunfoogunfoo2287]

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

[@user-sv6bw6tk4s]

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

[@aleksandrpanibratenko5581]

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

[@FedoskinYuriy]

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

[@nikiforvernidub7312]

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

[@UTElistan]

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

[@StRanGerManY]

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

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

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

[@digitalfloret]

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

[@igor_karpov]

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

[@ravabat5841]

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

[@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) подсмотрел решение, но полностью проанализировал и понял алгоритм. не сложно, но сам бы я не знаю сколько над этим думал(я про вторую часть)

[@c7rsed118]

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

[@Masya812]

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

[@AnyKeySkywalker]

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

[@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]

[@ulianaeskina9646]

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

[@darmoed_phantorm]

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

[@bengurion3938]

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

[@user-kz7tm8hz1n]

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

[@vladivas5846]

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

[@mrSvob75A]

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

[@user-pc9wq8ke1s]

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

[@frost1437]

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

[@user-jm5or1dm7s]

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

[@Discipline.Sanity.Liberty.]

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

[@titovcg]

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

[@w4keupneo]

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

[@nurlanbaliev5126]

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

[@kelavr8961]

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

[@h4rd1son]

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

[@lftf-beats]

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

[@lsam9766]

Квадратичные сортировки: Сортировка вставками 22:04, реализация 59:35 Сортировка выбора 26:53, реализация 1:05:59 Пузырьковая сортировка 35:10, реализация 1:08:03

[@antonrosen5786]

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

[@viewer_evgeniy]

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

[@kbkb5634]

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

[@user-ut1nc1ug2g]

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

[@kvl5478]

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

[@violettafedotova7668]

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

[@alexeybukach282]

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

[@searlasdeveloper7190]

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

[@user-rw8ki5pq4l]

Searlas Developer спасибо

[@user-pt7lu7cd7c]

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

[@savel2work]

Как в жизни!

[@jointmeister]

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

[@rddimafaliush802]

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

[@c7rsed118]

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

[@SergeyNicolayevich]

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

[@ImmortalBest]

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

[@evergreenmouse7275]

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

[@SergeyFominVL]

Как книга?

[@lumeondatrackbeatstore1803]

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

[@user-zf4pm4ky1r]

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

[@user-zl2ej8nr1i]

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

[@kneejerkreactor9100]

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

[@user-jo2hd5dj5o]

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

[@user-zd4vo1vy8u]

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

[@neverBsad]

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

[@digitalpetor]

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

[@user-uu3us9ys4q]

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

[@6598335]

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

[@zubrdens]

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

[@akravchuk]

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

[@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).

[@user-qz3xt6ko5c]

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

[@AlexizDG]

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

[@phibonacchi]

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

[@bryanpantera]

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

[@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])

[@user-pc9wq8ke1s]

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

[@Asylum_M]

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

[@Asylum_M]

@@user-zn6rh1tu6r так они все тут есть: judge.mipt.ru/mipt_cs_on_python3/

[@bocik2854]

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

[@user-iz9sj1nn5q]

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 , допёр рисуя в тетради. Потом идёт некрасивая длинная строка создания нового массива А, по способу из начала лекции. Тут наверняка можно сделать красивее, но сейчас уже башка не варит) Ну и проверял я это визуально, что, конечно, неграмотно.

[@BoldBass24]

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

[@Berseny]

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

[@vitek5660]

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

[@user-pc9wq8ke1s]

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

[@evaleks]

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

[@frolovskii_v]

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

[@talivik]

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

[@frolovskii_v]

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

[@ChiNANANANA]

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

[@Werumag]

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

[@guideland1]

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

[@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

[@user-jo2hd5dj5o]

Потому что это не метод вставки. В методе вставки соседние элементы местами не меняются. 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 # а теперь вставляем перед сдвинутой вправо часть массива

[@igorbabyuk]

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

[@Vlad-hk7ge]

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

[@Ivan27a5]

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

[@user-mm3gq2zt5g]

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

[@KananMammadli]

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

[@userw8331]

Кто напомнит, тот получит))

[@Сергей_Петров_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]

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

[@development_edu]

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

[@user-ht3gi5qk5x]

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

[@barkas2589]

Спасибо

[@MrTimson85]

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

[@pro100SOm]

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

[@lelelele1746]

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

[@danbaal7242]

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

[@marines8725]

спасибо!

[@igoryagiyaev]

Спасибо!

[@UrTa91]

26:15 солдат строят от высокого к низким )))

[@cuckoops]

Не понимаю, почему при массив A изменяется, хотя функции сортировки не возвращают отсортированный список? По идее массив А, который задаётся вне функции сортировки не должен быть равен массиву А внутри функции, это могли бы быть две разные буквы.

[@Roiser101]

Так и есть. Это работает в нелокальной области видимости переменной. Вызовите функцию sort_insert(Z) для глобальной переменной и она вернет None. Для использования написанных функций надо return писать...(наверное! Я сам новичок)

[@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() и всё заработало.

[@user-cx4qg2kh5x]

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

[@konstantinkozlov8086]

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

[@PROPHESSOR]

Selection sort

[@umbopoua745]

Эххх, еще бы контесты и лабы получить )))

[@user-hw5ww2mp7c]

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

[@OleksandrOmyshev]

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

[@user-pw9sn6ih9e]

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

[@antonvolkov8982]

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

[@vovach-m3b]

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

[@osintervalproject5636]

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

[@daredeviii6865]

Было бы круто добавить бота с тайм кодами на рассматриваемые темы, либо кто не поленится ручками прописать - плюс с карму

[@user-yi3px4rq6v]

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

[@user-ns4mz8ei6g]

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

[@zl0y]

Всё хорошо! Классные видео. ВОПРОС кто двигает камеру???

[@adbln1]

Оператор