#9. Сортировка вставками | Алгоритмы на Python
Vložit
- čas přidán 28. 02. 2021
- Узнаете как работает алгоритм сортировки вставками и в чем его ключевое отличие от алгоритма сортировки выбором. Приведена реализация рассматриваемого алгоритма на Python.
algorithm-sort-inserts.py: github.com/selfedu-rus/python...
Сергей, спасибо вам огромное за ваш труд ! Человечество держится на таких людях как вы, которые безвозмездно помогают другим, ваш вклад в обучение неоценим!)
лучшее из объяснений данной темы на ютюбе, я не преувеличиваю
Огромное спасибо Вам!
Максимально понятно объясняете, ждем продолжение по алгоритмам!)
спасибо полезный алгоритм + очень простая подача, Жду от вас рекурсии, хеш и деревья, очень интересно посмотреть
Очень хорошее объяснение алгоритма. Сергею большое спасибо.
Пересмотрел несколько раз, и все равно мне кажется что это не сортировка вставками а модифицированный "пузырёк" с реверсом во вложенном цикле, так как вы сравниваете элементы 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 часа экзамен начнётся, на котором будет билет с вопросом по методам сортировок.
Спасибо Вам большое за видео
сдал?
Сергей, вам следует заняться преподаванием. Огромное спасибо.
спасибо!
спасибо
Вітаю, контент супер , але було б крутіше , щоб назви змін відповідали їх суті бо j та i заплутує навіть в такому простому на перший погляд алгоритмі
👏👍
За видео и труды однозначно лайк! Мне вот не совсем понятно, зачем блок else? Ведь если if дает False, то и так перейдем не следующую итерацию цилка с j.
Имеется массив целых чисел a[1],...,a[n], принимающих значения {0,1,....,m}.Сортировать этот массив по возрастанию , используя количество действий порядка (m + n). Указание: Посчитать сколько раз каждое из чисел {0,1,....,m} встречается в массиве.
Кто знает подскажите какой алгоритм сортировки тут применять ?
Как сделать такой же код на C# ?
Вроде всё понятно, начинаю сам повторять не понимаю((( не как в голове не могу представать как это прорабатывается.
Я так и не понял, в каком месте кода определяется, с каким начальным отсортированным подмассивом мы будем работать. По идее, чем больше элементов в начале стоит по порядку, тем меньше должно быть итераций, разве нет? Но количество итераций не меняется даде если подставить полностью отсортированный массив в а. Будет точно также сравниваться второй элемент с первым и т.д.
можно же вместо 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: break писать? Если да, то почему?
Писать не обязательно, но это позволяет уменьшить кол-во сравнений (а следовательно и вычислительную сложность алгоритма). Тут else: break дает нам возможность не совершать лишние сравнения в уже отсортированной части массива, поэтому его лучше писать, чем не писать.
Спасибо большое))))
Доброе время суток! Есть еще такой алгоритм сортировки вставками
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 Спасибо большое за объяснение!!! и за Ваши уроки , в книгах очень мудрят !!!
А еще, смешно получилось. Я нашла Ваши уроки потому, что учусь на платных курсах и нам преподаватель объяснял полтора часа алгоритм КМТ и никто ничего не понял, вот и полезла погуглить)))
здраствуйте а как сделать сортировку ставками но наоборот от большого к меньшему
при слиянии списков формируете последовательности от большего к меньшему и все
объясните пожалуйста for j in range(i, 0, -1)
см. курс по Python на этом канале
@@selfedu_rus затупил , -1 это же шаг))
у меня ощущение что этот метод похож на пузырьковую сортировку только список каждый раз увеличивается на 1 элемент. быстрее тут получается за счет того, что если новый элемент больше сравниваемого то остальные элементы в списке будут меньше его и нужно только новый элемент воткнуть на место.
Подскажите пожалуйста я прав в своих рассждениях?
Это разве не пузырьковый метод? Я про код
Зачем это изучается если есть встроенные функции сортировки? На работе не оценят если вместо встроенной функции потратить время на такую реализацию.
А кто все это изначально реализовывает? Бог? И что если нужно немного изменить алгоритм или развить?
пузырьковая реверс xd
Это метод пузырька, а не вставка....
Я не совсем понимаю, различия между пузырьком и вставкой, если значение (большее или меньшее передвигается на один, как при пузырьке. Там такое сравнение с соседом, и такое перемещение. Позиция поиска разве что другая. Так почему тогда вставку нельзя назвать пузырьком?
Потому что:
1. Пузырьки уже есть и тот алгоритм более логичен по названию. А называть можете как хотите - частичный пузырек.))
2. Сложность этого алгоритм по лучшему его времени = n (если алгоритм уже отсортирован на входе, то алгоритм по нему пройдет один раз). В то время, как у пузырька всегда n^2.
@@user-pw4cq7cp8vпройдет еще раз если использовали break. Если не использовать break то это обратный пузырек
Дизлайк сюда:
👍