#9. Сортировка вставками | Алгоритмы на Python

Узнаете как работает алгоритм сортировки вставками и в чем его ключевое отличие от алгоритма сортировки выбором. Приведена реализация рассматриваемого алгоритма на Python.
algorithm-sort-inserts.py: github.com/selfedu-rus/python...

[@user-cc1qp6hd9b]

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

[@nazarkhort4362]

лучшее из объяснений данной темы на ютюбе, я не преувеличиваю

[@user-dy8sc3bp8o]

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

[@ladogaspirit9953]

тоже так подумалось при просмотре

[@usernoname-wv6of]

Можно без инсерта сделать вполне. 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

[@timur8216]

Огромное спасибо Вам! Максимально понятно объясняете, ждем продолжение по алгоритмам!)

[@user-qh5fr3yo1w]

Очень хорошее объяснение алгоритма. Сергею большое спасибо.

[@mrfang5908]

спасибо полезный алгоритм + очень простая подача, Жду от вас рекурсии, хеш и деревья, очень интересно посмотреть

[@reasonableengine]

Большое спасибо за популярное объяснение!

[@user-pw4cq7cp8v]

Спасибо за визуальное объяснение.

[@user-ux1ev4cx1w]

Отличное объяснение!) Спасибо огромное)

[@WadeChannal]

Самое понятное объяснение из всех что я видел

[@friend1cat]

Спасибо, Сергей!

[@nikitun85]

Все очень круто! Безусловно лайк. Но было бы неплохо хотя бы в двух словах акцентировать внимание на разнице с уже объясненными подходами. Когда разбираешься в этом первый раз, это не всегда очевидно. Первая моя мысль после этого видео была о том, что методы суть одно и то же, только идут по массиву в разных направлениях. Один из начала в конец, другой из конца в начало.

[@mma_lina]

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

[@antonivanov7687]

Спасибо, это лучше объяснение

[@lukasmog777]

Топ объяснение! Спасибо!

[@user-yp6yv2ub2u]

Сергей, вам следует заняться преподаванием. Огромное спасибо.

[@kirillguryanov4925]

спасибо большое!

[@ChibiPipa]

У меня через 3,5 часа экзамен начнётся, на котором будет билет с вопросом по методам сортировок. Спасибо Вам большое за видео

[@mag1c629]

сдал?

[@user-gu1eo9oy1y]

Вітаю, контент супер , але було б крутіше , щоб назви змін відповідали їх суті бо j та i заплутує навіть в такому простому на перший погляд алгоритмі

[@user-ft9sd1gj4g]

спасибо!

[@musecollaboration]

можно же вместо 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)

[@eulampiosubengaus8416]

За видео и труды однозначно лайк! Мне вот не совсем понятно, зачем блок else? Ведь если if дает False, то и так перейдем не следующую итерацию цилка с j.

[@workout3D]

Я так и не понял, в каком месте кода определяется, с каким начальным отсортированным подмассивом мы будем работать. По идее, чем больше элементов в начале стоит по порядку, тем меньше должно быть итераций, разве нет? Но количество итераций не меняется даде если подставить полностью отсортированный массив в а. Будет точно также сравниваться второй элемент с первым и т.д.

[@___12_37]

спасибо

[@donfedor007]

Вроде всё понятно, начинаю сам повторять не понимаю((( не как в голове не могу представать как это прорабатывается.

[@ANONIM_KA289]

Имеется массив целых чисел a[1],...,a[n], принимающих значения {0,1,....,m}.Сортировать этот массив по возрастанию , используя количество действий порядка (m + n). Указание: Посчитать сколько раз каждое из чисел {0,1,....,m} встречается в массиве. Кто знает подскажите какой алгоритм сортировки тут применять ?

[@jamjam3337]

👏👍

[@k-065olga8]

Доброе время суток! Есть еще такой алгоритм сортировки вставками 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) он ведь сложнее, но почему то именно он описан в книге. Можете объяснить зачем так усложняют некоторые авторы?

[@selfedu_rus]

Наверное эти авторы ранее программировали на С++, Fortran или каком другом подобном языке и формально также продолжают писать и на Python. Сам грешил вначале ))

[@k-065olga8]

@@selfedu_rus Спасибо большое за объяснение!!! и за Ваши уроки , в книгах очень мудрят !!!

[@k-065olga8]

А еще, смешно получилось. Я нашла Ваши уроки потому, что учусь на платных курсах и нам преподаватель объяснял полтора часа алгоритм КМТ и никто ничего не понял, вот и полезла погуглить)))

[@user-gc6jr7ev5u]

Как сделать такой же код на C# ?

[@user-nn5gz8ge1i]

А обезательно else: break писать? Если да, то почему?

[@user-hh2mi8dp2p]

Писать не обязательно, но это позволяет уменьшить кол-во сравнений (а следовательно и вычислительную сложность алгоритма). Тут else: break дает нам возможность не совершать лишние сравнения в уже отсортированной части массива, поэтому его лучше писать, чем не писать.

[@Oleg_RZA]

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

[@froggyt1243]

здраствуйте а как сделать сортировку ставками но наоборот от большого к меньшему

[@selfedu_rus]

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

[@happybunny9685]

Это разве не пузырьковый метод? Я про код

[@SLSRPPRO]

объясните пожалуйста for j in range(i, 0, -1)

[@selfedu_rus]

см. курс по Python на этом канале

[@SLSRPPRO]

@@selfedu_rus затупил , -1 это же шаг))

[@ladogaspirit9953]

Зачем это изучается если есть встроенные функции сортировки? На работе не оценят если вместо встроенной функции потратить время на такую реализацию.

[@selfedu_rus]

А кто все это изначально реализовывает? Бог? И что если нужно немного изменить алгоритм или развить?

[@tbma137]

пузырьковая реверс xd

[@anitar1996]

Это метод пузырька, а не вставка....

[@r1seup127]

Я не совсем понимаю, различия между пузырьком и вставкой, если значение (большее или меньшее передвигается на один, как при пузырьке. Там такое сравнение с соседом, и такое перемещение. Позиция поиска разве что другая. Так почему тогда вставку нельзя назвать пузырьком?

[@user-pw4cq7cp8v]

Потому что: 1. Пузырьки уже есть и тот алгоритм более логичен по названию. А называть можете как хотите - частичный пузырек.)) 2. Сложность этого алгоритм по лучшему его времени = n (если алгоритм уже отсортирован на входе, то алгоритм по нему пройдет один раз). В то время, как у пузырька всегда n^2.

[@ladogaspirit9953]

@@user-pw4cq7cp8vпройдет еще раз если использовали break. Если не использовать break то это обратный пузырек

[@user-yj7cv1bl9r]

Дизлайк сюда: 👍