Сортировка — одна из фундаментальных операций в программировании, встречающаяся в различных приложениях, таких как базы данных, поисковые системы и системы обработки данных. Сортировка позволяет упорядочивать элементы массива или списка на основе определенных критериев (например, по возрастанию или убыванию). Существуют различные алгоритмы сортировки, каждый из которых имеет свои особенности, преимущества и недостатки. В этом уроке мы рассмотрим некоторые базовые алгоритмы сортировки, их реализацию в PHP и проанализируем их сложность.
Алгоритмы сортировки
Сортировка пузырьком
Описание: Сортировка пузырьком — один из простейших алгоритмов сортировки. Он многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока массив не будет отсортирован.
Алгоритм:
- Пройтись по массиву от первого до последнего элемента.
- Сравните каждый элемент с соседним элементом.
- Если текущий элемент больше следующего, поменяйте их местами.
- Повторяйте процесс, пока массив не будет отсортирован.
Реализация на 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) — если массив уже отсортирован, пузырьковая сортировка может выполнить минимальное количество операций.
Сортировка по выбору
Описание: Сортировка выбором находит наименьший элемент в массиве и меняет его местами с первым элементом. Затем алгоритм повторяет этот процесс для оставшейся неотсортированной части массива.
Алгоритм:
- Пройдитесь по массиву и найдите минимальный элемент.
- Поменяйте его местами с первым элементом.
- Повторите эти действия для оставшейся части массива.
Реализация на 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²), так как количество операций не зависит от того, отсортирован ли массив.
Сортировка вставкой
Описание: Сортировка вставками работает как сортировка карт в вашей руке: элементы массива вставляются в правильную позицию среди уже отсортированных элементов.
Алгоритм:
- Начните со второго элемента и рассмотрите его как часть отсортированной последовательности.
- Вставить текущий элемент в правильную позицию в отсортированной части массива.
- Повторите для всех элементов.
Реализация на 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) — если массив уже отсортирован.
Рекомендуемая литература:
- «Изучаем алгоритмы» Адитьи Бхаргавы. Отличная книга для начинающих, в которой объясняются основные алгоритмы с наглядными иллюстрациями и примерами (написана на Python, но может быть легко адаптирована для PHP).
- «Введение в алгоритмы» Томаса Кормена и др. Классическая книга по алгоритмам, охватывающая более сложные и продвинутые алгоритмы, такие как быстрая сортировка и сортировка слиянием.
- «Алгоритмы PHP» Мизанура Рахмана Книга с реализациями алгоритмов специально на PHP.
Заключение
Сегодня мы рассмотрели несколько базовых алгоритмов сортировки, таких как пузырьковая сортировка, сортировка выбором и сортировка вставкой. Эти алгоритмы просты в реализации, но различаются по эффективности в зависимости от ситуации. На следующем уроке мы рассмотрим более сложные алгоритмы, такие как быстрая сортировка и сортировка слиянием, которые используются для сортировки больших наборов данных.
