Базовые алгоритмы сортировки (PHP)

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

---

Алгоритмы сортировки

Сортировка пузырьком

Описание:  Сортировка пузырьком — один из простейших алгоритмов сортировки. Он многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока массив не будет отсортирован.

Алгоритм:

1. Пройтись по массиву от первого до последнего элемента.
2. Сравните каждый элемент с соседним элементом.
3. Если текущий элемент больше следующего, поменяйте их местами.
4. Повторяйте процесс, пока массив не будет отсортирован.

Реализация на PHP:

function bubbleSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // Swap elements
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// Example function call
$arr = [64, 34, 25, 12, 22, 11, 90];
$sortedArr = bubbleSort($arr);

echo "Sorted array: ";
print_r($sortedArr);

Сложность:

• Худший случай: O(n²) — возникает, когда массив сортируется в обратном порядке.
• Лучший случай: O(n) — если массив уже отсортирован, пузырьковая сортировка может выполнить минимальное количество операций.

---

Сортировка по выбору

Описание:  Сортировка выбором находит наименьший элемент в массиве и меняет его местами с первым элементом. Затем алгоритм повторяет этот процесс для оставшейся неотсортированной части массива.

Алгоритм:

1. Пройдитесь по массиву и найдите минимальный элемент.
2. Поменяйте его местами с первым элементом.
3. Повторите эти действия для оставшейся части массива.

Реализация на PHP:

function selectionSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        // Swap the found minimum element with the first element
        $temp = $arr[$minIndex];
        $arr[$minIndex] = $arr[$i];
        $arr[$i] = $temp;
    }
    return $arr;
}

// Example function call
$arr = [64, 25, 12, 22, 11];
$sortedArr = selectionSort($arr);

echo "Sorted array: ";
print_r($sortedArr);

Сложность:

• Худший и лучший случай: O(n²), так как количество операций не зависит от того, отсортирован ли массив.

---

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

Описание:  Сортировка вставками работает как сортировка карт в вашей руке: элементы массива вставляются в правильную позицию среди уже отсортированных элементов.

Алгоритм:

1. Начните со второго элемента и рассмотрите его как часть отсортированной последовательности.
2. Вставить текущий элемент в правильную позицию в отсортированной части массива.
3. Повторите для всех элементов.

Реализация на PHP:

function insertionSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        // Move elements greater than the key one position ahead
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

// Example function call
$arr = [12, 11, 13, 5, 6];
$sortedArr = insertionSort($arr);

echo "Sorted array: ";
print_r($sortedArr);

Сложность:

• Худший случай: O(n²) — возникает, когда массив сортируется в обратном порядке.
• Лучший случай: O(n) — если массив уже отсортирован.

Рекомендуемая литература:

1. «Изучаем алгоритмы» Адитьи Бхаргавы.  Отличная книга для начинающих, в которой объясняются основные алгоритмы с наглядными иллюстрациями и примерами (написана на Python, но может быть легко адаптирована для PHP).
2. «Введение в алгоритмы» Томаса Кормена и др.  Классическая книга по алгоритмам, охватывающая более сложные и продвинутые алгоритмы, такие как быстрая сортировка и сортировка слиянием.
3. «Алгоритмы PHP» Мизанура Рахмана  Книга с реализациями алгоритмов специально на PHP.

---

Заключение

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