Алгоритмы на 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б]

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

[@kurchiparchi]

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

[@8888UNIVERSE8888]

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

[@volhak4519]

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

[@Pupy2ru]

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

[@SergeyChernetsky]

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

[@aleksandrpanibratenko5581]

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

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

[@Alex-hh5oe]

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

[@FedoskinYuriy]

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

[@webkoth6105]

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

[@maisonmargiela7901]

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

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

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

[@chcklc]

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

[@pavel_zosim]

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

[@lotrand3880]

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

[@maxsergeevic1610]

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

[@radunov.a]

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

[@Masya812]

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

[@alexanderkalinin1631]

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

[@gunfoogunfoo2287]

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

[@igor_karpov]

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

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

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

[@ravabat5841]

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

[@ulianaeskina9646]

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

[@funtorm]

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

[@bengurion3938]

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

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

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

[@vladivas5846]

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

[@antontkachev4747]

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

[@AlexZener_66]

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

[@maisonmargiela7901]

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

[@SkromnyParen1]

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

[@nskslant9304]

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

[@SkromnyParen1]

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

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

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

[@digitalfloret]

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

[@nikiforvernidub7312]

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

[@UTElistan]

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

[@StRanGerManY]

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

[@titovcg]

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

[@searlasdeveloper7190]

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

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

Searlas Developer спасибо

[@AnyKeySkywalker]

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

[@frost1437]

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

[@alexeybukach282]

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

[@kelavr8961]

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

[@w4keupneo]

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

[@Discipline.Sanity.Liberty.]

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

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

[@antonrosen5786]

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

[@3405-j2w]

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

[@mrSvob75A]

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

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

[@digitalpetor]

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

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

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

[@6598335]

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

[@h4rd1son]

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

[@lftf-beats]

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

[@nurlanbaliev5126]

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

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

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

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

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

[@savel2work]

Как в жизни!

[@jointmeister]

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

[@rddimafaliush802]

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

[@ritsu133]

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

[@SergeyNicolayevich]

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

[@violettafedotova7668]

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

[@akravchuk]

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

[@kbkb5634]

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

[@user-ut1nc1ug2g]

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

[@kvl5478]

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

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

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

[@viewer_evgeniy]

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

[@kneejerkreactor9100]

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

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

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

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

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

[@ImmortalBest]

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

[@evergreenmouse7275]

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

[@SergeyFominVL]

Как книга?

[@lumeondatrackbeatstore1803]

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

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

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

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

[@bryanpantera]

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

[@neverBsad]

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

[@BoldBass24]

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

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

[@zubrdens]

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

[@danbaal7242]

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

[@4INA_TTV]

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

[@development_edu]

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

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

[@guideland1]

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

[@tle4ajlbka375]

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

[@stennick1237]

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

[@vasiliykosarev8473]

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

[@dizogdizog2591]

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

[@vladimirmashkov5194]

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

[@dizogdizog2591]

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

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

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

[@AlexizDG]

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

[@phibonacchi]

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

[@vitek5660]

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

[@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 # а теперь вставляем перед сдвинутой вправо часть массива

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

[@Vlad-hk7ge]

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

[@igorbabyuk]

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

[@_coffee42_]

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

[@MrTimson85]

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

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

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

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

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

[@Berseny]

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

[@frolovskii_v]

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

[@talivik]

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

[@frolovskii_v]

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

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

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

[@konstantinkozlov8086]

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

[@antonvolkov8982]

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

[@vovach-m3b]

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

[@user-yi3px4rq6v]

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

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

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

[@evaleks]

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

[@zl0y]

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

[@adbln1]

Оператор

[@Asylum_M]

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

[@Asylum_M]

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

[@bocik2854]

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

[@МихаилКрутый-ц7з]

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

[@yevhenukrainianer4781]

не реклама. Но по пайтону я проходил на prometheus курсы. Открытая рег-я, б/платные сертификаты. Но в этой лекции Тимофей Федорович больше учит программированию, чем только пайтон. И за это невыразимое спс. Вобщем совмещайте.

[@4INA_TTV]

hack

[@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. Спасибо, Игнат. В общении рождается ответ.

[@userw8331]

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

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

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

[@SkromnyParen1]

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

[@SkromnyParen1]

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

[@mrSvob75A]

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

[@SkromnyParen1]

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

[@РоРо-ш8ч]

Test Driven Development это круто!

[@PimenovMA]

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

[@VladArnoldner]

Спасибо

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

[@Werumag]

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

[@Black_Cat_295]

01:08:00

[@marines8725]

спасибо!

[@umbopoua745]

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

[@ruslangit9752]

не совсем понял, зачем в алгоритме подсчетом вводится оператор input, что должен вводить пользователь?

[@ruslangit9752]

это в самом конце, за две минуты до окончания

[@mini_clop]

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