Алгоритм на 9:17 Сортировка пузырьком: bool sorted = true; while (!sorted) { ... } => while( false){ ... } переменная sorted должна быть проинициализирована значением false, иначе не выполняется условие оператора while, и код в теле цикла не будет выполнен.
Вы не правы, значение переменной sorted меняется на false в том случае, когда будет произведена хотя бы одна перестановка в ходе цикла, иначе она остается true и цикл заканчивается(массив отсортирован). Если она в начале каждого цикла будет false , то произойдет зацикливание и он не закончится никогда
при начальном значении boolean = true в цикл даже не удастся зайти. А если проинициализировать как false, то все как раз отработает при неизменном теле цикла
Еще алгоритм можно простым действием оптимизировать, уменьшая после каждой итерации цикла while значение n на 1. В таком случае цикл действительно будет работать за n-1, n-2, n-3... операций. В том виде, как указано на слайде, алгоритм будет каждый раз сравнивать уже отсортированную часть справа, что итого приведет к n-1, n-1, n-1... операций.
У меня от этого преподавателя двоякое впечатление - вроде все толково объясняет, но такие элементарные ляпы на слайдах делает, которые сразу бросаются в глаза и вызывают небольшое раздражение. Видимо, единственное разумное объяснение - возраст или проблемы с глазами. Конечно, можно еще предположить, что это кто-то из его нерадивых студентов делает за него слайды ("за зачет"), но даже в таком случае, все равно же надо какое-то ревью делать самому. Ведь твоя работа - это зеркало тебя самого, твоего мышления. Мне было бы стыдно выставлять публично такие сырые "эскизы".
Поправка к слайду 11:22 про сортировку вставками: На первом проходе, пузырек не нужен. Мы просто говорим: проход №1, первый 1 элемент массива упорядочен (так как последовательность из одного элемента всегда упорядочена). Дальше проход №2, делаем так, чтобы первых 2 элемента массива были упорядочены. Итд. Спасибо за лекции, они замечательные!
Поправка к слайду 39:35 про k-статистику: в пункте 3, оба вхождения |Sr| должны быть заменены на |Sv|. Особенно это видно по последней строке, где k-|Sr|-|Sv| должно быть положительным. |Sr| - мощность правого множества - нас вообще нигде не должна интересовать, раз ищем k-минимум.
Еще бы он дал корректное определение k-ой порядковой статистики. Смотрю на алгоритм, и кажеться, что сюр какой-то. Но как только нашел на википедии правильное определение, понял, что алгоритм рабочий, с вашими замечаниями, конечно. Материал подобран неплохо, но лектор так себе.
Поправка к 1:23:11 "Могли бы мы сортировку начать со старшего разряда?" - На самом деле - нет, только с младшего. Достаточно попробовать, чтобы в этом убедиться. Но лекции отличные.
Сортировка вставками зачем 3 цикла вместо двух?. Количество открывающихся скобок больше чем закрывающихся, переменная v нигде не определена. Неужели сложно было хотя бы попробовать скомпилировать??
Алгоритм на 9:17 Сортировка пузырьком:
bool sorted = true;
while (!sorted) { ... } => while( false){ ... }
переменная sorted должна быть проинициализирована значением false, иначе не выполняется условие оператора while, и код в теле цикла не будет выполнен.
Вы не правы, значение переменной sorted меняется на false в том случае, когда будет произведена хотя бы одна перестановка в ходе цикла, иначе она остается true и цикл заканчивается(массив отсортирован). Если она в начале каждого цикла будет false , то произойдет зацикливание и он не закончится никогда
при начальном значении boolean = true в цикл даже не удастся зайти. А если проинициализировать как false, то все как раз отработает при неизменном теле цикла
Это не единственная ошибка в его лекциях, увы.
Еще алгоритм можно простым действием оптимизировать, уменьшая после каждой итерации цикла while значение n на 1. В таком случае цикл действительно будет работать за n-1, n-2, n-3... операций. В том виде, как указано на слайде, алгоритм будет каждый раз сравнивать уже отсортированную часть справа, что итого приведет к n-1, n-1, n-1... операций.
У меня от этого преподавателя двоякое впечатление - вроде все толково объясняет, но такие элементарные ляпы на слайдах делает, которые сразу бросаются в глаза и вызывают небольшое раздражение. Видимо, единственное разумное объяснение - возраст или проблемы с глазами. Конечно, можно еще предположить, что это кто-то из его нерадивых студентов делает за него слайды ("за зачет"), но даже в таком случае, все равно же надо какое-то ревью делать самому. Ведь твоя работа - это зеркало тебя самого, твоего мышления. Мне было бы стыдно выставлять публично такие сырые "эскизы".
Поправка к слайду 11:22 про сортировку вставками:
На первом проходе, пузырек не нужен. Мы просто говорим: проход №1, первый 1 элемент массива упорядочен (так как последовательность из одного элемента всегда упорядочена).
Дальше проход №2, делаем так, чтобы первых 2 элемента массива были упорядочены. Итд.
Спасибо за лекции, они замечательные!
Поправка к слайду 39:35 про k-статистику: в пункте 3, оба вхождения |Sr| должны быть заменены на |Sv|. Особенно это видно по последней строке, где k-|Sr|-|Sv| должно быть положительным.
|Sr| - мощность правого множества - нас вообще нигде не должна интересовать, раз ищем k-минимум.
Еще бы он дал корректное определение k-ой порядковой статистики. Смотрю на алгоритм, и кажеться, что сюр какой-то. Но как только нашел на википедии правильное определение, понял, что алгоритм рабочий, с вашими замечаниями, конечно.
Материал подобран неплохо, но лектор так себе.
Поправка к 1:23:11 "Могли бы мы сортировку начать со старшего разряда?" - На самом деле - нет, только с младшего. Достаточно попробовать, чтобы в этом убедиться. Но лекции отличные.
Чтоб у меня был такой преподаватель!
В сортировке Шелла наверное лучше второй цикл for записать как
for (h = h / 3; h > 0; h /= 3)
потому что последний найденный шаг здесь for (h = 1; h n
Сортировка вставками зачем 3 цикла вместо двух?. Количество открывающихся скобок больше чем закрывающихся, переменная v нигде не определена. Неужели сложно было хотя бы попробовать скомпилировать??
Алгоритм поиска k-й порядковой статистики. Как разбить массив на три части, не используя дополнительной памяти, если есть повторяющиеся элементы?
Опубликуйте слайды для 3 и 4 лекций!
Сортировка вставками - на одном слайде говорит что в лучшем и худшем случае работает за одно время. На следующем слайде себя опровергает.
Можно и одним циклом без 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
Можно, но ведь такая запись гораздо менее читаема
на скорости 1.75 самое то
2
Мне кажется, или у дядьки голова трясётся