Тайм-коды: Сортировки, объект 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 частотный анализ
До чего же крутой преподаватель. Глаза горят, как у ребёнка в начт на 31 декабря. Мысли порой путаются от возбуждения. Хочет все и сразу рассказать, а пара всего 1.20 и не уместить все то, что так хотелось. Рад, что спустя 20 лет после окончания университета есть подобные видео, с такими профессионалами, с которыми учиться стало интересно, чего увы не было на моих парах.
С удовольствие смотрю! Спасибо за лекции, за запись и монтаж! Нас этим алгоритмам и оптимизации кода учили на детском кружке Информатики и Вычислительной техники в советском "Дворце пионеров и школьников" в отношении популярных в 80-х Фокала, Паскаля и Бейсика. Алгоритмы и понимание работы ЭВМ первичны. Синтаксис - вторичен )
@@maxsergeevic1610 может просто есть понимание, что там большой объем информации дается где-то за кадром, и тут вы получается смотришь не владея информацией. Даже в этом видео, там люди прошли массивы, не списки питона, а именно массивы как структура данных, а тут люди не получают этой информации и неизвестно какой еще. Вот и смысл смотреть по кусочкам пропуская базу?
Во 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))
Мой вариант сортировки подсчетом: 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)
у меня аж в макушке так приятно заболело, по ходу нейроны формируются. Подача материала отличная. Делал сортировку раз тридцать, а тут я именно понял как она работает.
Чувак ты сначала ценники посмотри обучения в МФТИ , а теперь задай себе вопрос , будет ли для них проблемой твоя армия ? На бюджет тоже абы кого не берут...
Уважаемый Тимофей Фёдорович, большое спасибо Вам за этот проект и его доступность здесь! Ваши лекции -- это сплошное удовольствие, а продуманность задач (например, их автоматическая проверка и т.п.) вызывает особое восхищение. На всякий случай сообщу также, что (возможно) перестала корректно работать проверяющая система в заданиях к этой (6-й) неделе, для групп 737-738. Суть в том, что в условиях задач A и B указано, что формат входных данных -- три целых числа и три натуральных числа, соответственно; но, судя по данным проверяющей системы (которые можно посмотреть после отправки решения), после нескольких тестов с корректным форматом входных данных идут тесты с некорректным форматом входных данных. В итоге мои решения этих задач проходят лишь все тесты с верным форматом данных, и общий балл в таблице становится низкий. Впрочем, суть не в наборе максимального числа баллов (спасибо, что контесты с задачками и проверкой вообще доступны нам!..)), просто в идеале хотелось бы понять, почему сломалась часть тестов и насколько это затронуло дальнейшие задачи и контесты.
Как интересно! Об алгоритмах: методами вставки и выбора. Интересные принципиальные подходы. Вставки: то, что отсортировано - это белый ящик(в фокусе/во внимании), не отсортировано - эдакий чёрный ящик (не в фокусе/не во внимании). Выбора: наоборот. То, что отсортировано - не нужно/не в фокусе/не во внимании, а то, что не отсортировано - во внимании.
Четко, классно, только вроде в англ литературе сортировка выбором это selection sort. Ну или хотя бы choiCe тогда. Спасибо за интересные лекции еще раз)
Лектор настолько гениальный что небольшие ошибки в произношении и написании английских слов не имеют никакого значения. Simple вместо prime numbers, и т.п. не имеет никакого значения когда материал подается настолько хорошо.
Да, уровень владения английским у этого преподавателя явно не Advanced, уже не первый раз это подмечаю. Тот же самый "аппенд", или "Инсерт", улыбнулся на этих моментах. Но это, безусловно, никоим образом не умаляет его как преподавателя! Главное, что он отлично знает свой материал, а что еще важнее, умеет его преподать так, чтобы даже самые ленивые или неодаренные студенты его восприняли - у него есть харизма. Смотрю паралеллельно лекции из MIT, там индус читает лекции, уже без такого энтузиазма и вовлечения аудитории. Правда, там и материал сложнее. Здесь все же на уровне 10-11го класса материал преподается
@@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) подсмотрел решение, но полностью проанализировал и понял алгоритм. не сложно, но сам бы я не знаю сколько над этим думал(я про вторую часть)
@@salovafidi8913 а почему без return? мне кажется как-то глупо писать функцию без этого, они для того и существуют, чтобы применять их в программном коде
попытался воспроизвести в pythonista пример с сортировками. При попытке запуска, выдало ошибку на строке где описание второго теста. Это какая-то магия. Поменял местами условия для 2го и 3го тестов и все заработало!!!
1:18:24 Я не понял, что будет если массив счётчиков заполнится (число заполненных элементов дойдёт до 10)? Как на практике данная функция продолжит выполнять поставленную на 1:16:02 задачу после переполнения массива? То есть как обеспечить, чтобы после того как ячейки счётчиков заполняться в первый раз, к ним же потом снова приплюсовывались новые значения, а не происходила перезапись?
Я реализовал это в коде следующим способом: 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 , допёр рисуя в тетради. Потом идёт некрасивая длинная строка создания нового массива А, по способу из начала лекции. Тут наверняка можно сделать красивее, но сейчас уже башка не варит) Ну и проверял я это визуально, что, конечно, неграмотно.
я только учусь прог-ию и самое смешное, что вроде понятно и в тоже время ничего не понятно, а когда Тимофей обращается к залу с вопросом понятно ли им и они все молчат, я тоже сижу с квадратными глазами
Осмелюсь завить, но сортировка выбором не совсем верна. Результат конечно верный, но действия не те. Вы меняете каждый раз элементы местами, если они меньше текущего. Да в итоге минимальный будет на месте, но перелопатили мы весь список. Это замедляет работу алгоритма. Наша задача найти минимальный и потом только поменять его местами с текущим. 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]
Возможно неточность в реализации сортировки выбором. Здесь за один проход внутреннего цикла могут происходить обмены нескольких элементов. А должен быть только один обмен с минимумом.
Не согласен с 1:17:45 . Сортировка подсчетом может применяться на массивах с любыми значениями и любым их количеством даже заранее неизвестным, просто нужно массив частот сделать динамическим (точнее два массива частот для символов и самих частот) и при появлении нового элемента сортируемого массива добавлять его в массив частот. Да потом придется разбирать сам массив частот, но это не препятствие.
В питоне это проще сделать при помощи словаря, чтобы не создавать два массива, если я правильно вас понял. Либо увеличивать динамический массив частот сразу на число пропущенных номеров между новым и последним известным символами.
if __name__ == "__main__" - используется для того чтоб заснуть туда подпрограммы, которые выполняются при прямом компилировании файла библиотеки, но при импорте файла в другкю программу - эти подпрограммы не будут запущены автоматически. Не проверял еще можно ли импортить их принудительно типа from scriptname.py import test_sort
Подскажите пожалуйста: Для чего в первом методе сортировки нужна переменная 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 не пойму. спасибо
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])
Сортировки th-cam.com/video/D1u3H9_wmUU/w-d-xo.html Фёдорыч явно человек хороший, поэтому предположу что он не обидится если оставлю тут ссылку на его коллегу из Гарварда.
Считай, что кто-то просто случайно зашел, кто-то просто из интереса, кто-то просто посчитал это скучным или не то, чего он ожидал. Посмотри на последние лекции по данной программе, там только 3-4% от тех, кто посмотрел 1 лекцию, из этого числа отними тех, кто просто случайно нажал и получишь очень маленькое количество.
@@jointmeister Заметил много комментариев, типа лектор говорит слишком много лишнего А что эти люди хотели, попав на лекцию для 1-курсников и даже не про программирование, а про АЛГОРИТМЫ? Считаю, что все правильно, информация должна быть разложена хоть и объемно, но ясно. Выучить синтаксис Python можно и зайдя на их офф. сайт, только вот толку от этого маловато
Замечания можно конечно сделать любому, но это лучший лектор, которого я видел. А замечания на самом деле простые. Мне кажется, что навык слушателя, к которому апеллирует лектор не успевает формироваться, и как следствие разрыв между лектором и слушателем наращивается. Если совсем просто, то лектор читает лекцию не для того, чтобы похвалиться своими знаниями, что бесспорно в случае с Тимофеем Хирьяновым, а для того, чтобы выработать практические навыки у слушателей. Но всё равно Тимофей отличный лектор.
Вопрос возник 50:50 - последняя строка if name == "__main__": - что это? в программе не задано имя name. Достаёт какой то доп файл с функцией*? Вот учусь на программиста с дипломом техник технолог хлебопекарных производств))... Надеюсь за пол года осилю сие...
1:08:07 Ошибка. Нужно вывести на print результаты тестирования и всё станет очевидным. Но Тимофей получает результат ОК , не подтверждённый визуальным подтверждением.
Я реализовал это в коде следующим способом: 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)
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) Получилась небольшая игра в гольф, но если добавить комментарии, то всё станет понятно. Хотя мне так больше нравится ;-)
А вот в виде готовой функции. Пользуйтесь кому надо ;-) 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)
@@dnssm7074 А тест показывает Fail, хотя выглядит 1 в 1 и типы одинаковые (int). Начал разбираться выяснил, что внутри функции сортировки массив А выглядит отсортированным, а внутри функции теста - нет. При том, что для других функций сортировки массив А внутри функции теста выглядит отсортированным. Т.е. функции сортировки передают отсортированный массив А, а функция сортировки подсчетом сортирует массив А, но возвращает исходный.
Я конечно в этом не понимаю, первый раз вылетело новых видео.... Вот сейчас интересно- какое действие можно наблюдать на компе ...от этих действий которые описываются в этом видео?
подскажите, пожалуста, в сортировке методом выбора, если убрать переменную N, а вместо нее везде подставить len(A), почему список не получается отсортированным?
Кто-нибудь смог запустить сортировку подсчетом со считыванием "х" с клавиатуры как это показано на 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] Буду признателен, если кто-то покажет как это можно было сделать короче, но простыми функциями, НЕ используя методы!
очень нужна помощь, смотрю ваши лекции, но пока не увидела раздела по тому, что мне не понятно, проблемы с пониманием счетчиков, counter(подсчет кол-ва) и total(вычисление суммы и произведения) и сигнальные метки (flag), можете посоветовать какую-то литературу, где я как новичок, смогу разобраться с этими вопросами???
У меня предложенный код сортировки вставками не работает с 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
Потому что это не метод вставки. В методе вставки соседние элементы местами не меняются. 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 # а теперь вставляем перед сдвинутой вправо часть массива
Подскажите, я не понял. На 59:00 в сортировке вставкой вводится строка "for top in range(1,N):". Почему здесь "top" равен 5? Отсчет проходов идет в обратную сторону?
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. Спасибо, Игнат. В общении рождается ответ.
Обьясните пожалуйста, что означает sort_algoritm(A)? Это функция ,которая выступает в качестве параметра функции test_sort? Мы же ее не создавали.Никак не могу понять.Помогите разобраться откуда это взялось и что означает.
Это параметр для функции test_sort. И этим параметром является другая функция - одна из трёх сортировок. test_sort(insert_sort) #тут на вход функции test_sort поступает функция insert_sort То есть в этом вызове у нас вместо sort_algoritm будет insert_sort
не реклама. Но по пайтону я проходил на prometheus курсы. Открытая рег-я, б/платные сертификаты. Но в этой лекции Тимофей Федорович больше учит программированию, чем только пайтон. И за это невыразимое спс. Вобщем совмещайте.
@@talivik ну сейчас у меня начинается основное обучение и информации куча, не знаю насколько она ценна и полна от лица профессионалов, но для меня очень много
Важное замечание на счет скорости. Меня задело что прапорщик туповат и не помнит каких солдат сортировал и решил написать свой алгоритм. Спустя несколько часов пришел к хорошей (как я думал) формуле. Алгоритм оказался действительно быстрее. Но потом решил опробовать метод .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]
Это у вас та же сортировка выбором алгоритмически - нашли в подмассиве [i:len(A)] минимальный элемент, поставили на i-e место. Стандартная сортировка написана не на Python, поэтому очень много накладных расходов интерпретатора убирается, вот и быстрее. Ну и стандартный sort() работает по алгоритму со сложностью O(n*log n), а не O(n^2).
Ставим столько коробочек сколько самая большая гиря весит (10 кг - 10 коробок). Бежим вдоль ряда с гирями. Сколько гиря весит (3 кг) в ту коробку (коробка №3) кидаем печенку. Потом бежим вдоль наших коробок. Если в коробке есть печенки, то печатаем номер коробки столько раз сколько в ней печенек.
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. Или это я чего-то не понял, и лектор всё верно написал?
Алгоритм не идет дальше, встречает первое число меньше нужного и меняет сразу. Для вашего варианта нужно сначала отметить все числа меньше нужного, потом еще их между собой сравнить, чтобы определить наименьшее, и только потом менять, а это уже какой-то другой способ, возможно неэффективный.
Тайм-коды: Сортировки, объект 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 частотный анализ
спасибо!
До чего же крутой преподаватель. Глаза горят, как у ребёнка в начт на 31 декабря. Мысли порой путаются от возбуждения. Хочет все и сразу рассказать, а пара всего 1.20 и не уместить все то, что так хотелось.
Рад, что спустя 20 лет после окончания университета есть подобные видео, с такими профессионалами, с которыми учиться стало интересно, чего увы не было на моих парах.
Спасибо вам, Тимофей, за возможность поприсутствовать на лекции в МФТИ. То что вы делаете очень ценно.
С удовольствие смотрю! Спасибо за лекции, за запись и монтаж!
Нас этим алгоритмам и оптимизации кода учили на детском кружке Информатики и Вычислительной техники в советском "Дворце пионеров и школьников" в отношении популярных в 80-х Фокала, Паскаля и Бейсика.
Алгоритмы и понимание работы ЭВМ первичны. Синтаксис - вторичен )
Великое вам спасибо за ваш труд!
Присоединяюсь
Аплодирую стоя!!! Спасибо Вам, Тимофей Фёдорович! Еще ни раз пересмотрю Вашим суперские лекции!!! Всех Вам благ!!!!
Смотрю лекции и вижу, что человеку не хватает 1:20 что бы рассказать всё что он хочет. Видно что обладает большими знаниями и хочет ими делиться
Как в аудитории "начали пропадать последние ряды", так и здесь: чем дальше, тем меньше просмотров. :D
Мало людей вытягивает поток.
людишки хотят кодить без понимания сути программирования ))
@@maxsergeevic1610 может просто есть понимание, что там большой объем информации дается где-то за кадром, и тут вы получается смотришь не владея информацией. Даже в этом видео, там люди прошли массивы, не списки питона, а именно массивы как структура данных, а тут люди не получают этой информации и неизвестно какой еще. Вот и смысл смотреть по кусочкам пропуская базу?
Тимофей, ваши лекции доставляют мне великую радость!)) Смотрю взахлёб! Спасибо вам огромное!
Во
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))
Мой вариант сортировки подсчетом:
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)
Посещаемость не падает, а вот просмотри от лекции к лекции...))))
ну не узнают 0:52
Тимофей, спасибо вам за ваше, не побоюсь этого слова, "искусство" преподавания!
у меня аж в макушке так приятно заболело, по ходу нейроны формируются. Подача материала отличная. Делал сортировку раз тридцать, а тут я именно понял как она работает.
просто надо меньше пить)
Благодарю от души за ваш труд!!! Понятно, просто и по-человечески объясняете!!!
B = [жесть * жесть for жесть in A if жесть % 2 == 0]
в примере про солдат надо добавлять маленький комментарий "кто будет плохо учиться, тот скоро будет участвовать в такой сортировке вживую" :-)
Кто в институт пролез, тот и армейку прокрутит на оси X.
Чувак ты сначала ценники посмотри обучения в МФТИ , а теперь задай себе вопрос , будет ли для них проблемой твоя армия ? На бюджет тоже абы кого не берут...
@@maisonmargiela7901 около 300000руб в год. Для кого-то много, для кого-то мало
@@SkromnyParen1 у меня з.п в год 360к
Так что много)
@@nskslant9304 у меня даже чуть меньше, чем у тебя, получается)
Потрясающие уроки! огромное спасибо Тимофей!
Поправка в английских терминах:
insert sort -> insertion sort
choise sort -> правильно будет selection sort
Просто у него не английский, это рунглиш. Так что всё верно. ChoiSe :)) «Чойси» это видимо кликуха прапорщика.
Здраствуйте!!!Ваши лекции очень позновательны и легко воспринимаются!!!Спасибо за возможность их смотреть и питать информацию!
Спасибо за великолепные лекции! Очень вдохновляют.
Тимофей Фёдорович, какой же вы умный преподаватель!)
Красава! Здоровья вам Тимофей!
18:00 начало обсуждения сортировок. Для тех кому пайтон не так важен, а важно само понимание алгоритмов.
Searlas Developer спасибо
Уважаемый Тимофей Фёдорович, большое спасибо Вам за этот проект и его доступность здесь! Ваши лекции -- это сплошное удовольствие, а продуманность задач (например, их автоматическая проверка и т.п.) вызывает особое восхищение.
На всякий случай сообщу также, что (возможно) перестала корректно работать проверяющая система в заданиях к этой (6-й) неделе, для групп 737-738. Суть в том, что в условиях задач A и B указано, что формат входных данных -- три целых числа и три натуральных числа, соответственно; но, судя по данным проверяющей системы (которые можно посмотреть после отправки решения), после нескольких тестов с корректным форматом входных данных идут тесты с некорректным форматом входных данных. В итоге мои решения этих задач проходят лишь все тесты с верным форматом данных, и общий балл в таблице становится низкий.
Впрочем, суть не в наборе максимального числа баллов (спасибо, что контесты с задачками и проверкой вообще доступны нам!..)), просто в идеале хотелось бы понять, почему сломалась часть тестов и насколько это затронуло дальнейшие задачи и контесты.
У тебя есть аккаунт?
Подскажите пожалуйста, как получить доступ к контесту?
У меня тоже некоторые ответы не засчитывает
Как интересно!
Об алгоритмах: методами вставки и выбора. Интересные принципиальные подходы. Вставки: то, что отсортировано - это белый ящик(в фокусе/во внимании), не отсортировано - эдакий чёрный ящик (не в фокусе/не во внимании). Выбора: наоборот. То, что отсортировано - не нужно/не в фокусе/не во внимании, а то, что не отсортировано - во внимании.
Четко, классно, только вроде в англ литературе сортировка выбором это selection sort. Ну или хотя бы choiCe тогда. Спасибо за интересные лекции еще раз)
Лектор настолько гениальный что небольшие ошибки в произношении и написании английских слов не имеют никакого значения. Simple вместо prime numbers, и т.п. не имеет никакого значения когда материал подается настолько хорошо.
Да, уровень владения английским у этого преподавателя явно не Advanced, уже не первый раз это подмечаю. Тот же самый "аппенд", или "Инсерт", улыбнулся на этих моментах. Но это, безусловно, никоим образом не умаляет его как преподавателя! Главное, что он отлично знает свой материал, а что еще важнее, умеет его преподать так, чтобы даже самые ленивые или неодаренные студенты его восприняли - у него есть харизма. Смотрю паралеллельно лекции из MIT, там индус читает лекции, уже без такого энтузиазма и вовлечения аудитории. Правда, там и материал сложнее. Здесь все же на уровне 10-11го класса материал преподается
Тимофей Фёдорович - Лютик от программистов 🥰
44:10 в сортировке выбором спадающая, а не возрастающая арифметическая прогрессия
Благодарю за лекцию!
Спасибо)
P.s. ура! 6-я лекция, а я не среди отсеившихся!)
Последний метод сортировки смог реализовать в коде?
@@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
@@optimusprime9456 А отсортированный список то где?:)
@@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)
подсмотрел решение, но полностью проанализировал и понял алгоритм. не сложно, но сам бы я не знаю сколько над этим думал(я про вторую часть)
@@salovafidi8913 а почему без return?
мне кажется как-то глупо писать функцию без этого, они для того и существуют, чтобы применять их в программном коде
попытался воспроизвести в pythonista пример с сортировками. При попытке запуска, выдало ошибку на строке где описание второго теста. Это какая-то магия. Поменял местами условия для 2го и 3го тестов и все заработало!!!
1:18:24 Я не понял, что будет если массив счётчиков заполнится (число заполненных элементов дойдёт до 10)? Как на практике данная функция продолжит выполнять поставленную на 1:16:02 задачу после переполнения массива? То есть как обеспечить, чтобы после того как ячейки счётчиков заполняться в первый раз, к ним же потом снова приплюсовывались новые значения, а не происходила перезапись?
Я реализовал это в коде следующим способом:
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
, допёр рисуя в тетради.
Потом идёт некрасивая длинная строка создания нового массива А, по способу из начала лекции. Тут наверняка можно сделать красивее, но сейчас уже башка не варит)
Ну и проверял я это визуально, что, конечно, неграмотно.
Спасибо, очень интересно смотреть ваши лекции.
я только учусь прог-ию и самое смешное, что вроде понятно и в тоже время ничего не понятно, а когда Тимофей обращается к залу с вопросом понятно ли им и они все молчат, я тоже сижу с квадратными глазами
Спасибо Вам еще раз!)
очень хотелось бы походить на живые лекции к этому преподавателю, пока что лучше уроков на ютубе не встречал
Осмелюсь завить, но сортировка выбором не совсем верна. Результат конечно верный, но действия не те. Вы меняете каждый раз элементы местами, если они меньше текущего. Да в итоге минимальный будет на месте, но перелопатили мы весь список. Это замедляет работу алгоритма. Наша задача найти минимальный и потом только поменять его местами с текущим.
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]
Возможно неточность в реализации сортировки выбором. Здесь за один проход внутреннего цикла могут происходить обмены нескольких элементов. А должен быть только один обмен с минимумом.
и, правда, ошибка
Не согласен с 1:17:45 . Сортировка подсчетом может применяться на массивах с любыми значениями и любым их количеством даже заранее неизвестным, просто нужно массив частот сделать динамическим (точнее два массива частот для символов и самих частот) и при появлении нового элемента сортируемого массива добавлять его в массив частот. Да потом придется разбирать сам массив частот, но это не препятствие.
В питоне это проще сделать при помощи словаря, чтобы не создавать два массива, если я правильно вас понял. Либо увеличивать динамический массив частот сразу на число пропущенных номеров между новым и последним известным символами.
в названиях видосов было бы полезно добавлять тему лекции
In English these ones are correct: Insertion sort, Selection sort and Bubble sort.
Спасибо за труды!
Спасибо за ваш огромный труд!
if __name__ == "__main__" - используется для того чтоб заснуть туда подпрограммы, которые выполняются при прямом компилировании файла библиотеки, но при импорте файла в другкю программу - эти подпрограммы не будут запущены автоматически. Не проверял еще можно ли импортить их принудительно типа from scriptname.py import test_sort
явно человек хороший! = Respect !!!
Тимофей Федорович is The Best!
Спасибо большое, очень интересно, Тимофей Федорович ❤
"Тимофей Федорович мог налажать, но не налажал" )) а все благодаря тестирующей функции.
Сортировка выбором (методом выбора) - selection sort. И не choise, а choice.
1:03:07 Тимофей сейчас излагает ровно противоположный алгоритм, то есть ставит в начало строя самых высоких.
Подскажите пожалуйста:
Для чего в первом методе сортировки нужна переменная 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 не пойму. спасибо
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])
Сортировки th-cam.com/video/D1u3H9_wmUU/w-d-xo.html
Фёдорыч явно человек хороший, поэтому предположу что он не обидится если оставлю тут ссылку на его коллегу из Гарварда.
До 6й лекции не дошло и 10% тех, кто посмотрел первую...)
Как в жизни!
Считай, что кто-то просто случайно зашел, кто-то просто из интереса, кто-то просто посчитал это скучным или не то, чего он ожидал. Посмотри на последние лекции по данной программе, там только 3-4% от тех, кто посмотрел 1 лекцию, из этого числа отними тех, кто просто случайно нажал и получишь очень маленькое количество.
@@jointmeister и это создаёт иллюзию переполненого рынка ИТ для многих
@@jointmeister Заметил много комментариев, типа лектор говорит слишком много лишнего
А что эти люди хотели, попав на лекцию для 1-курсников и даже не про программирование, а про АЛГОРИТМЫ?
Считаю, что все правильно, информация должна быть разложена хоть и объемно, но ясно.
Выучить синтаксис Python можно и зайдя на их офф. сайт, только вот толку от этого маловато
Не только дошел, но и много интересного законспектировал, хотя много лет работаю unix сисадмином и пишу на перле, баше и golang
В "selection/choice sort" в позицию k можно просто ставить минимумы массивов [k+1, N], не нужно делать swap для каждой пары, где arr[k] > arr[j]
@up4k свап для каждой пары - это не метод вставки
связка топчик, спасибо
List Comprehension можно было бы называть коллектором списка, по аналогии с Прологом.
Замечания можно конечно сделать любому, но это лучший лектор, которого я видел.
А замечания на самом деле простые. Мне кажется, что навык слушателя, к которому апеллирует лектор не успевает формироваться, и как следствие разрыв между лектором и слушателем наращивается. Если совсем просто, то лектор читает лекцию не для того, чтобы похвалиться своими знаниями, что бесспорно в случае с Тимофеем Хирьяновым, а для того, чтобы выработать практические навыки у слушателей.
Но всё равно Тимофей отличный лектор.
Вопрос возник 50:50 - последняя строка if name == "__main__":
- что это? в программе не задано имя name. Достаёт какой то доп файл с функцией*?
Вот учусь на программиста с дипломом техник технолог хлебопекарных производств))... Надеюсь за пол года осилю сие...
rtfm.co.ua/python-zachem-nuzhen-if-__name__-__main__/
1:08:07 Ошибка. Нужно вывести на print результаты тестирования и всё станет очевидным. Но Тимофей получает результат ОК , не подтверждённый визуальным подтверждением.
Так а в чем ошибка?
Здравствуйте спасибо вам большое. Нет возможности получать логин и пароль для прохождения практики на сайте?
начал читать книгу грокаем алгоритмы и случайно увидел данные лекции, само собой начал смотреть ) только все алгоритмы проецирую в языке C#
та же история)) только на Swift вместе с питоном :)
Как книга?
Sergey Fomin Книга хороша,очень классно оформлена в плане визуала
Подскажите пожалуйста как заканчивается сортировка подсчетом? Как создать массив из полученного F?
Я реализовал это в коде следующим способом:
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)
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)
Получилась небольшая игра в гольф, но если добавить комментарии, то всё станет понятно. Хотя мне так больше нравится ;-)
А вот в виде готовой функции. Пользуйтесь кому надо ;-)
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)
@@dnssm7074 А тест показывает Fail, хотя выглядит 1 в 1 и типы одинаковые (int). Начал разбираться выяснил, что внутри функции сортировки массив А выглядит отсортированным, а внутри функции теста - нет. При том, что для других функций сортировки массив А внутри функции теста выглядит отсортированным. Т.е. функции сортировки передают отсортированный массив А, а функция сортировки подсчетом сортирует массив А, но возвращает исходный.
вместо A=[] сделал A.clear() и всё заработало.
20:15 роняет мел, 20:18 берет новый! Absolute MAD LAD!
Ну тот скорее всего маленький был. Он оценил затраты/полезность поднятия старого мела и решил что взять новый - более рационально. Че тут MAD то?
Так уже не первый раз! А зачем корчиться и мел поднимать, если это можно сделать потом?!
почему бы не протестировать скорость выполнения сортировки с каждым методом ? в данном случае , естественно считать тысячные
Алгоритмы сортировки в танце. Шедевр :))))
th-cam.com/users/AlgoRythmics
Я конечно в этом не понимаю, первый раз вылетело новых видео.... Вот сейчас интересно- какое действие можно наблюдать на компе ...от этих действий которые описываются в этом видео?
подскажите, пожалуста, в сортировке методом выбора, если убрать переменную N, а вместо нее везде подставить len(A), почему список не получается отсортированным?
Коммент в поддержку контента.
Сортировка подсчётом, можете выложить решение? А, если на JavaScript сразу, было-бы супер)))
Кто-нибудь смог запустить сортировку подсчетом со считыванием "х" с клавиатуры как это показано на 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]
Буду признателен, если кто-то покажет как это можно было сделать короче, но простыми функциями, НЕ используя методы!
Сортировка вставками: в цикле while мы уменьшаем k(k-=1). Какой в этом смысл,если в цикле for k=top?
Задачи в практикуме вообще разноуровневые - есть на 5 минут, а есть и на 2 дня.
а можно как то решить задания,которые в контесте? Почему их скрыли(
очень нужна помощь, смотрю ваши лекции, но пока не увидела раздела по тому, что мне не понятно, проблемы с пониманием счетчиков, counter(подсчет кол-ва) и total(вычисление суммы и произведения) и сигнальные метки (flag), можете посоветовать какую-то литературу, где я как новичок, смогу разобраться с этими вопросами???
У меня предложенный код сортировки вставками не работает с 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
Потому что это не метод вставки.
В методе вставки соседние элементы местами не меняются.
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 # а теперь вставляем перед сдвинутой вправо часть массива
Тимофей, спасибо
запускаю в визуал студио, ни чего не работает. в первой строке что-то еще наверное должно быть, пишет с def не может начинаться, синтаксическая ошибка
Я чет не понял: чем сортировка вставками отличается от пузырьковой кроме направления движения по массиву?
Тем что в сортировки пузырьком ты сразу же сортируешь весь массив, тем самым у тебя всплывает последний элемент(пузырек)
Почему у меня не доконца работает код на 17:24?
А именно, не возвращает нули в место отрицательных чисел(я добавлял в массив отрицатедьные числа)
@@SkromnyParen1 у вас отрицательные цисла четные? Сейчас проверил. Все работает
@@mrSvob75A блин, уже не помню) Сейчас еще раз посмотрю
Возможно как-то получить доступ к заданиям из контеста? Или обязательно надо быть студентом МФТИ?
Можно ли увидеть задания из контеста?
не факт то что вы искали, но тут есть практические работы
judge.mipt.ru/mipt_cs_on_python3/
@@stennick1237 Супер!!! Спасибо огромное за ссылку!
@@stennick1237скажите пожалуйста а как туда попасть. Логин и пароль я вроде получил... Но не пускает (((
@@dizogdizog2591 смогли зайти? Меня тож не пускает
@@vladimirmashkov5194 нет (( с заданиями что то все туго. Может написать Тимофею. Он вроде не жадина
Подскажите, я не понял. На 59:00 в сортировке вставкой вводится строка "for top in range(1,N):". Почему здесь "top" равен 5? Отсчет проходов идет в обратную сторону?
top не равен 5, N равен 5.
top будет равен элементам арифметической прогрессии, генерируемой range(1,N), т.е.: 1, 2, 3, 4
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. Спасибо, Игнат. В общении рождается ответ.
Огромное спасибо!
Обьясните пожалуйста, что означает sort_algoritm(A)? Это функция ,которая выступает в качестве параметра функции test_sort? Мы же ее не создавали.Никак не могу понять.Помогите разобраться откуда это взялось и что означает.
Это параметр для функции test_sort.
И этим параметром является другая функция - одна из трёх сортировок.
test_sort(insert_sort) #тут на вход функции test_sort поступает функция insert_sort
То есть в этом вызове у нас вместо sort_algoritm будет insert_sort
Это не функция, а имя функции. Интерпретатор питона по этому имени находит соответствующую функцию, и подставляет её при вызове sort_algoritm(A).
Можно ли где-нибудь найти таблицу с планом?
Всем привет! Ребята, а как нибудб можно достать логины и пароли для контеста? Я не учусь в этом университете, но очень хочется пройти курс.
не реклама. Но по пайтону я проходил на prometheus курсы. Открытая рег-я, б/платные сертификаты. Но в этой лекции Тимофей Федорович больше учит программированию, чем только пайтон. И за это невыразимое спс. Вобщем совмещайте.
hack
Эх попасть бы к вам на информатику... Учусь на geekbrains, но там и половины не понял того, что понял у вас. О comprehension вообще молчали
Я тоже начинал учить на geeke. Очень плохо и скудно объясняют. Поэтому отказался от их услуг и вернул деньги.
@@talivik ну сейчас у меня начинается основное обучение и информации куча, не знаю насколько она ценна и полна от лица профессионалов, но для меня очень много
01:08:00
Важное замечание на счет скорости.
Меня задело что прапорщик туповат и не помнит каких солдат сортировал и решил написать свой алгоритм. Спустя несколько часов пришел к хорошей (как я думал) формуле. Алгоритм оказался действительно быстрее. Но потом решил опробовать метод .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]
Это у вас та же сортировка выбором алгоритмически - нашли в подмассиве [i:len(A)] минимальный элемент, поставили на i-e место.
Стандартная сортировка написана не на Python, поэтому очень много накладных расходов интерпретатора убирается, вот и быстрее.
Ну и стандартный sort() работает по алгоритму со сложностью O(n*log n), а не O(n^2).
Ктонить пробовал это повторить? У меня выдает ошибку. Он в первую ячейку списка вставляет всё, что написано в квадратных скобках в виде текста.
17:50
Я не понял откуда это следует.
Почему
0 if x
там должно быть b = [0 if x%2 != 0 else x**2 for x in a]
У нас задача поставлена, если x меньше нуля, то вместо возведения в квадрат, писать 0, оттуда и пошло
Selection sort
не совсем понял, зачем в алгоритме подсчетом вводится оператор input, что должен вводить пользователь?
это в самом конце, за две минуты до окончания
Тем самым он показал что это однопроходный алгоритм, и его можно реализовать "на ходу" считывая элементы вводимые пользователем.
спасибо!
Очень странный код в сортировке подсчётом, может кто дать ссылку или объяснить как это работает ?
Ставим столько коробочек сколько самая большая гиря весит (10 кг - 10 коробок).
Бежим вдоль ряда с гирями.
Сколько гиря весит (3 кг) в ту коробку (коробка №3) кидаем печенку.
Потом бежим вдоль наших коробок.
Если в коробке есть печенки, то печатаем номер коробки столько раз сколько в ней печенек.
Забыл в сортировке пузырьком проверять если на каком-то значении bypass не было ни одной замены, то можно выходить из цикла.
почему у Вас в этой задаче 10 + 5 + 3 равно 15 а не 18?
judge2.vdi.mipt.ru/cgi-bin/new-client?SID=2404f651ea51585c&action=139&prob_id=7
Потому что одноранговые операции без скобок выполняются в порядке записи. Для изменения порядка вычисления применяются скобки. 10 + (5 + 3) = 18
Total fail! =)) Это была мощная реализация! =)) Кодинг уровня "Бог".
Нет, кроме шуток, очень любопытно.
Я не совсем понял смысл этих алгоритмов. Разве метод sorted или sort не сортирует? Если сортирует, зачем городить такой огород?
Это вы к чему?
Эти методы сортируют по конкретному алгоритму сортировки, который не всегда является эффективным решением. Погуглите Quick sort и Buble sort
Ваш вопрос можно переформулировать как "Зачем придумывать способы готовки еды (на кастрюле, сковороде и т.п.), если существует мультиварка?".
@@СтепанСавельев-м8й зачем учиться считать, когда есть калькулятор
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.
Или это я чего-то не понял, и лектор всё верно написал?
Алгоритм не идет дальше, встречает первое число меньше нужного и меняет сразу. Для вашего варианта нужно сначала отметить все числа меньше нужного, потом еще их между собой сравнить, чтобы определить наименьшее, и только потом менять, а это уже какой-то другой способ, возможно неэффективный.