Сортировка выбором — это алгоритм сортировки массива или списка путем постепенных перестановок наименьших элементов в начало списка или наибольших в конец.

Алгоритм

1. Найти наименьшее значение в списке.
2. Записать его в начало списка, а первый элемент — на место, где раньше стоял наименьший.
3. Снова найти наименьший элемент в списке. При этом в поиске не участвует первый элемент.
4. Второй минимум поместить на второе место списка. Второй элемент при этом перемещается на освободившееся место.
5. Продолжать выполнять поиск и обмен, пока не будет достигнут конец списка.

Важно!

Это очень плохой алгоритм для больших данных. Но очень хороший для обучения. Сложность алгоритма O(n²).

2 варианта решения

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

Потом то же самое происходит со следующим по количеству воспроизведений исполнителем.

Это более простой вариант.

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

Реализация

Делим решение задачи на 2 отдельных задачи:

1. Функция, которая будет находить максимальное / минимальное значение в массиве.
2. На основе этой функции можно написать функцию сортировки выбором.

<?php

$numbers = [
    58, 91, 42, 89, 53,
    82, 38, 74, 51, 76,
    45, 72, 54, 71, 56,
    69, 63, 60, 99, 65,
];

function sortItems($arr) {

    $n = count($arr);

    for ($i = 0; $i < $n; $i++) {

        echo "\n=============================\n";
        echo "Итерация i = $i\n";
        echo "Массив ДО:  " . implode(', ', $arr) . "\n";

        // найти индекс самого большого элемента в диапазоне i..конец
        $biggestIndex = getBiggest($arr, $i);

        echo "Найден максимум: {$arr[$biggestIndex]} (index $biggestIndex)\n";
        echo "Меняем местами: arr[$i] = {$arr[$i]} и arr[$biggestIndex] = {$arr[$biggestIndex]}\n";

        // swap
        $tmp = $arr[$i];
        $arr[$i] = $arr[$biggestIndex];
        $arr[$biggestIndex] = $tmp;

        echo "Массив ПОСЛЕ: " . implode(', ', $arr) . "\n";
    }

    return $arr;
}

function getBiggest($arr, $start) {

    $biggest = $arr[$start];
    $biggestIndex = $start;

    for ($i = $start + 1; $i < count($arr); $i++) {
        if ($arr[$i] > $biggest) {
            $biggest = $arr[$i];
            $biggestIndex = $i;
        }
    }

    return $biggestIndex;
}

$result = sortItems($numbers);

echo "\n=============================\n";
echo "ФИНАЛЬНЫЙ РЕЗУЛЬТАТ:\n";
echo implode(', ', $result);

Вот как массив меняется на каждой итерации:

=============================
Итерация i = 0
Массив ДО:  58, 91, 42, 89, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 99, 65
Найден максимум: 99 (index 18)
Меняем местами: arr[0] = 58 и arr[18] = 99
Массив ПОСЛЕ: 99, 91, 42, 89, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 1
Массив ДО:  99, 91, 42, 89, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 91 (index 1)
Меняем местами: arr[1] = 91 и arr[1] = 91
Массив ПОСЛЕ: 99, 91, 42, 89, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 2
Массив ДО:  99, 91, 42, 89, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 89 (index 3)
Меняем местами: arr[2] = 42 и arr[3] = 89
Массив ПОСЛЕ: 99, 91, 89, 42, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 3
Массив ДО:  99, 91, 89, 42, 53, 82, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 82 (index 5)
Меняем местами: arr[3] = 42 и arr[5] = 82
Массив ПОСЛЕ: 99, 91, 89, 82, 53, 42, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 4
Массив ДО:  99, 91, 89, 82, 53, 42, 38, 74, 51, 76, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 76 (index 9)
Меняем местами: arr[4] = 53 и arr[9] = 76
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 42, 38, 74, 51, 53, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 5
Массив ДО:  99, 91, 89, 82, 76, 42, 38, 74, 51, 53, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 74 (index 7)
Меняем местами: arr[5] = 42 и arr[7] = 74
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 38, 42, 51, 53, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 6
Массив ДО:  99, 91, 89, 82, 76, 74, 38, 42, 51, 53, 45, 72, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 72 (index 11)
Меняем местами: arr[6] = 38 и arr[11] = 72
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 42, 51, 53, 45, 38, 54, 71, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 7
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 42, 51, 53, 45, 38, 54, 71, 56, 69, 63, 60, 58, 65
Найден максимум: 71 (index 13)
Меняем местами: arr[7] = 42 и arr[13] = 71
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 51, 53, 45, 38, 54, 42, 56, 69, 63, 60, 58, 65

=============================
Итерация i = 8
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 51, 53, 45, 38, 54, 42, 56, 69, 63, 60, 58, 65
Найден максимум: 69 (index 15)
Меняем местами: arr[8] = 51 и arr[15] = 69
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 53, 45, 38, 54, 42, 56, 51, 63, 60, 58, 65

=============================
Итерация i = 9
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 53, 45, 38, 54, 42, 56, 51, 63, 60, 58, 65
Найден максимум: 65 (index 19)
Меняем местами: arr[9] = 53 и arr[19] = 65
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 45, 38, 54, 42, 56, 51, 63, 60, 58, 53

=============================
Итерация i = 10
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 45, 38, 54, 42, 56, 51, 63, 60, 58, 53
Найден максимум: 63 (index 16)
Меняем местами: arr[10] = 45 и arr[16] = 63
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 38, 54, 42, 56, 51, 45, 60, 58, 53

=============================
Итерация i = 11
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 38, 54, 42, 56, 51, 45, 60, 58, 53
Найден максимум: 60 (index 17)
Меняем местами: arr[11] = 38 и arr[17] = 60
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 54, 42, 56, 51, 45, 38, 58, 53

=============================
Итерация i = 12
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 54, 42, 56, 51, 45, 38, 58, 53
Найден максимум: 58 (index 18)
Меняем местами: arr[12] = 54 и arr[18] = 58
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 42, 56, 51, 45, 38, 54, 53

=============================
Итерация i = 13
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 42, 56, 51, 45, 38, 54, 53
Найден максимум: 56 (index 14)
Меняем местами: arr[13] = 42 и arr[14] = 56
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 42, 51, 45, 38, 54, 53

=============================
Итерация i = 14
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 42, 51, 45, 38, 54, 53
Найден максимум: 54 (index 18)
Меняем местами: arr[14] = 42 и arr[18] = 54
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 51, 45, 38, 42, 53

=============================
Итерация i = 15
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 51, 45, 38, 42, 53
Найден максимум: 53 (index 19)
Меняем местами: arr[15] = 51 и arr[19] = 53
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 45, 38, 42, 51

=============================
Итерация i = 16
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 45, 38, 42, 51
Найден максимум: 51 (index 19)
Меняем местами: arr[16] = 45 и arr[19] = 51
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 38, 42, 45

=============================
Итерация i = 17
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 38, 42, 45
Найден максимум: 45 (index 19)
Меняем местами: arr[17] = 38 и arr[19] = 45
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38

=============================
Итерация i = 18
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38
Найден максимум: 42 (index 18)
Меняем местами: arr[18] = 42 и arr[18] = 42
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38

=============================
Итерация i = 19
Массив ДО:  99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38
Найден максимум: 38 (index 19)
Меняем местами: arr[19] = 38 и arr[19] = 38
Массив ПОСЛЕ: 99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38

=============================
ФИНАЛЬНЫЙ РЕЗУЛЬТАТ:
99, 91, 89, 82, 76, 74, 72, 71, 69, 65, 63, 60, 58, 56, 54, 53, 51, 45, 42, 38

Мы начинаем сравнение с индекса $i, потому что:

• элементы слева от $i уже отсортированы
• они стоят на своих окончательных местах
• трогать их больше нельзя вообще

Алгоритм каждый раз делит массив мысленно на две части:

[ отсортировано | не отсортировано ]
  0 ... i-1        i ... конец

На итерации i мы отвечаем только на один вопрос:

какое самое большое число в диапазоне i .. конец?

И когда мы его нашли, мы:

• кладем его в позицию i
• тем самым расширяем отсортированную часть на один элемент

Вот тут мы передаем с какого элемента надо начинать искать самое большое число в хвосте – $start:

function getBiggest($arr, $start) {

    $biggest = $arr[$start];
    $biggestIndex = $start;

    for ($i = $start + 1; $i < count($arr); $i++) {
    ......

То есть на итерации 14, мы уже будем брать и сравнивать элементы с позиции 14 и до конца массива.

Альтернативное решение

<?php

function selectionSort(array $arr): array
{
    $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;
            }
        }
        
        // Меняем местами, если нашли меньший элемент
        if ($minIndex !== $i) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp;
        }
    }
    
    return $arr;
}

// Пример использования
$numbers = [64, 25, 12, 22, 11, 90, 45];

echo "До сортировки: " . implode(', ', $numbers) . "\n";
echo "После сортировки: " . implode(', ', selectionSort($numbers)) . "\n";
```

**Вывод:**
```
До сортировки: 64, 25, 12, 22, 11, 90, 45
После сортировки: 11, 12, 22, 25, 45, 64, 90

Пошаговый процесс

1. Начинаем с первой позиции массива
2. Просматриваем все элементы от текущей позиции до конца
3. Находим среди них минимальный
4. Меняем его местами с элементом на текущей позиции
5. Сдвигаемся на одну позицию вправо
6. Повторяем шаги 2–5, пока не дойдём до конца массива