Пишем на С++ простые сортировки и пытаемся понять то, что написали
HTML-код
- Опубликовано: 29 сен 2024
- Сортировки: вставками, обменом и выбором.
Работающую программу можно посмотреть, откомпилировать (compile) и запустить (execute) здесь: goo.gl/8IyBPz
Для внимательных читателей и зрителей, Я допустила одну ошибку. Если кто-то её найдет, то я назову его имя в следующем ролике.
Подсказка: одна сортировка не будет работать, если в массиве появится отрицательное число.
Особая благодарность Чаку Норрису и "Друзьям" за содействие в создании видео.
Шикардос)
ты лучший преподаватель! однозначно )))
спасибо))
Спасибо за объяснение. Кстати привет из 2020
вы очень милая)
:)
В примере Insertion sort нам приходится сравнивать переменную x c a[-1] а это выход за пределы массива? Там же может быть какое то значение? Может ли это как то сказаться на работе?
Первый цикл начинается с 1, а не с 0 как массив. Минимум х сравниваем с а[0] и не выходим за пределы массива. Спасибо!)))
@@КонстантинФерафонтов-д3п нет, тут допущена ошибка, может выходить за пределы массива, j-- даст -1 и все, краш
Я понял! Спасибо!
Спасибо, я очень рада!! :)
Отличные видео! Однако, возник вопрос про сортировку вставками: разве во внутреннем цикле не будет возникать ситуация, когда j примет значение -1? И тогда в условии на этот цикл будет обращение к несуществующему а[-1]. А это вроде как выход за границы массива....
именно так и происходит!
Я думал такие профессионалы как Дарья сортировки по ключу пишут
Привет , я сам программист только на с# . Закончил Станкин с отличием а так же институт управления так же с отличием закончил кафедра информационных систем . Очень интересно рассказываете давайте что нибудь вместе создадим ? Я сейчас работаю над одним интересным на мой взгляд проектом связанным с библиотекой Open.cv . Предлагаю присоединиться .
В сортировке выбором во внешнем цикле граница N-1 :)
Да, действительно, Olexandr, последняя итерация бессмысленна)), потому что все элементы уже отсортированы).
Спасибо большое! Вот, что значит доверять своим учебным записям)) и тому, что программа работает правильно, но получается, не до конца эффективно).
Ещё раз спасибо!
Не за что :)
Но мне кажется, что будет segfault из-за итерации по N-ному элементу (i = N-1 => j = i+1 = N)
Странно, у меня нет..
Я же выложила ссылку на код и прямо на сайт, где можно откомпилировать онлайн, и там всё работает, по крайней мере, компилировалось и сортировало, когда я выкладывала. Я всё всегда по 20-30 раз проверяю, как ненормальная).
Да мне только показалось :)
Там всё же условие j < N не пропустит к несуществующему элементу.
А почему вдруг мы стали сравнивать i 2 не с i 0 а с i 1🤯 у нас ведь изначально в ящичке был i 0❓❓❓❓
Чё серйозно это могут на собеседовании спросить, просто не вписывается в мое представление мира, типа прихожу я такой на собеседование как программист С++, сажусь, а они такие напишите нам сортировку пузырьком, ну даже если выбором, а я в это время только radix буду помнить и что мне делать, выход один, идти в нормальную компанию) (p.s. или создать свою)
Работодатель вправе спросить такую дичь как реализация сортировки, даже если сами они вовсю используют STL. Это некий фильтр для них выбрать лучшего кандидата. Ведь много желающих работать программистом и как их проверить?
Сверху индекс элементов ептааааааааааааааааааааааа
Вы молодец, это очень важная тема для начинающих. Большое спасибо)))
Решил заняться программированием.Посмотрел пару видео и дошел до этого.Мой мозг где то сзади на стене остался.Но я не буду опускать руки.
А так спасибо за видео все очень интересно и понятно(но пока не мне).
Аха-ха-ха))), ни в коем случае не опускайте руки, программисты с таким чувством юмора очень нужны).
Да ладно, все более чем доступно Дарья объясняет.
В школах бы так объясняли.
А то сухую теорию ребятишкам гонят...
Один хороший программист с 40 летним опытом мне сказал начинай читать книгу и когда глаза уже как по стеклу ездят и ничего не понимаешь от обьема новой информации закрывай ее отдыхай часик а потом начинай читать ее задом наперед и так по кругу пока в середину не дойдешь с дух сторон =))
@@MrNastoyashiy лол=)
@@TheTalants если новичок посмотрит даже это видео, то вряд ли поймёт с 1 раза, если вернётся через неделю, может быть меньше, хоть немного разобравшись с сортировка, то поймёт =)
Здравствуйте. От куда известно что N это количество элементов и почему а это указатель на массив ❓❓❓
Спасибо большое за столь подробное видео!
Наконец-то разобралась с сортировками и успешно сдала зачет. :)
Большое спасибо, Dalila, спасибо, что нашли время и написали про сдачу зачета))! Я очень рада))!
Лет 20 назад на бэйсике эти сортировки делал а вот теперь ради спортивного интереса хотел повторить и оказывается напрочь забыл. Вы хорошо представляете материал... классно. Хотя такой как я всё.ровно непоймет... мне надо просто часами разглядывать код, так и вникал. Помню была представлена программа "жизнь" с подробным объяснением но не мог понять как это работает очень долго сверлил глазами код а когда дошло то радости было наверно больше чем у тех кто этот код придумал
Как это в пузырьковой не получится, в сортировке вставками это рабатало компьютер справлялся с одним ящиком, а в пузырьковой понадобилось почему-то три ящика🤣🤣🤣❓❓❓❓
Откуда и для чего появилось j и почему емуу присвоен элемент 3. Если это часть массива i который временно помещён в ящичек🤯❓❓❓❓
int j = i - 1;
while...
j--;
что мешало использовать for?
for (int j = i - 1; ... j--) {
...}
Непонятно где показано что в нашем ящичке находится карта с номером 3. В данной строке видно что есть якобы какой-то ящичек типа х которому присвоен типа указатель на массив а с каким-то индексом но непонятно каким❓❓❓❓🤯
Непонятно для чего j, у нас что два массива ❓❓❓ и почему в сортировке вставками мы могли обойтись без b🤣 а тут мы не можем тут мы вдруг так не умеем❓❓❓
Опять же где в коде указано на перемещение всех карт❓❓❓❓и почему последняя карта это отдельная итерация❓❓❓❓
При сортировке вставкой у вас будет выход за границы массива для любого случая, когда наименьший элемент первоначально не стоит на первом месте, поэтому прежде чем сортировать необходимо сначала расположить «самый легкий элемент» в а[0]
thanks
А почему перескочил через две строки❓❓❓
Ну, почему мы не встретились раньше? и программирование бы легче пошло)
👍😁
Вообще не понятно что в коде делает j ❓❓❓
блин, пока слушал второй способ сортировки, сам додумался до сортировки выбором. Думал что я гений, а нет просто изобрел велосипед
Большое спасибо!
А куда она плывёт в начале?
домой с работы lol
Как бы это по мягче то. Ошибок я сам могу написать кучу. Уж будте любезны, ссылку на иделальный код в описании на яндекс диск или гидхаб.
Лучше делать отдельные уроки по разбору ошибок.
Это взрывает мозг.👣💆
Мало того, что он напрягался так ещё и это.
Вы как всегда очень обоятельны.
insertion sort big O n в квадрате, есть лучше алгоритмы- n log n average case, log n best case для некоторых.
Вы так быстро пишете код? Или это перемотка? Я офигел от скорости...
HACKER MAN
Как вам учебник герберт шилдт с++ базовый курс 3 издание? И стоил ли начинать изучать с++98 в 2021 году.
Есть ли разница в использования вашего кода, и например, вот такого: (сортировка вставками) ?
for(int i = 0; i < N-1; i++)
for(int j = i; (j >= 0) && (A[j] > A[j+1]); j--) {
buf = A[j];
A[j] = A[j+1];
A[j+1] = buf;
}
И еще вопрос: зачем задействовать новую переменную для A[i], если можно в условии ставить прямо: if(A[j] < A[i]) ?
Различие в алгоритме, при сортировки вставками, Вы как бы сдвигаете элементы, перезаписывая их, а в Вашем варианте идёт обмен, по-моему, она похожа на пузырек.
А насчёт переменной, это дело вкуса, мне проще так объяснять, называя переменную отдельным именем.
Новая переменная x = A[i] выполняет роль буфера(временного хранилища) для сдвига нового элемента массива в подходящее место. Так как на каждом шаге необходимого сдвига мы стираем значение нового элемента массива перезаписывая вместо него следующее неподходящее значение, а той переменной где храниться неподходящее значение которое было взято для перезаписи нового, присваиваем значение нового элемента массива которое мы заранее сохранили в переменной x.
Где в коде указано на замену i = 0 на i = 1❓❓❓ а так же с другими i ❓❓❓
реализация сортировки вставкой используя вложенный цикл for возможно выглядит более понятно
#include
#define COUNT 19
#define START_SORT_INDEX 0
void *insertion_sort* (int* a, int N) *{*
int x;
for (int i = 1; i < N; i++){
x = a[i];
int j;
for (j = i; x < a[j-1] && j > 0; j--) a[j] = a[j-1];
a[j] = x;
}
*}*
int main(){
int mass[] = {8,6,4,1,3,7,2,11,5,9,10,14,12,13,22,16,15,19,17};
int length_mass = sizeof(mass)/sizeof(int);
if ((length_mass - COUNT - START_SORT_INDEX + 1) < 1){
printf("Incorect COUNT OR START_SORT_INDEX
");
return -1;
}
insertion_sort(&mass[START_SORT_INDEX], COUNT);
for(int i = 0; i < length_mass; i++) printf(" %d ", mass[i]);
}
При копировании кода из браузера в редактор - не компилиться
error: stray '\357' in program
error: stray '\273' in program
error: stray '\277' in program
error: stray '#' in program
Бесят меня такие ругачки, отвлекают от работы и очевидного решения нет. Смотришь на код, вроде все нормально, а программа не компилируется. А дело на самом деле в том, что в тексте есть невидимый символ, который стоит в самом начале или в конце .
Короче, чтобы решить проблему нужно открыть файл в режиме HEX и удалить непотребные символы , а затем сохранить и тогда будет счастье.
Для Windows торрент файл на HEX редактор можно скачать тут nnm-club.name/forum/viewtopic.php?t=1036101
меня тоже), спасибо за способ, надо попробовать).
Расходимся,это не Августина(
Дарья, в сортировке InsertionSort необходимо добавить ещё одно условие
while (j >= 0 && x < a[j])
иначе возможна ситуация, когда индекс выйдет за границы массива и получится ошибка времени выполнения.
После просмотра нескольких твоих видео, сразу подписался, несмотря на обилие на ютуб информации по программированию, нашёл для себя много полезного, у тебя очень неординарная подача. Всё сразу становится понятно!
А в начале, когда сбоку в рекомендованных твои ролики выпадали, как-то не решался нажать, сидит какой-то стереотип, что не женское это дело, код писать, даже подумал "стёб" какой-то. Но был приятно удивлён твоим уровнем знаний, а ещё больше удивлён, что ты вообще балдеешь от данного вида деятельности)
Да, это правильный ответ! Вы молодец! :) Первый внимательный зритель)). ( ruclips.net/video/zHMEclmUXOM/видео.html )
Grumnum, большое спасибо).
тоже когда читал подумал а не вылетит ли это за пределы)
А покажи полный код, иначе это алгоритм как дал ошибку, так и даёт
какое очарование! спасибо за ролик, очень наглядно и познавательно.
Можно это сделать и без ящика (х который)
В цикле for мы видим что i=1 допустим что с него начинается сравнение i=0, но причём здесь i меньше количества элементов(i
потому что идем по всем элементам
Отличное и понятное видео, большое спасибо 👍🏻
5:51 на самом деле у процессора есть инструкция обмена регистрами. а ещё есть std::swap().
и да, сортировку пузырьками можно реализовать без лишней переменной changed.
swap здесь не подойдёт, нужно самыми простыми методами написать.
спасибо это видео очень помогло разобраться с сортировкой методом выбора )
Здравствуйте, Дарья! случайно наткнулся на ваш канал и сразу подписался. Я давно уже не юн, но программирование изучать стал недавно. Однако, есть проблема: когда смотрю ваше видео - о программировании никак думать не получается. Какие там алгоритмы, ваша улыбка и голос просто завораживают. А скажите, вы замужем?
Здравствуйте, Александр))! Спасибо, я рада, что Вам нравятся мои видео)). Я не люблю отвечать на личные вопросы, но почему-то это самый часто задаваемый вопрос)). Я в разводе.
Видел Ваши видео раньше. Что-то не сильно обратив внимание. А сейчас так подсел!) Ну пусть квадратические сортировки - это супер просто, но всё равно прикольно!
Спасибо, Богдан!
напишите еще код для сортировки слиянием
Здравствуйте, Дарья, у меня возник вопрос - у вас в сортировке вставками индекс j в видео принимает отрицательное значение, хотя по условию и логике j>=0, объясните пожалуйта
Вы молодец), объяснение в инфобоксе под видео). Ответ ruclips.net/video/zHMEclmUXOM/видео.html
Сложно... Понял только с 10 просмотра.
(Я фейк). Вы очень очень похожи на подругу Даши в отеле Элеон. Её Юля зовут. Удивительно
Люди вообще все очень похожи).
Дарья, я вот только начал смотреть видео, а именно функцию insertion_sort() и сразу же увидел ошибку :-( У вас есть переменная j, которая декрементируется, но нет проверки что эта j выйдет в отрицательное значение и начнет "безобразничать" по адресам памяти, меньшим чем адрес начала массива. Могу пример привести:
int bigArray[ 5] = { 100, 99, 98, 97, 96}; // объявили массив из пяти элементов
insertion_sort( &bigArray[2], 3); // хотим отсортировать 3 последних элемента массива, а два первых функция не должна трогать.
Но после выполнения функции мы видим, что функция "прошлась" и по первым двум элементам и поменяла их.
Тьфу, эту ошибку уже давно заметили, а я то думал что это я один такой умный выискался. Всё, посыпаю голову пеплом и замираю в глубоком пардоне.
🤣
Подскажите пожалуйста, полное название книги, которая стоит на полке: "Ядро..." ?
"Ядро Linux" Бовет, Чезати
Классное видео, помогло)
а почему нельзя использовать в пузырьковом способе функцию swap()? я знаю что пузырьковый метод такой, но его можно же упростить и все.
потому что на собеседованиях любят вопросы про сортировки и часто просят написать какую-нибудь (обычно пузырьковую), не пользуясь никакими функциями.
а так, конечно, лучше пользоваться библиотечными методами.
понятно, а вы сейчас работаете где нибудь? Я просто учусь пока и изучаю С++ как раз, вот скажите как тренироваться после изучения основ, ну даже основы ты уже понял, как перейти к практике ооп, просто нигде не найти задания для такой более сложной части программирования. И еще вопрос, вы говорите что устраивались на первую работу зная хорошо С++ , а остальные поверхностно, это как? Просто основы?. И например на сколько хорошо вы знали С++, вы могли сделать приложение на с++ и многое другое? Или что то в узкой сфере?
Да, работаю, в своей фирме, программирую на Java и python.
"Хорошо зная", значит я написала 3-4 курсовые и защитила бакалавра на С++.
Сейчас, напрягусь, и пару вспомню: дофичивание текстового редактора на GTK (это ещё на C было) , визуализация графов, моделирование ИК пропускания КРТ на подложках CdZnTe для ФГУП Гиредмет. Это были довольно самостоятельные приложения, последнюю программу я ездила устанавливала прямо на предприятие и рассказывала, как им пользоваться.
ну разве только если инлайн. Почитайте про этапы запуска функции и вы поймете что накладные расходы процессорного времени на запуск функции слишком велики для короткого тела функции свап.
Вот ведь какая незадача.
Из всех названий сортировок, я знал только "пузырьковую" (:-)),
НО!
Задай мне на собеседовании вопрос подобного характера, я бы смог написать программу сортировки, даже разными способами...
Только это было бы свеже придуманная мной функция (метод) и я в упор даже не смог бы предположить, к какому типу сортировки моя функция относится.
Налицо отсутствие высшего образования с математическим уклоном :)
Как так люди живут... (без высшего образования) :)
Как часто в реальной практике приходится сортировать массив?
В моей практике - раз в день, раз в неделю. И обычно используются уже готовые методы сортировки.
Daria Emacs Добрый день, зачем тогда на собеседованиях просят написать алгоритм сортировки на листе бумаги, если все и так используют готовые методы?
с праздником Вас ! С днем весны и женским днем ! %)
Спасибо большое! Так приятно! :))))
@@DariaEmacs Здоровья и счастья Вам и вашему дому !
❤️🥰😊
Дарья, спасибо Вам!
Спасибо, Дмитрий! :)
Вы лучше всех объяснили, спасибо огромное ✨👏
Не вижу новых видео???
Я тоже
@@DariaEmacs Все видео 2-3 летней давности.
@@DariaEmacs Прошу прощения, есть и другие.
Да, есть)).
Почему девушки программисты так любят хвастаться?
потому что -- девушки
Спасибо вам за ваш труд, за то что делитесь своим пониманием с другими..а еще вы милашка!!!
Спасибо Вам за Ваш комментарий, Garry! :)
Даша ты работаешь сейчас только на c++?
Андрей, нет сейчас еще на java и python.
на python для web не разрабатываешь?
только для web и разрабатываю).
как относишься к фреймворку flask? И не хотела бы сделать курс типа приложение spa на angular 6 и api на python?
я к нему никак не отношусь, использую другие инструменты).
Ох меня уже эти сортировки извели даже пузырьковую понять не могу в плане кода. Если после просмотра этого видео ничего не пойму то я сдался.
Не сдавайтесь)), все получится!
А какой способ самый быстрый?
Из усовершенствованных сортировок quicksort (это сортировка используется в стандартной библиотеке C++ называется std::sort) nlog(n), но есть сортировки и быстрее, но требуют дополнительных ресурсов (память) и определенных условий, к примеру сортировка подсчетом для идущих подряд положительных чисел, сложность у нее ~ n.