Insertion sort

Insertion sort is a simple sorting algorithm that consumes one input element each iteration and builds the final sorted array.

[@happygun4685]

Благодарю Вас за проделанную работу! Всё прекрасно и предельно ясно объяснили!

[@romantsarev1145]

Пожалуйста

[@Fravije]

Спасибо. Добавили домашней уютной атмосферы тихие звуки сервировки стола начиная с 1:56 😇

[@yolo-cars]

Спасибо за объяснение! Я написал этот псевдокод на JavaScript, однако, у меня массив [1,4,3,8,5] не упорядочился. В этоге получилось так: [1,3,4,8,5]. Чтобы это работало я во внешнем цикле увеличил диапазон до n, т.е. до длинны массива. Вот фрагмент моего кода внешнего цикла: for(let i = 1; i < arr.length; i++){....}. Здесь arr - это аргумент, который я передаю в функцию по сортировке, т.е. arr - это и есть массив, а вот arr.length - это встроенный метод, который возвращает длину массива. А вообще я изначально думал, как лучше сделать вставку элемента Х, чтобы не менять местами все элементы. Но не придумал. Например, можно добавить элемент Х в нужное место и затем удалить элемент Х из исходного места с помощью встроенных методов для объекта массива array.splice и array.slice, но я думаю, что у каждого под капотом живёт ещё и переиндексация элементов массива, т.е. сложность будет уже не O(n^2), а O(n^4). PS: там в псевдокоде даже когда мы ничего не должны по идее менять, то всё равно происходит присвоение A[j]=x. Я понимаю, что тут уже на сложность O(n^2) это не влияет, но всё как по мне, то неплохо было бы ничего не делать, если ничего не нужно менять. Я проверил эту идею и оборнул весь цикл while и A[j]=x в if-else statement. Теперь если x > A[j-1], то просто идём дальше по массиву вправо.

[@romantsarev1145]

Отлично

[@orangesecurity3908]

спасибо за видео. кратко и понятно 💗

[@romantsarev1145]

Пожалуйста

[@ЭрикБружас]

В данном моменте 1 итерация - это одного цикла, а во вложенном цикле итераций больше, то есть итерации первого цикла нужно помножить на итерации второго цикла и тогда получится правильное число итераций

[@romantsarev1145]

Что Вы называете итерацией? Я, вернее классики, определяют ее следующим образом: 0:23

[@ЭрикБружас]

@@romantsarev1145 итерация - это повторение какого либо действия, математической операции и т.д. В итоге получается в первом цикле происходит сравнение впереди идущих элементов и если их нужно поменять местами, происходит замена элементов (итерация) далее, во вложенном цикле, сравнивается помененный раннее элемент в обратном порядке и при необходимости происходит замена (это снова итерация), чтобы он встал на свое место. То есть получается, что общее кол-во итераций, это количество итераций внешнего цикла, помноженное на кол-во итераций вложенного цикла.

[@ЭрикБружас]

@@romantsarev1145 для простоты объяснения, возможно. А когда необходимо разбирать алгоритмы на скорость работы, то тут следует учитывать и итерации вложенных циклов потому, как это сильно влияет на скорость работы алгоритма.

[@RicoVideoChannel]

Очень понятно, спасибо!

[@romantsarev1145]

Пожалуйста.

[@nicejacket6607]

"Нам дан массив, готовая последовательность содержит только один элемент, исходная последовательность содержит все остальные элементы". Я не понимаю, каким образом компьютер должен понять, какая последовательность готовая, а какая нет?? Это вам как человеку , который смотрит на этот массив очевидно, а комп как это должен понять? То есть, мы предварительно должны это установить каким-то алгоритмом? Почему вы об этом не говорите?

[@ДмитрийПостнов-з5ь]

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

[@samfisher8864]

Компьютер и не должен ничего понимать :) Для него достаточно, что он движется вперед по массиву и ему не важны уже пройденные элементы. Условно за отсортированный массив принимается нулевой элемент массива, потому цикл for в данной сортировке и начинается с 1. Далее для каждого элемента данного массива мы создаем его копию, которую в конце и помещаем на позицию с подходящим индексом. Эту самую позицию мы и вычисляем с помощью цикла while. Важно, чтобы мы не уходили за пределы массива и чтобы элемент позицию которого мы ищем был меньше его "соседа" слева. Собственно если "сосед слева" меньше значения или же индекс ушел за пределы, то цикл прерывается, а мы получаем тот самый искомый индекс этого элемента в отсортированном массиве. Поиск соседа в данном цикле осуществляется путем замещения элемента тем самым соседом "слева", а само значение индекса этого элемента уменьшается на 1(для сдвига влево). В итоге мы при нарушении условия цикла while (а оно рано или поздно наступает) получаем нужный нам индекс, где должен находиться сортируемый элемент, где нам и пригождается та самая копия сделанная в начале, которую мы присваиваем элементу с уже имеющимся индексом.

[@aiahz]

Тогда для начала советую почитать Д.Кнута "Искусство программирования" или хотя бы подучить тот язык, на котором собираешься реализовывать данную сортировку. Так как ответ на твой вопрос достаточно элементарный. Самый простой вариант: мы организуем цикл с предусловием который увеличивает счетчик до тех пока соблюдается условие Array[n]

[@aiahz]

А можешь просто крикнуть: "На йух мне ваша оптимизация!" и херачить с первого элемента.

[@reptiloid7438]

@@aiahz "Кнута для начала" - ну ты и загнул)

[@Youtooobo]

00:35 сдвигаем двойку пошагово? Сначала она будет между 3 и 4, а только после следующей итерации, между 1 и 3. Как она сразу попадает между 1 и 3?

[@romantsarev1145]

Нет, не пошагово. Если бы пошагово, то это была бы сортировка обменами (пузырьковая сортировка). Здесь Вы 2 сохраняете во временную переменную, сдвигаете 4, затем 3. И уже потом ставите на место тройки 2.

[@gfest1119]

А если j=1 то по псевдокоду получится что 1>0 и A[0]>x и как бы мы вышли за границу массива...?

[@romantsarev1145]

Вопрос не понятен. "А если j=1 то по псевдокоду получится что 1>0 и A[0]>x" - всё верно, получится условие (1>0 и A[0]>x). А вот, было ли бы оно истинным, зависит от значения переменной икс. "и как бы мы вышли за границу массива...?" - так нам и нельзя выходить за нее. Мы бы за нее и не вышли. Если бы A[0] оказался меньше или равен иксу, то мы вышли бы из while уже сейчас, на этой итерации, так и не зайдя в тело цикла while. Если же условие A[0]>x было бы истинным, то мы бы вышли из while на следующей итерации, поскольку j стал бы равен нулю.

[@gfest1119]

@@romantsarev1145 так А[0] элемента не существует

[@romantsarev1145]

@@gfest1119 почему не существует?! Обратите внимание, что у нас цикл идет до элемента с индексом n-1. Это последний элемент. Всего элементов в массиве n. Нумерация начинается с нуля, как, например, в языке Си. Таким образом, A[0] - значение первого элемента массива.

[@gfest1119]

@@romantsarev1145 аааа. У вас с нуля. Понял

[@ВикторПирожков-ш2ю]

Очень хотелось бы, чтобы каждая переменная на 1:52 была подписана, не понятно какая переменная за что отвечает, самому приходится разбираться, а так урок хороший, спасибо

[@romantsarev1145]

Это было бы уже чересчур )

[@Гычпук]

​@@romantsarev1145что чересчур? Если учите, то учите нормально

[@musosalamov]

Код на каком языке программирования?

[@romantsarev1145]

На псевдокоде

[@lkkath]

ребята, скиньте код

[@romantsarev1145]

def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >=0 and key < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key arr = [12, 11, 13, 5, 6] insertion_sort(arr) print ("Sorted array is:") for i in range(len(arr)): print arr[i]

[@lkkath]

@@romantsarev1145 спасибо вам

[@nicholasspezza9449]

так се объяснение

[@romantsarev1145]

Уж как смог. Сорри

[@nicholasspezza9449]

я не буду против, если вы переделаете и перезальёте

[@romantsarev1145]

@@nicholasspezza9449 Уже засучил рукова. Спасибо, что позволили