⚡ JavaScript

Алгоритмы сортировки в JavaScript (Node.js): подробное руководство

Урок 29 / 35 • Полная теория для чтения

Что это такое и зачем? (аналогия из реальной жизни)

Представь, что у тебя есть огромная коробка с конструктором Lego, в которой перемешаны все детали: красные кирпичики, синие пластины, зелёные колёсики. Ты хочешь построить космический корабль, но сначала тебе нужно найти все красные детали одного размера. Что ты сделаешь? Высыплешь всё на пол и начнёшь перебирать? Это займёт вечность!

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

Сортировка — это процесс упорядочивания набора данных по определённому правилу. Чаще всего это числовой порядок (от меньшего к большему) или алфавитный порядок. Зачем это нужно в реальном программировании?

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

💡 Важно: В реальных проектах ты часто будешь использовать встроенные методы сортировки (например, .sort() в JavaScript). Но понимание того, как работают алгоритмы внутри, отличает настоящего программиста от того, кто просто копирует код. Это развивает алгоритмическое мышление.

Теория: как это работает изнутри

Давай заглянем под капот. Алгоритмы сортировки отличаются друг от друга стратегией. Представь, что ты — учитель физкультуры, и тебе нужно построить класс по росту. Вот как бы действовали разные алгоритмы:

Пузырьковая сортировка (Bubble Sort)

Ты проходишь вдоль шеренги и сравниваешь двух соседних учеников. Если левый выше правого — меняешь их местами. Проходишь так много раз, пока все не встанут по порядку. Самый высокий «всплывает» в конец, как пузырёк в газировке. Очень медленно, но очень просто для понимания.

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

Ты ищешь самого низкого ученика во всей шеренге и ставишь его в начало. Потом ищешь второго по низкости и ставишь его вторым. И так далее. Ты делаешь ровно столько проходов, сколько учеников.

Сортировка вставками (Insertion Sort)

Ты начинаешь со второго ученика. Если он ниже первого — вставляешь его перед ним. Потом берёшь третьего и вставляешь его в правильное место среди первых двух. Постепенно левая часть шеренги становится отсортированной, а правая — неотсортированной. Так обычно сортируют карты в руке во время игры.

Быстрая сортировка (Quick Sort)

Ты выбираешь одного ученика — «опорного». Всех, кто ниже его, ставишь слева, всех, кто выше — справа. Потом повторяешь то же самое для левой и правой групп. Это стратегия «разделяй и властвуй». Очень быстрый метод.

Сортировка слиянием (Merge Sort)

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

Сложность алгоритмов (Big O Notation)

Чтобы понять, какой алгоритм лучше, программисты используют «О-большое» (Big O). Это способ измерить, как быстро растёт время работы алгоритма при увеличении количества данных.

Алгоритм	Лучший случай	Средний случай	Худший случай	Память
Пузырьковая	O(n)	O(n²)	O(n²)	O(1)
Выбором	O(n²)	O(n²)	O(n²)	O(1)
Вставками	O(n)	O(n²)	O(n²)	O(1)
Быстрая	O(n log n)	O(n log n)	O(n²)	O(log n)
Слиянием	O(n log n)	O(n log n)	O(n log n)	O(n)

⚡ Запомни: O(n²) — это «квадратичная сложность». Если элементов 10, нужно 100 операций. Если 1000 — уже 1 000 000. O(n log n) — «линейно-логарифмическая». Для 1000 элементов нужно всего около 10 000 операций. Разница огромна!

Синтаксис в JavaScript (Node.js): все формы и варианты

В JavaScript есть встроенный метод .sort(), но он работает не совсем так, как думают новички. Давай разберём его досконально.

Базовый синтаксис `.sort()`

// Создаём массив чисел
let numbers = [3, 1, 4, 1, 5, 9, 2, 6];

// Просто вызываем sort() — и получаем... сюрприз!
numbers.sort();
console.log(numbers); // [1, 1, 2, 3, 4, 5, 6, 9] — вроде работает

// А теперь попробуем с другими числами
let trickyNumbers = [10, 5, 80, 2, 100];
trickyNumbers.sort();
console.log(trickyNumbers); // [10, 100, 2, 5, 80] — что за ерунда?!

Почему так произошло? Дело в том, что .sort() по умолчанию преобразует все элементы в строки и сортирует их как строки! Строка "10" идёт раньше строки "2", потому что первый символ '1' меньше '2'.

Правильный синтаксис с функцией сравнения

// Чтобы сортировать числа правильно, передаём функцию сравнения
let numbers = [10, 5, 80, 2, 100];

// Сортировка по возрастанию
numbers.sort((a, b) => a - b);
console.log(numbers); // [2, 5, 10, 80, 100]

// Сортировка по убыванию
numbers.sort((a, b) => b - a);
console.log(numbers); // [100, 80, 10, 5, 2]

Функция сравнения работает так:

Если результат отрицательный — a ставится перед b
Если результат положительный — b ставится перед a
Если результат ноль — порядок не меняется

Сортировка объектов

// У нас есть массив студентов
let students = [
    { name: "Анна", grade: 85 },
    { name: "Борис", grade: 92 },
    { name: "Вика", grade: 78 },
    { name: "Глеб", grade: 92 }
];

// Сортируем по оценкам (по возрастанию)
students.sort((a, b) => a.grade - b.grade);
console.log(students);
// [
//   { name: 'Вика', grade: 78 },
//   { name: 'Анна', grade: 85 },
//   { name: 'Борис', grade: 92 },
//   { name: 'Глеб', grade: 92 }
// ]

// Сортируем по имени (строки!)
students.sort((a, b) => {
    if (a.name < b.name) return -1;
    if (a.name > b.name) return 1;
    return 0;
});
console.log(students);
// [
//   { name: 'Анна', grade: 85 },
//   { name: 'Борис', grade: 92 },
//   { name: 'Вика', grade: 78 },
//   { name: 'Глеб', grade: 92 }
// ]

Стабильность сортировки

Современный JavaScript (ES2019+) использует стабильную сортировку. Это значит, что если два элемента равны, их относительный порядок сохраняется. В примере выше Борис и Глеб имеют одинаковые оценки (92), но Борис остаётся перед Глебом, как и в исходном массиве.

Примеры кода — от простого к сложному

Пример 1: Пузырьковая сортировка (Bubble Sort)

/**
 * Пузырьковая сортировка
 * Проходим по массиву, сравнивая соседние элементы.
 * Если левый больше правого — меняем их местами.
 * Повторяем, пока массив не будет отсортирован.
 */

function bubbleSort(arr) {
    // Делаем копию массива, чтобы не изменять оригинал
    const result = [...arr];
    const n = result.length;
    
    // Внешний цикл: каждый проход "выталкивает" один элемент на своё место
    for (let i = 0; i < n - 1; i++) {
        // Флаг: если за проход не было обменов — массив уже отсортирован
        let swapped = false;
        
        // Внутренний цикл: сравниваем пары
        for (let j = 0; j < n - 1 - i; j++) {
            // Сравниваем соседние элементы
            if (result[j] > result[j + 1]) {
                // Меняем местами через временную переменную
                let temp = result[j];
                result[j] = result[j + 1];
                result[j + 1] = temp;
                swapped = true;
            }
        }
        
        // Если не было обменов — выходим досрочно
        if (!swapped) break;
    }
    
    return result;
}

// Тестируем
const testArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Исходный массив:", testArray);
console.log("Отсортированный:", bubbleSort(testArray));
// Исходный массив: [64, 34, 25, 12, 22, 11, 90]
// Отсортированный: [11, 12, 22, 25, 34, 64, 90]

Пример 2: Сортировка выбором (Selection Sort)

/**
 * Сортировка выбором
 * На каждом шаге находим минимальный элемент в неотсортированной части
 * и ставим его в начало этой части.
 */

function selectionSort(arr) {
    const result = [...arr];
    const n = result.length;
    
    for (let i = 0; i < n - 1; i++) {
        // Считаем, что текущий элемент — минимальный
        let minIndex = i;
        
        // Ищем реальный минимальный элемент в оставшейся части
        for (let j = i + 1; j < n; j++) {
            if (result[j] < result[minIndex]) {
                minIndex = j;
            }
        }
        
        // Если нашли элемент меньше текущего — меняем местами
        if (minIndex !== i) {
            [result[i], result[minIndex]] = [result[minIndex], result[i]];
            // Используем деструктуризацию для обмена — современный способ!
        }
    }
    
    return result;
}

console.log(selectionSort([29, 10, 14, 37, 13]));
// [10, 13, 14, 29, 37]

Пример 3: Сортировка вставками (Insertion Sort)

/**
 * Сортировка вставками
 * Берём элемент из неотсортированной части и вставляем его
 * в правильное место в отсортированной части.
 * Отлично работает для почти отсортированных массивов!
 */

function insertionSort(arr) {
    const result = [...arr];
    const n = result.length;
    
    // Начинаем со второго элемента (индекс 1)
    for (let i = 1; i < n; i++) {
        // Запоминаем текущий элемент
        let current = result[i];
        let j = i - 1;
        
        // Сдвигаем элементы вправо, пока не найдём место для current
        while (j >= 0 && result[j] > current) {
            result[j + 1] = result[j];
            j--;
        }
        
        // Вставляем current на освободившееся место
        result[j + 1] = current;
    }
    
    return result;
}

console.log(insertionSort([12, 11, 13, 5, 6]));
// [5, 6, 11, 12, 13]

Пример 4: Быстрая сортировка (Quick Sort)

/**
 * Быстрая сортировка (рекурсивная версия)
 * Выбираем опорный элемент, делим массив на меньшие и большие части,
 * рекурсивно сортируем каждую часть.
 */

function quickSort(arr) {
    // Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if (arr.length <= 1) {
        return arr;
    }
    
    // Выбираем опорный элемент (обычно берут последний или средний)
    const pivot = arr[arr.length - 1];
    
    // Создаём массивы для меньших и больших элементов
    const left = [];
    const right = [];
    
    // Проходим по всем элементам, кроме опорного
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);  // Меньшие — налево
        } else {
            right.push(arr[i]); // Большие или равные — направо
        }
    }
    
    // Рекурсивно сортируем левую и правую части, собираем результат
    return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]

Пример 5: Сортировка слиянием (Merge Sort)

/**
 * Сортировка слиянием
 * Делим массив пополам, рекурсивно сортируем половины,
 * затем сливаем их в один отсортированный массив.
 */

function mergeSort(arr) {
    // Базовый случай
    if (arr.length <= 1) {
        return arr;
    }
    
    // Находим середину и делим массив
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    
    // Рекурсивно сортируем обе половины
    return merge(mergeSort(left), mergeSort(right));
}

// Вспомогательная функция для слияния двух отсортированных массивов
function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    // Сравниваем элементы и добавляем меньший в результат
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    // Добавляем оставшиеся элементы (если один массив закончился раньше)
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Пример 6: Сортировка строк (с учётом регистра и локали)

/**
 * Сортировка строк — это отдельное искусство!
 * Нужно учитывать регистр букв и национальные особенности.
 */

const fruits = ["яблоко", "Банан", "апельсин", "Груша", "вишня"];

// Простая сортировка (проблема: заглавные буквы идут раньше строчных)
fruits.sort();
console.log("Простая сортировка:", fruits);
// ['Банан', 'Груша', 'апельсин', 'вишня', 'яблоко']
// Заглавные буквы имеют меньший код в Unicode!

// Правильная сортировка с localeCompare
fruits.sort((a, b) => a.localeCompare(b, 'ru'));
console.log("С учётом локали:", fruits);
// ['апельсин', 'Банан', 'вишня', 'Груша', 'яблоко']

// Сортировка по длине строки
fruits.sort((a, b) => a.length - b.length);
console.log("По длине:", fruits);
// ['Банан', 'Груша', 'вишня', 'яблоко', 'апельсин']

Пример 7: Сортировка массива объектов по нескольким полям

/**
 * Сортировка по нескольким критериям
 * Сначала по возрасту (по возрастанию), потом по имени (по алфавиту)
 */

const people = [
    { name: "Иван", age: 25 },
    { name: "Анна", age: 30 },
    { name: "Пётр", age: 25 },
    { name: "Мария", age: 30 },
    { name: "Иван", age: 20 }
];

// Сортируем: сначала по возрасту, потом по имени
people.sort((a, b) => {
    // Сначала сравниваем возраст
    if (a.age !== b.age) {
        return a.age - b.age;
    }
    // Если возраст одинаковый — сравниваем имена
    return a.name.localeCompare(b.name, 'ru');
});

console.log("Многоуровневая сортировка:");
people.forEach(person => {
    console.log(`${person.name}: ${person.age} лет`);
});
// Иван: 20 лет
// Анна: 25 лет  (Иван и Пётр 25 лет, но Анна по алфавиту раньше)
// Иван: 25 лет
// Пётр: 25 лет
// Мария: 30 лет
// Анна: 30 лет

Сравнение с Python: чем похоже и чем отличается

Если ты изучал Python, ты заметишь много общего, но есть и важные различия.

Характеристика	JavaScript (Node.js)	Python
Встроенная сортировка	`arr.sort()` — изменяет исходный массив	`sorted(arr)` — возвращает новый список `arr.sort()` — изменяет исходный
Сортировка по умолчанию	Как строки (лексикографически) — нужно передавать функцию сравнения	Как числа/строки (интуитивно понятно)
Функция сравнения	Возвращает число (отрицательное, ноль, положительное)	Возвращает ключ через `key` или использует `cmp` (устарело)
Сортировка по ключу	Нужно писать свою функцию сравнения	Есть параметр `key` — очень удобно: `sorted(arr, key=lambda x: x['age'])`
Стабильность	Стабильная (с ES2019)	Стабильная (с Python 3)
Сортировка строк с учётом локали	`localeCompare()`	`locale.strxfrm()` или библиотека `locale`

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

Типичные ошибки и подводные камни

Ошибка 1: Забыть про функцию сравнения для чисел

// ❌ Неправильно
let nums = [1, 2, 10, 20];
nums.sort();
console.log(nums); // [1, 10, 2, 20] — строковая сортировка!

// ✅ Правильно
nums.sort((a, b) => a - b);
console.log(nums); // [1, 2, 10, 20]

Ошибка 2: Мутация исходного массива

// ❌ sort() изменяет исходный массив!
let original = [3, 1, 4, 1, 5];
let sorted = original.sort();
console.log(original); // [1, 1, 3, 4, 5] — оригинал тоже изменился!

// ✅ Чтобы сохранить оригинал, делаем копию
let original2 = [3, 1, 4, 1, 5];
let sorted2 = [...original2].sort((a, b) => a - b);
console.log(original2); // [3, 1, 4, 1, 5] — оригинал не тронут
console.log(sorted2);   // [1, 1, 3, 4, 5]

Ошибка 3: Неправильное сравнение строк с заглавными буквами

// ❌ Проблема с регистром
let words = ["apple", "Banana", "cherry"];
words.sort();
console.log(words); // ['Banana', 'apple', 'cherry'] — 'B' (код 66) меньше 'a' (код 97)

// ✅ Решение: приводим к одному регистру или используем localeCompare
words.sort((a, b) => a.toLowerCase().localeCompare(b.toLowerCase()));
console.log(words); // ['apple', 'Banana', 'cherry']

Ошибка 4: Сортировка undefined или null

// ❌ Если в массиве есть undefined, sort() ведёт себя странно
let mixed = [3, undefined, 1, null, 2];
mixed.sort((a, b) => a - b);
console.log(mixed); // [null, 1, 2, 3, undefined] — null преобразуется в 0, undefined в NaN

// ✅ Лучше отфильтровать некорректные значения
let clean = mixed.filter(item => item !== null && item !== undefined);
clean.sort((a, b) => a - b);
console.log(clean); // [1, 2, 3]

Ошибка 5: Предположение, что sort() возвращает новый массив

// ❌ Многие думают, что sort() возвращает новый массив
let arr = [3, 1, 2];
let result = arr.sort();
console.log(result === arr); // true — это один и тот же массив!

// ✅ Для создания нового массива используем toSorted() (ES2023)
let arr2 = [3, 1, 2];
let result2 = arr2.toSorted((a, b) => a - b);
console.log(arr2);    // [3, 1, 2] — оригинал не изменён
console.log(result2); // [1, 2, 3] — новый массив

Лучшие практики и советы профессионалов

1. Всегда используй функцию сравнения

Даже если ты сортируешь строки и уверен, что регистр одинаковый — привыкай писать функцию сравнения. Это делает код явным и понятным.

2. Для сложных объектов используй библиотеки

В реальных проектах для сортировки больших объёмов данных часто используют библиотеки вроде Lodash:

// Установка: npm install lodash
const _ = require('lodash');

const users = [
    { user: 'fred', age: 48 },
    { user: 'barney', age: 36 },
    { user: 'fred', age: 40 }
];

// Сортировка по нескольким полям одной строкой!
const sorted = _.sortBy(users, ['user', 'age']);
console.log(sorted);
// [
//   { user: 'barney', age: 36 },
//   { user: 'fred', age: 40 },
//   { user: 'fred', age: 48 }
// ]

3. Для больших массивов используй TypedArray

Если ты работаешь с огромными массивами чисел (миллионы элементов), используй Float64Array или Int32Array — они сортируются быстрее обычных массивов.

4. Помни про стабильность

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

5. Тестируй производительность

Для массивов меньше 10 элементов разница между алгоритмами незаметна. Для массивов больше 1000 элементов — используй встроенный .sort(), он оптимизирован (обычно использует TimSort — гибрид сортировки вставками и слиянием).

6. Избегай рекурсии для очень больших массивов

Быстрая сортировка и сортировка слиянием используют рекурсию. Для массивов из 100 000+ элементов может возникнуть ошибка переполнения стека. В таких случаях лучше использовать итеративные версии или встроенный .sort().

Вопросы для самопроверки

Вопрос: Почему [10, 2, 30].sort() даёт результат [10, 2, 30]?

Ответ: Потому что .sort() без функции сравнения преобразует числа в строки и сортирует их лексикографически. Строка "10" идёт раньше "2", потому что первый символ '1' меньше '2'.
Вопрос: Какой алгоритм сортировки самый быстрый в среднем случае?

Ответ: Быстрая сортировка (Quick Sort) имеет среднюю сложность O(n log n). Однако встроенный .sort() в JavaScript обычно использует TimSort, который также имеет сложность O(n log n) и часто работает быстрее на реальных данных.
Вопрос: Что такое стабильная сортировка и почему это важно?

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

Ответ: Нужно написать функцию сравнения: сначала сравниваем возраст (b.age - a.age для убывания), если они равны — сравниваем имена через localeCompare.
Вопрос: В чём разница между arr.sort() и arr.toSorted()?

Ответ: sort() изменяет исходный массив и возвращает его же. toSorted() (ES2023) возвращает новый отсортированный массив, не изменяя исходный.
Вопрос: Какой алгоритм сортировки лучше всего подходит для почти отсортированного массива?

Ответ: Сортировка вставками (Insertion Sort). В лучшем случае (массив уже отсортирован) она работает за O(n).
Вопрос: Почему пузырьковая сортировка считается плохой для больших массивов?

Ответ: Её сложность O(n²) — для 10 000 элементов нужно около 100 миллионов операций. Это очень медленно по сравнению с O(n log n) алгоритмами.
Вопрос: Как отсортировать массив строк без учёта регистра?

Ответ: Использовать localeCompare с опцией sensitivity: 'base' или привести все строки к одному регистру перед сравнением.
Вопрос: Что произойдёт, если передать в функцию сравнения (a, b)

← Предыдущая Регулярные выражения в JavaScript (Node.js): подро Вперёд → Алгоритмы поиска в JavaScript (Node.js): подробное