Сергей, спасибо вам огромное за ваш труд ! Человечество держится на таких людях как вы, которые безвозмездно помогают другим, ваш вклад в обучение неоценим!)
Пересмотрел несколько раз, и все равно мне кажется что это не сортировка вставками а модифицированный "пузырёк" с реверсом во вложенном цикле, так как вы сравниваете элементы j и j -1 . По идее при сортировке вставками сравниваем i-й элемент и продвигаемся с проверкой условия к 0 элементу, если условие срабатывает то забираем элемент с позиции i и вставляем на позицию j на которой сработало условие, при этом если ранее сортированные элементы просто сдвигаются. Именно сортировка вставками в моём понимании ( в питоновском стиле) может выглядеть так: for i in range(1, len( list )): for j in range(i - 1, -1, -1): if list[ i ] < list[ j ]: continue else: j += 1 break if list[ j ] > list[ i ]: list.insert(j, list.pop(i)) поправьте, если я ошибся
Можно без инсерта сделать вполне. for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j -= 1 print(array) - Этот принт покажет что происходит со списком. По факту элемент, который будет вставлен на свое место хранится в key. В это время проходимся по списку и сдвигаем каждый элемент, который больше key вправо на +1 (если вставлять так n элементов, то на +n) array[j + 1] = key
Все очень круто! Безусловно лайк. Но было бы неплохо хотя бы в двух словах акцентировать внимание на разнице с уже объясненными подходами. Когда разбираешься в этом первый раз, это не всегда очевидно. Первая моя мысль после этого видео была о том, что методы суть одно и то же, только идут по массиву в разных направлениях. Один из начала в конец, другой из конца в начало.
не понял в чем различие этой сортировки от пузырька(в коде), потому что по сути так же меняем два соседних элемента. Когда сортировка вставкой подразумевает немного другое.
Я так и не понял, в каком месте кода определяется, с каким начальным отсортированным подмассивом мы будем работать. По идее, чем больше элементов в начале стоит по порядку, тем меньше должно быть итераций, разве нет? Но количество итераций не меняется даде если подставить полностью отсортированный массив в а. Будет точно также сравниваться второй элемент с первым и т.д.
можно же вместо break использовать continue? l = [10, 7, 8, 3, 8, -2] n = len(l) for run in range(1, n): for i in range(run, 0, -1): if l[i] < l[i - 1]: l[i], l[i - 1] = l[i - 1], l[i] continue print(l)
За видео и труды однозначно лайк! Мне вот не совсем понятно, зачем блок else? Ведь если if дает False, то и так перейдем не следующую итерацию цилка с j.
Доброе время суток! Есть еще такой алгоритм сортировки вставками a = [5, 2, 4, 6, 1, 3] for i in range(1, len(a)): temp = a[i] j = i - 1 while (j >= 0 and temp < a[j]): a[j + 1] = a[j] j = j - 1 a[j + 1] = temp print(*a) он ведь сложнее, но почему то именно он описан в книге. Можете объяснить зачем так усложняют некоторые авторы?
Наверное эти авторы ранее программировали на С++, Fortran или каком другом подобном языке и формально также продолжают писать и на Python. Сам грешил вначале ))
А еще, смешно получилось. Я нашла Ваши уроки потому, что учусь на платных курсах и нам преподаватель объяснял полтора часа алгоритм КМТ и никто ничего не понял, вот и полезла погуглить)))
В питоне есть возможность множественного присваивания, поэтому нет с смысла в использовании переменной key. Посмотрите ещё начальную лекцию Тимофея Хирьянова
Писать не обязательно, но это позволяет уменьшить кол-во сравнений (а следовательно и вычислительную сложность алгоритма). Тут else: break дает нам возможность не совершать лишние сравнения в уже отсортированной части массива, поэтому его лучше писать, чем не писать.
у меня ощущение что этот метод похож на пузырьковую сортировку только список каждый раз увеличивается на 1 элемент. быстрее тут получается за счет того, что если новый элемент больше сравниваемого то остальные элементы в списке будут меньше его и нужно только новый элемент воткнуть на место. Подскажите пожалуйста я прав в своих рассждениях?
Имеется массив целых чисел a[1],...,a[n], принимающих значения {0,1,....,m}.Сортировать этот массив по возрастанию , используя количество действий порядка (m + n). Указание: Посчитать сколько раз каждое из чисел {0,1,....,m} встречается в массиве. Кто знает подскажите какой алгоритм сортировки тут применять ?
Я не совсем понимаю, различия между пузырьком и вставкой, если значение (большее или меньшее передвигается на один, как при пузырьке. Там такое сравнение с соседом, и такое перемещение. Позиция поиска разве что другая. Так почему тогда вставку нельзя назвать пузырьком?
Потому что: 1. Пузырьки уже есть и тот алгоритм более логичен по названию. А называть можете как хотите - частичный пузырек.)) 2. Сложность этого алгоритм по лучшему его времени = n (если алгоритм уже отсортирован на входе, то алгоритм по нему пройдет один раз). В то время, как у пузырька всегда n^2.
Сергей, спасибо вам огромное за ваш труд ! Человечество держится на таких людях как вы, которые безвозмездно помогают другим, ваш вклад в обучение неоценим!)
лучшее из объяснений данной темы на ютюбе, я не преувеличиваю
Пересмотрел несколько раз, и все равно мне кажется что это не сортировка вставками а модифицированный "пузырёк" с реверсом во вложенном цикле, так как вы сравниваете элементы j и j -1 .
По идее при сортировке вставками сравниваем i-й элемент и продвигаемся с проверкой условия к 0 элементу, если условие срабатывает то забираем элемент с позиции i и вставляем на позицию j на которой сработало условие, при этом если ранее сортированные элементы просто сдвигаются.
Именно сортировка вставками в моём понимании ( в питоновском стиле) может выглядеть так:
for i in range(1, len( list )):
for j in range(i - 1, -1, -1):
if list[ i ] < list[ j ]:
continue
else:
j += 1
break
if list[ j ] > list[ i ]:
list.insert(j, list.pop(i))
поправьте, если я ошибся
тоже так подумалось при просмотре
Можно без инсерта сделать вполне.
for i in range(1, len(array)):
key = array[i]
j = i - 1
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j -= 1
print(array) - Этот принт покажет что происходит со списком. По факту элемент, который будет вставлен на свое место хранится в key. В это время проходимся по списку и сдвигаем каждый элемент, который больше key вправо на +1 (если вставлять так n элементов, то на +n)
array[j + 1] = key
спасибо! помогло при прохождении курса на степике
Огромное спасибо Вам!
Максимально понятно объясняете, ждем продолжение по алгоритмам!)
спасибо полезный алгоритм + очень простая подача, Жду от вас рекурсии, хеш и деревья, очень интересно посмотреть
Очень хорошее объяснение алгоритма. Сергею большое спасибо.
Самое понятное объяснение из всех что я видел
Все очень круто! Безусловно лайк. Но было бы неплохо хотя бы в двух словах акцентировать внимание на разнице с уже объясненными подходами. Когда разбираешься в этом первый раз, это не всегда очевидно. Первая моя мысль после этого видео была о том, что методы суть одно и то же, только идут по массиву в разных направлениях. Один из начала в конец, другой из конца в начало.
не понял в чем различие этой сортировки от пузырька(в коде), потому что по сути так же меняем два соседних элемента. Когда сортировка вставкой подразумевает немного другое.
У меня через 3,5 часа экзамен начнётся, на котором будет билет с вопросом по методам сортировок.
Спасибо Вам большое за видео
сдал?
Спасибо, Сергей!
Большое спасибо за популярное объяснение!
Спасибо за визуальное объяснение.
Отличное объяснение!) Спасибо огромное)
Спасибо, это лучше объяснение
Сергей, вам следует заняться преподаванием. Огромное спасибо.
А не надо в конце к N добавлять +1, потому что range последний элемент не включает?
Топ объяснение! Спасибо!
спасибо большое!
Я так и не понял, в каком месте кода определяется, с каким начальным отсортированным подмассивом мы будем работать. По идее, чем больше элементов в начале стоит по порядку, тем меньше должно быть итераций, разве нет? Но количество итераций не меняется даде если подставить полностью отсортированный массив в а. Будет точно также сравниваться второй элемент с первым и т.д.
можно же вместо break использовать continue?
l = [10, 7, 8, 3, 8, -2]
n = len(l)
for run in range(1, n):
for i in range(run, 0, -1):
if l[i] < l[i - 1]:
l[i], l[i - 1] = l[i - 1], l[i]
continue
print(l)
За видео и труды однозначно лайк! Мне вот не совсем понятно, зачем блок else? Ведь если if дает False, то и так перейдем не следующую итерацию цилка с j.
спасибо
Вітаю, контент супер , але було б крутіше , щоб назви змін відповідали їх суті бо j та i заплутує навіть в такому простому на перший погляд алгоритмі
👏👍
спасибо!
Доброе время суток! Есть еще такой алгоритм сортировки вставками
a = [5, 2, 4, 6, 1, 3]
for i in range(1, len(a)):
temp = a[i]
j = i - 1
while (j >= 0 and temp < a[j]):
a[j + 1] = a[j]
j = j - 1
a[j + 1] = temp
print(*a)
он ведь сложнее, но почему то именно он описан в книге. Можете объяснить зачем так усложняют некоторые авторы?
Наверное эти авторы ранее программировали на С++, Fortran или каком другом подобном языке и формально также продолжают писать и на Python. Сам грешил вначале ))
@@selfedu_rus Спасибо большое за объяснение!!! и за Ваши уроки , в книгах очень мудрят !!!
А еще, смешно получилось. Я нашла Ваши уроки потому, что учусь на платных курсах и нам преподаватель объяснял полтора часа алгоритм КМТ и никто ничего не понял, вот и полезла погуглить)))
В питоне есть возможность множественного присваивания, поэтому нет с смысла в использовании переменной key. Посмотрите ещё начальную лекцию Тимофея Хирьянова
А обезательно else: break писать? Если да, то почему?
Писать не обязательно, но это позволяет уменьшить кол-во сравнений (а следовательно и вычислительную сложность алгоритма). Тут else: break дает нам возможность не совершать лишние сравнения в уже отсортированной части массива, поэтому его лучше писать, чем не писать.
Спасибо большое))))
Вроде всё понятно, начинаю сам повторять не понимаю((( не как в голове не могу представать как это прорабатывается.
у меня ощущение что этот метод похож на пузырьковую сортировку только список каждый раз увеличивается на 1 элемент. быстрее тут получается за счет того, что если новый элемент больше сравниваемого то остальные элементы в списке будут меньше его и нужно только новый элемент воткнуть на место.
Подскажите пожалуйста я прав в своих рассждениях?
Имеется массив целых чисел a[1],...,a[n], принимающих значения {0,1,....,m}.Сортировать этот массив по возрастанию , используя количество действий порядка (m + n). Указание: Посчитать сколько раз каждое из чисел {0,1,....,m} встречается в массиве.
Кто знает подскажите какой алгоритм сортировки тут применять ?
Как сделать такой же код на C# ?
здраствуйте а как сделать сортировку ставками но наоборот от большого к меньшему
при слиянии списков формируете последовательности от большего к меньшему и все
Это разве не пузырьковый метод? Я про код
объясните пожалуйста for j in range(i, 0, -1)
см. курс по Python на этом канале
@@selfedu_rus затупил , -1 это же шаг))
Зачем это изучается если есть встроенные функции сортировки? На работе не оценят если вместо встроенной функции потратить время на такую реализацию.
А кто все это изначально реализовывает? Бог? И что если нужно немного изменить алгоритм или развить?
пузырьковая реверс xd
Это метод пузырька, а не вставка....
Я не совсем понимаю, различия между пузырьком и вставкой, если значение (большее или меньшее передвигается на один, как при пузырьке. Там такое сравнение с соседом, и такое перемещение. Позиция поиска разве что другая. Так почему тогда вставку нельзя назвать пузырьком?
Потому что:
1. Пузырьки уже есть и тот алгоритм более логичен по названию. А называть можете как хотите - частичный пузырек.))
2. Сложность этого алгоритм по лучшему его времени = n (если алгоритм уже отсортирован на входе, то алгоритм по нему пройдет один раз). В то время, как у пузырька всегда n^2.
@@ЕгорМиронов-щ3ппройдет еще раз если использовали break. Если не использовать break то это обратный пузырек
Дизлайк сюда:
👍