Пузырьковая сортировка и бинарный поиск на PHP (обучение, эксперименты)

[JekaMas]

Тут даже пооптимизировать можно. Например, зачем в цикле по j идти по всем элементам массива — часть массива же уже отсортирована на предыдущих шагах.

[volmir]

$j зависит $iterations. А $iterations постоянно уменьшается. Т.е. все о чем вы пишите — реализовано.
Спасибо за замечание. Оптимизацию можно провести эвристически :) — реализовать более продвинутые алгоритмы сортировки.

[volmir]

Посмотрел таки в Википедию :) Для реализации полноценной пузырьковой сортировки надо ввести отдельную переменную, которая будет проверять, если ли перемещения элементов в текущем цикле. Если их нет — то сортировка завершена, выход из цикла.

[volmir]

Исправил код в статье и в репозитории (Hot fix :)).

[Ruckus]

Занятно, но мы проходили оба алгоритма на первом курсе института, абы не в школе (бинарный поиск так точно в школе). Что здесь нового/интересного для аудитории хабра?

[volmir]

Извините, я понимаю, что это уровень первого курса в ВУЗе. Вот я до этого уровня только дорос :)
Интересного для Хабра может быть то, что все делается в комплексе, например (алгоритм -> юнит-тест -> нагрузочное тестирование). Или интересным будет то, что подобные алгоритмы достаточно просты для реализации и не надо на курсы тратиться и ходить в течении нескольких месяцев. А все можно изучить самостоятельно быстрее и дешевле.

[ghost404]

Не стоит говорить за всех. Я учился на вечерке и все алгоритмы прошли мимо меня, о чем я сейчас жалею.

[Ramires]

Дождались! Bubble sort на хабре.

[volmir]

Ещё раз прошу прощения за слишком простую статью (как для всего сообщества в целом).

[Lexx918]

А почему на тестах сравнивается нативный sort с баблом? Почему не с быстрой сортировкой, например?

[volmir]

Сравнивать можно различные сортировки друг с другом. Думаю, на эту тему много кто писал более серьезные исследования. Я просто взял две сортировки (нативную на PHP и свою реализацию) и сравнил их.

[impwx]

Две последние строки в результатах тестирования поиска: массив на порядок больше, время выполнения на порядок меньше! Как так получилось?

[volmir]

Может дело в том, что я брал одно число для поиска?
Я видел это и пробовал менять код, запускать этот кусок отдельно, менять число для поиска — результат не менялся.
Сам удивлен этим фактом.

[GeMir]

Сортировки сортировками, но вот вертикальное представление массива вижу впервые :)

[GeMir]

Вы же в курсе, что у строительного уровня, расположенного на горизонтальной поверхности, пузырьки (а точнее пузырёк) будет строго по центру?

[volmir]

Я сам был удивлен в начале подобным представлением. А потом понял (прочитал) — что это как бы наглядная иллюстрация к пузырьковой сортировке: «тяжелые» (большие) числа опускаются на дно, а «легкие» (маленькие) числа всплывают наверх :)