Спасибо за объяснение! Я написал этот псевдокод на 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], то просто идём дальше по массиву вправо.
В данном моменте 1 итерация - это одного цикла, а во вложенном цикле итераций больше, то есть итерации первого цикла нужно помножить на итерации второго цикла и тогда получится правильное число итераций
@@romantsarev1145 итерация - это повторение какого либо действия, математической операции и т.д. В итоге получается в первом цикле происходит сравнение впереди идущих элементов и если их нужно поменять местами, происходит замена элементов (итерация) далее, во вложенном цикле, сравнивается помененный раннее элемент в обратном порядке и при необходимости происходит замена (это снова итерация), чтобы он встал на свое место. То есть получается, что общее кол-во итераций, это количество итераций внешнего цикла, помноженное на кол-во итераций вложенного цикла.
@@romantsarev1145 для простоты объяснения, возможно. А когда необходимо разбирать алгоритмы на скорость работы, то тут следует учитывать и итерации вложенных циклов потому, как это сильно влияет на скорость работы алгоритма.
Нет, не пошагово. Если бы пошагово, то это была бы сортировка обменами (пузырьковая сортировка). Здесь Вы 2 сохраняете во временную переменную, сдвигаете 4, затем 3. И уже потом ставите на место тройки 2.
"Нам дан массив, готовая последовательность содержит только один элемент, исходная последовательность содержит все остальные элементы". Я не понимаю, каким образом компьютер должен понять, какая последовательность готовая, а какая нет?? Это вам как человеку , который смотрит на этот массив очевидно, а комп как это должен понять? То есть, мы предварительно должны это установить каким-то алгоритмом? Почему вы об этом не говорите?
Ты начинаешь с нулевого элемента массива, т.е в начале "готовая" последовательность содержит 1 элемент,а затем на каждой итерации она увеличивается на 1
Компьютер и не должен ничего понимать :) Для него достаточно, что он движется вперед по массиву и ему не важны уже пройденные элементы. Условно за отсортированный массив принимается нулевой элемент массива, потому цикл for в данной сортировке и начинается с 1. Далее для каждого элемента данного массива мы создаем его копию, которую в конце и помещаем на позицию с подходящим индексом. Эту самую позицию мы и вычисляем с помощью цикла while. Важно, чтобы мы не уходили за пределы массива и чтобы элемент позицию которого мы ищем был меньше его "соседа" слева. Собственно если "сосед слева" меньше значения или же индекс ушел за пределы, то цикл прерывается, а мы получаем тот самый искомый индекс этого элемента в отсортированном массиве. Поиск соседа в данном цикле осуществляется путем замещения элемента тем самым соседом "слева", а само значение индекса этого элемента уменьшается на 1(для сдвига влево). В итоге мы при нарушении условия цикла while (а оно рано или поздно наступает) получаем нужный нам индекс, где должен находиться сортируемый элемент, где нам и пригождается та самая копия сделанная в начале, которую мы присваиваем элементу с уже имеющимся индексом.
Тогда для начала советую почитать Д.Кнута "Искусство программирования" или хотя бы подучить тот язык, на котором собираешься реализовывать данную сортировку. Так как ответ на твой вопрос достаточно элементарный. Самый простой вариант: мы организуем цикл с предусловием который увеличивает счетчик до тех пока соблюдается условие Array[n]
Вопрос не понятен. "А если j=1 то по псевдокоду получится что 1>0 и A[0]>x" - всё верно, получится условие (1>0 и A[0]>x). А вот, было ли бы оно истинным, зависит от значения переменной икс. "и как бы мы вышли за границу массива...?" - так нам и нельзя выходить за нее. Мы бы за нее и не вышли. Если бы A[0] оказался меньше или равен иксу, то мы вышли бы из while уже сейчас, на этой итерации, так и не зайдя в тело цикла while. Если же условие A[0]>x было бы истинным, то мы бы вышли из while на следующей итерации, поскольку j стал бы равен нулю.
@@gfest1119 почему не существует?! Обратите внимание, что у нас цикл идет до элемента с индексом n-1. Это последний элемент. Всего элементов в массиве n. Нумерация начинается с нуля, как, например, в языке Си. Таким образом, A[0] - значение первого элемента массива.
Очень хотелось бы, чтобы каждая переменная на 1:52 была подписана, не понятно какая переменная за что отвечает, самому приходится разбираться, а так урок хороший, спасибо
Благодарю Вас за проделанную работу! Всё прекрасно и предельно ясно объяснили!
Пожалуйста
Спасибо. Добавили домашней уютной атмосферы тихие звуки сервировки стола начиная с 1:56 😇
Очень понятно, спасибо!
Пожалуйста.
спасибо за видео. кратко и понятно 💗
Пожалуйста
Спасибо за объяснение! Я написал этот псевдокод на 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], то просто идём дальше по массиву вправо.
Отлично
В данном моменте 1 итерация - это одного цикла, а во вложенном цикле итераций больше, то есть итерации первого цикла нужно помножить на итерации второго цикла и тогда получится правильное число итераций
Что Вы называете итерацией? Я, вернее классики, определяют ее следующим образом: 0:23
@@romantsarev1145 итерация - это повторение какого либо действия, математической операции и т.д. В итоге получается в первом цикле происходит сравнение впереди идущих элементов и если их нужно поменять местами, происходит замена элементов (итерация) далее, во вложенном цикле, сравнивается помененный раннее элемент в обратном порядке и при необходимости происходит замена (это снова итерация), чтобы он встал на свое место. То есть получается, что общее кол-во итераций, это количество итераций внешнего цикла, помноженное на кол-во итераций вложенного цикла.
@@romantsarev1145 для простоты объяснения, возможно. А когда необходимо разбирать алгоритмы на скорость работы, то тут следует учитывать и итерации вложенных циклов потому, как это сильно влияет на скорость работы алгоритма.
00:35 сдвигаем двойку пошагово? Сначала она будет между 3 и 4, а только после следующей итерации, между 1 и 3.
Как она сразу попадает между 1 и 3?
Нет, не пошагово. Если бы пошагово, то это была бы сортировка обменами (пузырьковая сортировка). Здесь Вы 2 сохраняете во временную переменную, сдвигаете 4, затем 3. И уже потом ставите на место тройки 2.
"Нам дан массив, готовая последовательность содержит только один элемент, исходная последовательность содержит все остальные элементы".
Я не понимаю, каким образом компьютер должен понять, какая последовательность готовая, а какая нет?? Это вам как человеку , который смотрит на этот массив очевидно, а комп как это должен понять? То есть, мы предварительно должны это установить каким-то алгоритмом? Почему вы об этом не говорите?
Ты начинаешь с нулевого элемента массива, т.е в начале "готовая" последовательность содержит 1 элемент,а затем на каждой итерации она увеличивается на 1
Компьютер и не должен ничего понимать :) Для него достаточно, что он движется вперед по массиву и ему не важны уже пройденные элементы.
Условно за отсортированный массив принимается нулевой элемент массива, потому цикл for в данной сортировке и начинается с 1.
Далее для каждого элемента данного массива мы создаем его копию, которую в конце и помещаем на позицию с подходящим индексом. Эту самую позицию мы и вычисляем с помощью цикла while. Важно, чтобы мы не уходили за пределы массива и чтобы элемент позицию которого мы ищем был меньше его "соседа" слева.
Собственно если "сосед слева" меньше значения или же индекс ушел за пределы, то цикл прерывается, а мы получаем тот самый искомый индекс этого элемента в отсортированном массиве. Поиск соседа в данном цикле осуществляется путем замещения элемента тем самым соседом "слева", а само значение индекса этого элемента уменьшается на 1(для сдвига влево).
В итоге мы при нарушении условия цикла while (а оно рано или поздно наступает) получаем нужный нам индекс, где должен находиться сортируемый элемент, где нам и пригождается та самая копия сделанная в начале, которую мы присваиваем элементу с уже имеющимся индексом.
Тогда для начала советую почитать Д.Кнута "Искусство программирования" или хотя бы подучить тот язык, на котором собираешься реализовывать данную сортировку. Так как ответ на твой вопрос достаточно элементарный. Самый простой вариант: мы организуем цикл с предусловием который увеличивает счетчик до тех пока соблюдается условие Array[n]
А можешь просто крикнуть: "На йух мне ваша оптимизация!" и херачить с первого элемента.
@@aiahz "Кнута для начала" - ну ты и загнул)
А если j=1 то по псевдокоду получится что 1>0 и A[0]>x и как бы мы вышли за границу массива...?
Вопрос не понятен. "А если j=1 то по псевдокоду получится что 1>0 и A[0]>x" - всё верно, получится условие (1>0 и A[0]>x). А вот, было ли бы оно истинным, зависит от значения переменной икс.
"и как бы мы вышли за границу массива...?" - так нам и нельзя выходить за нее. Мы бы за нее и не вышли. Если бы A[0] оказался меньше или равен иксу, то мы вышли бы из while уже сейчас, на этой итерации, так и не зайдя в тело цикла while. Если же условие A[0]>x было бы истинным, то мы бы вышли из while на следующей итерации, поскольку j стал бы равен нулю.
@@romantsarev1145 так А[0] элемента не существует
@@gfest1119 почему не существует?! Обратите внимание, что у нас цикл идет до элемента с индексом n-1. Это последний элемент. Всего элементов в массиве n. Нумерация начинается с нуля, как, например, в языке Си. Таким образом, A[0] - значение первого элемента массива.
@@romantsarev1145 аааа. У вас с нуля. Понял
Код на каком языке программирования?
На псевдокоде
Очень хотелось бы, чтобы каждая переменная на 1:52 была подписана, не понятно какая переменная за что отвечает, самому приходится разбираться, а так урок хороший, спасибо
Это было бы уже чересчур )
@@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]
@@romantsarev1145 спасибо вам
for i=1 to n а не n-1
Нет
@@romantsarev1145 у меня при n-1 последний элемент остаётся неотсортированным
В программе косяк. Псевдокод правильный.
У Вас индекс первого элемента равен нулю?
@@romantsarev1145 в псевдокоде не нужно объявлять переменные?
так се объяснение
Уж как смог. Сорри
я не буду против, если вы переделаете и перезальёте
@@nicholasspezza9449 Уже засучил рукова. Спасибо, что позволили