3. Алгоритмы и структуры данных. Сортировки

[@ilyalapitan6808]

Алгоритм на 9:17 Сортировка пузырьком: bool sorted = true; while (!sorted) { ... } => while( false){ ... } переменная sorted должна быть проинициализирована значением false, иначе не выполняется условие оператора while, и код в теле цикла не будет выполнен.

[@ИльяШумилин-н2и]

Вы не правы, значение переменной sorted меняется на false в том случае, когда будет произведена хотя бы одна перестановка в ходе цикла, иначе она остается true и цикл заканчивается(массив отсортирован). Если она в начале каждого цикла будет false , то произойдет зацикливание и он не закончится никогда

[@mcvladthegoat]

при начальном значении boolean = true в цикл даже не удастся зайти. А если проинициализировать как false, то все как раз отработает при неизменном теле цикла

[@QWEqaz123ification]

Это не единственная ошибка в его лекциях, увы.

[@Mamaikan]

Еще алгоритм можно простым действием оптимизировать, уменьшая после каждой итерации цикла while значение n на 1. В таком случае цикл действительно будет работать за n-1, n-2, n-3... операций. В том виде, как указано на слайде, алгоритм будет каждый раз сравнивать уже отсортированную часть справа, что итого приведет к n-1, n-1, n-1... операций.

[@PeterSidoroff]

У меня от этого преподавателя двоякое впечатление - вроде все толково объясняет, но такие элементарные ляпы на слайдах делает, которые сразу бросаются в глаза и вызывают небольшое раздражение. Видимо, единственное разумное объяснение - возраст или проблемы с глазами. Конечно, можно еще предположить, что это кто-то из его нерадивых студентов делает за него слайды ("за зачет"), но даже в таком случае, все равно же надо какое-то ревью делать самому. Ведь твоя работа - это зеркало тебя самого, твоего мышления. Мне было бы стыдно выставлять публично такие сырые "эскизы".

[@ttatiana721]

Поправка к слайду 11:22 про сортировку вставками: На первом проходе, пузырек не нужен. Мы просто говорим: проход №1, первый 1 элемент массива упорядочен (так как последовательность из одного элемента всегда упорядочена). Дальше проход №2, делаем так, чтобы первых 2 элемента массива были упорядочены. Итд. Спасибо за лекции, они замечательные!

[@FF-ne2qz]

Чтоб у меня был такой преподаватель!

[@ttatiana721]

Поправка к слайду 39:35 про k-статистику: в пункте 3, оба вхождения |Sr| должны быть заменены на |Sv|. Особенно это видно по последней строке, где k-|Sr|-|Sv| должно быть положительным. |Sr| - мощность правого множества - нас вообще нигде не должна интересовать, раз ищем k-минимум.

[@EshkinKot1980]

Еще бы он дал корректное определение k-ой порядковой статистики. Смотрю на алгоритм, и кажеться, что сюр какой-то. Но как только нашел на википедии правильное определение, понял, что алгоритм рабочий, с вашими замечаниями, конечно. Материал подобран неплохо, но лектор так себе.

[@ttatiana721]

Поправка к 1:23:11 "Могли бы мы сортировку начать со старшего разряда?" - На самом деле - нет, только с младшего. Достаточно попробовать, чтобы в этом убедиться. Но лекции отличные.

[@ДмитрийЧебанов-ю1м]

Сортировка вставками зачем 3 цикла вместо двух?. Количество открывающихся скобок больше чем закрывающихся, переменная v нигде не определена. Неужели сложно было хотя бы попробовать скомпилировать??

[@glebchik]

В сортировке Шелла наверное лучше второй цикл for записать как for (h = h / 3; h > 0; h /= 3) потому что последний найденный шаг здесь for (h = 1; h n

[@wdtv80]

Опубликуйте слайды для 3 и 4 лекций!

[@D0sart]

Алгоритм поиска k-й порядковой статистики. Как разбить массив на три части, не используя дополнительной памяти, если есть повторяющиеся элементы?

[@ДмитрийЧебанов-ю1м]

Сортировка вставками - на одном слайде говорит что в лучшем и худшем случае работает за одно время. На следующем слайде себя опровергает.

[@Megapixxxell]

на скорости 1.75 самое то

[@dannylones2159]

2

[@SiteBizzona]

Можно и одним циклом без while, вот к примеру $data = [1,5,2,1,8,4,11,4,17,22,1]; function mySort($data) { $cnt = count($data); for($i=0;$i= 0 && ($data[$i] > $data[$i-1]) ) { list($data[$i], $data[$i-1]) = [$data[$i-1], $data[$i]]; $i = 0; } } return $data; } Но, а в самом коде с while ошибка - нет проверки на выход за пределы и начальное условие не верно function TestSort(array $data) { $sorted = false; while(!$sorted) { $sorted = true; for($i = 0; $i < count($data); $i++) { if(isset($data[$i+1]) && ($data[$i] > $data[$i+1])) { $temp = $data[$i+1]; $data[$i+1] = $data[$i]; $data[$i] = $temp; $sorted = false; } } } return $data; } $data = [8,1,4,2,7,44,22,77,11]; print_r(TestSort($data)); Yiideveloper.ru

[@AndreyGroza]

Можно, но ведь такая запись гораздо менее читаема

[@davvoprod.851]

Мне кажется, или у дядьки голова трясётся