Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 Сортировка массивов - самая базовая алгоритмическая задача, которую нередко обсуждают на собеседованиях. С другой стороны, в реальном коде массивы сортируют, используя уже готовые функции стандартной библиотеки. Тогда зачем задают подобные вопросы? Обычно интервьюер хочет узнать:

2 <ol><li>Что вы знаете об алгоритмах</li>

3 <li>Умеете ли вы писать свои реализации алгоритмов</li>

4 <li>Как работает ваше алгоритмическое мышление</li>

5 </ol>Знание алгоритмов действительно влияет на то, как вы обдумываете задачи и насколько быстро их решаете. Невозможно знать все алгоритмы, но нужно хотя бы иметь представление о самых ключевых алгоритмах, а в идеале - уметь их реализовывать. В<a>нашем списке рекомендуемых книг</a>есть как минимум одна книга, полностью посвященная алгоритмам.

6 Кроме того, советуем изучить работы Роберта Мартина - авторитетного программиста, по книгам которого учится весь мир. В своей книге "Идеальный программист" он рассказывает о<a>ката</a>- подходе из боевых искусств:

7 <blockquote>Изучение боевого искусства на основе ката - это повторение практик многие тысячи раз. В боевых искусствах ката приучает тело к определенным движениям и выводит их на бессознательный уровень. В боевой ситуации тело работает на основе рефлексов, вложенных многократным повторением ката. Также считается, что ката обладают медитативным воздействием.

8 </blockquote>Роберт Мартин рекомендует регулярно решать классические алгоритмические задачки для поддержания формы. Эта тема очень популярна - по запросуphp kataна GitHub можно найти множество репозиториев с подобными задачками.

9 <h2>Сортировка</h2>

10 Есть много способов сортировать массив. В материалах для начинающих программистов чаще всего встречается<a>пузырьковая сортировка</a>(bubble sort).

11 Этот алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно. Если порядок в паре неверный, выполняется обмен элементов. Когда алгоритм проходит по внутреннему циклу, каждый раз очередной наибольший элемент массива ставится на свое место в конце массива рядом с предыдущим "наибольшим элементом". При этом наименьший элемент перемещается на одну позицию к началу массива - "всплывает" до нужной позиции, как пузырек в воде. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе перестановка не потребуется.

12 Есть много сервисов, которые наглядно показывают процесс сортировки:

13 <ul><li><a>zenozeng.github.io/bubble-sort-visualization</a></li>

14 <li><a>visualgo.net/ru/sorting</a></li>

15 <li><a>cs.usfca.edu/~galles/visualization/ComparisonSort.html</a></li>

16 </ul>Рассмотрим такой код:

17 Весь код делится на два уровня:

18 <ol><li>Внутренний цикл for, который проходит по массиву от начала до конца, меняя элементы попарно, если нужно сортировать</li>

19 <li>Внешний цикл while..do, который останавливает сортировку. В худшем случае этот цикл выполнится count($coll) раз, что совпадает с теоретическим худшим случаем этого алгоритма, при котором самый большой или маленький элемент находятся в противоположных концах массива от сортированного варианта</li>

20 </ol>Мы меняем входной массив напрямую, но это никак не скажется на массиве, который был передан внутрь функции. Он останется таким же, каким был до входа в функцию. По сути, внутри мы работаем с копией, которую возвращаем наружу после сортировки.