Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Сортировка массивов PHP: Массивы

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

  1. Что вы знаете об алгоритмах
  2. Умеете ли вы писать свои реализации алгоритмов
  3. Как работает ваше алгоритмическое мышление

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

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

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

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

Сортировка

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

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

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

  • zenozeng.github.io/bubble-sort-visualization
  • visualgo.net/ru/sorting
  • cs.usfca.edu/~galles/visualization/ComparisonSort.html

Рассмотрим такой код:

<?php

function bubbleSort($coll)
{
    $size = count($coll);
    // Цикл do..while работает почти как while
    // В отличие от while, этот цикл делает проверку после выполнения тела, а не до нее
    // Цикл do..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 и произошла перестановка,
                // мы присваиваем значение true переменной swapped
                $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

Аватары экспертов Хекслета

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

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

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

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

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

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

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

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

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы
профессия
от 6 300 ₽ в месяц
Разработка веб-приложений на Laravel
10 месяцев
с нуля
Старт 18 апреля

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

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

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»