Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос нашим менторам. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Сортировка массивов

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

  1. Насколько вы вообще в курсе о существовании алгоритмов.
  2. Способны ли вы программировать.
  3. Как работает ваше алгоритмическое мышление.

Знание алгоритмов действительно влияет на то, как вы думаете и насколько быстро соображаете. И хотя невозможно знать все алгоритмы, нужно хотя бы иметь представление о самых ключевых и в идеале уметь их реализовывать. В нашем списке рекомендуемых книг есть как минимум одна книга, полностью посвящённая алгоритмам.

Кроме того, Роберт Мартин (авторитетный программист, по книгам которого учится весь мир) в своей книге «Идеальный программист» рассказывает о подходе Ката — понятии, взятом из боевых искусств.

Принцип изучения боевого искусства на основе ката состоит в том, что повторяя ката многие тысячи раз, практик боевого искусства приучает своё тело к определённого рода движениям, выводя их на бессознательный уровень. Таким образом, попадая в боевую ситуацию, тело работает «само» на основе рефлексов, вложенных многократным повторением ката. Также считается, что ката обладают медитативным воздействием.

Роберт рекомендует время от времени решать классические алгоритмические задачки для поддержания формы. Эта тема стала настолько популярной, что если загуглить php github kata, то вы увидите множество репозиториев с подобными задачками.

Сортировка

Способов сортировать массив достаточно много. Самый популярный для обучения — пузырьковая сортировка (bubble sort).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).

В интернете можно найти сервисы, визуализирующие процесс сортировки, что очень помогает пониманию, например:

<?php

function bubbleSort($coll)
{
    $size = count($coll);
    // do..while цикл. Работает почти идентично while
    // Разница в проверке. Тут она делается не до выполнения тела, а после.
    // Такой цикл полезен там, где надо выполнить тело хотя бы раз в любом случае.
    do {
        // Объявляем переменную swapped, значение которой показывает был ли
        // совершен обмен элементов во время перебора массива
        $swapped = false;
        // Перебираем массив и меняем местами элементы, если предыдущий
        // больше, чем следующий
        for ($i = 0; $i < $size - 1; $i++) {
            if ($coll[$i] > $coll[$i + 1]) {
                // temp – временная переменная для хранения текущего элемента
                $temp = $coll[$i];
                $coll[$i] = $coll[$i + 1];
                $coll[$i + 1] = $temp;
                // Если сработал if и была совершена перестановка,
                // присваиваем swapped значение true
                $swapped = true;
            }
        }
        // Уменьшаем счетчик на 1, т.к. самый большой элемент уже находится
        // в конце массива
        $size--;
    } while ($swapped); // продолжаем, пока swapped === true

    return $coll;
}

print_r(bubbleSort([3, 2, 10, -2, 0]));
// => Array
// => (
// =>     [0] => -2
// =>     [1] => 0
// =>     [2] => 2
// =>     [3] => 3
// =>     [4] => 10
// => )

https://repl.it/@hexlet/php-arrays-sorting-bubble

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

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

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


Дополнительные материалы

  1. Сортировка средствами php

<span class="translation_missing" title="translation missing: ru.web.courses.lessons.mentors.mentor_avatars">Mentor Avatars</span>

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят менторы из команды Хекслета или другие студенты.

Для полного доступа к курсу нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, даст возможность обращаться за помощью к менторам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов

Зарегистрироваться

или войти в аккаунт

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

Отправляя форму, вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».