Selection Sort (Сортировка выбором)

Краткое описание

Простой алгоритм сортировки, который разделяет массив на отсортированную и неотсортированную части. На каждом шаге находит минимальный элемент в неотсортированной части и помещает его в конец отсортированной части. Отличается минимальным количеством операций записи (не более n swap).

Когда использовать

• Маленькие массивы — где квадратичная сложность не критична (обычно до 50 элементов)
• Ограниченная память — алгоритм использует O(1) дополнительной памяти (in-place сортировка)
• Минимизация операций записи — когда запись в память дорогая (например, работа с диском или ROM), так как selection sort делает минимальное количество swap-операций (не более n)
• Образовательные цели — для понимания базовых принципов сортировки
• Простота реализации — когда важна понятность кода и не требуется высокая производительность

Когда не стоит использовать:

• Большие массивы — существуют намного более эффективные алгоритмы (Quick Sort, Merge Sort)
• Нужна адаптивность — алгоритм всегда O(n²), даже на отсортированных данных
• Требуется стабильность — Selection Sort не стабильный алгоритм

---

С объяснением логики работы

/**
 * Сортировка выбором (Selection Sort)
 * Принцип: разделяем массив на две части - отсортированную (слева) и неотсортированную (справа).
 * На каждом шаге находим минимальный элемент в неотсортированной части и перемещаем его в конец отсортированной части.
 */
function selectionSort(arr) {
    // Внешний цикл проходит по всем элементам массива, кроме последнего
    // Последний элемент не нужно проверять, так как он автоматически окажется на своем месте
    for (let i = 0; i < arr.length - 1; i++) {
        
        // Предполагаем, что текущий элемент (arr[i]) — это минимальный в неотсортированной части
        // minIndex будет хранить индекс самого маленького элемента
        let minIndex = i;
        
        // Внутренний цикл ищет минимальный элемент в оставшейся неотсортированной части
        // Начинаем с i+1, так как элементы до i уже отсортированы
        for (let j = i + 1; j < arr.length; j++) {
            
            // Если нашли элемент меньше текущего минимума
            if (arr[j] < arr[minIndex]) {
                // Обновляем индекс минимального элемента
                minIndex = j;
            }
        }
        
        // После завершения внутреннего цикла minIndex содержит индекс самого маленького элемента
        
        // Проверяем, нужно ли делать обмен
        // Если минимальный элемент не находится уже на позиции i, меняем их местами
        if (minIndex !== i) {
            // Обмен элементов используя деструктуризацию массива (ES6 синтаксис)
            // Это эквивалентно временной переменной: temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
        
        // Теперь arr[i] содержит правильный элемент для этой позиции
        // Граница между отсортированной и неотсортированной частью сдвинулась на одну позицию вправо
    }
    
    // Возвращаем отсортированный массив
    // Примечание: массив сортируется "на месте" (in-place), но возврат удобен для цепочки вызовов
    return arr;
}
 
// Пример использования
const numbers = [64, 25, 12, 22, 11];
console.log("Исходный массив:", numbers);
selectionSort(numbers);
console.log("Отсортированный массив:", numbers);
 

---

С анализом сложностей

/**
 * Сортировка выбором (Selection Sort)
 * 
 * ВРЕМЕННАЯ СЛОЖНОСТЬ:
 * - Лучший случай:   O(n²) — даже если массив уже отсортирован, алгоритм всё равно проверяет все элементы
 * - Средний случай:  O(n²) — стандартный случай с произвольным порядком элементов
 * - Худший случай:   O(n²) — когда массив отсортирован в обратном порядке
 * 
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
 * - O(1) — требуется только константное количество дополнительной памяти для переменных (i, j, minIndex, temp)
 * - Сортировка происходит "на месте" (in-place), без создания дополнительных массивов
 * 
 * КОЛИЧЕСТВО ОПЕРАЦИЙ:
 * - Сравнения: всегда (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2
 * - Обмены (swaps): в худшем случае O(n), в лучшем O(0)
 */
function selectionSort(arr) {
    // Внешний цикл выполняется (n-1) раз
    // Сложность внешнего цикла: O(n)
    for (let i = 0; i < arr.length - 1; i++) {
        
        // Инициализация minIndex — O(1) операция
        let minIndex = i;
        
        // Внутренний цикл выполняется (n-i-1) раз для каждой итерации внешнего цикла
        // Итерация 1: (n-1) сравнений
        // Итерация 2: (n-2) сравнений
        // ...
        // Итерация n-1: 1 сравнение
        // Общее количество: (n-1) + (n-2) + ... + 1 = n(n-1)/2
        // Сложность: O(n²)
        for (let j = i + 1; j < arr.length; j++) {
            
            // Сравнение — O(1) операция
            // Выполняется n(n-1)/2 раз за всю работу алгоритма
            if (arr[j] < arr[minIndex]) {
                // Присваивание — O(1) операция
                minIndex = j;
            }
        }
        
        // Проверка и обмен — O(1) операция
        // Обмен выполняется максимум (n-1) раз за всю работу (один раз на итерацию внешнего цикла)
        // Это делает selection sort эффективным, когда операция записи дорогая
        if (minIndex !== i) {
            // Swap операция — O(1) по времени, использует O(1) дополнительной памяти
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    
    // ИТОГОВАЯ СЛОЖНОСТЬ:
    // Время:  O(n) * O(n) = O(n²) — два вложенных цикла
    // Память: O(1) — только переменные i, j, minIndex
    
    return arr;
}
 
// Примеры для демонстрации одинаковой сложности во всех случаях:
 
// Худший случай: обратно отсортированный массив
const worst = [5, 4, 3, 2, 1];
 
// Лучший случай: уже отсортированный массив
// Важно: даже здесь будет O(n²), так как алгоритм всё равно проверяет все элементы
const best = [1, 2, 3, 4, 5];
 
// Средний случай: произвольный порядок
const average = [3, 1, 4, 5, 2];