📘 TypeScript

Sorting Algorithms in TypeScript: A Comprehensive Guide

Lesson 29 / 35 • Full reading theory

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

Представь, что ты — библиотекарь, и тебе привезли огромную стопку книг, которые нужно расставить на полки в алфавитном порядке. Если книг всего пять, ты можешь сделать это быстро и на глаз. Но что, если книг тысяча? Или десять тысяч? Ты будешь тратить часы, постоянно перекладывая книги с места на место, путаться и уставать.

Вот тут-то и приходят на помощь алгоритмы сортировки. Это не магия, а чёткие, пошаговые инструкции (как рецепт пирога), которые говорят компьютеру: «Возьми этот список чисел (или книг, или имён) и разложи их по порядку — от самого маленького к самому большому (или наоборот)».

В реальной жизни мы постоянно сортируем: раскладываем одежду по цветам, ищем самую дешёвую вещь в магазине, выстраиваем одноклассников по росту на физкультуре. В программировании сортировка — это база. Без неё не работают поисковики (Google не смог бы показать тебе самые важные сайты), онлайн-магазины (не смогли бы отсортировать товары по цене) и даже твои плейлисты в Spotify.

💡 Запомни: Сортировка — это не просто «сделать красиво». Это способ сделать данные удобными для поиска и анализа. Отсортированный список — это как аккуратно подписанные папки в шкафу, а не куча бумаг на полу.

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

Давай заглянем «под капот». Компьютер не видит весь список сразу, как человек. Он может только сравнивать два элемента и менять их местами. Алгоритм сортировки — это последовательность таких сравнений и перестановок.

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

Основные понятия

Сравнение (Comparison): Проверка, какой из двух элементов больше, меньше или равен.
Обмен (Swap): Перестановка двух элементов местами.
Проход (Pass/Iteration): Один полный цикл сравнения всех или части элементов.
Стабильность (Stability): Если два элемента равны, сохранят ли они свой первоначальный порядок? Стабильная сортировка — да.
Сложность (Complexity): Как быстро работает алгоритм, если данных становится очень много. Измеряется в O(...) (О-большое).

Три главных «кита» сортировки

Мы разберём три алгоритма, которые идеально подходят для начала. Они разные по скорости и логике.

Алгоритм	Как работает (аналогия)	Скорость (O-большое)	Сложность для новичка
Пузырьковая (Bubble Sort)	Как пузырьки воздуха в газировке: большие числа «всплывают» в конец списка, проходя через соседей.	O(n²) — медленная	⭐ (Очень простая)
Вставками (Insertion Sort)	Как ты собираешь колоду карт: берёшь новую карту и вставляешь её в нужное место среди уже отсортированных.	O(n²) — медленная, но быстрее пузырьковой	⭐ (Простая)
Быстрая (Quick Sort)	Как «разделяй и властвуй»: выбираешь один элемент (опорный), а все меньшие кидаешь налево, большие — направо. Потом повторяешь то же самое для каждой части.	O(n log n) — очень быстрая	⭐⭐⭐ (Средняя)

⚠️ Важно: O(n²) — это плохо. Если у тебя 1000 элементов, такой алгоритм сделает около 1 000 000 операций. O(n log n) — хорошо. Для 1000 элементов это всего около 10 000 операций. Разница колоссальная!

Синтаксис в TypeScript: все формы и варианты

TypeScript — это «умный» JavaScript. Он умеет всё то же самое, но ещё и следит за типами данных (число это, строка или объект). Это очень помогает не допускать глупых ошибок.

В TypeScript (и JavaScript) уже есть встроенный метод для сортировки массивов: Array.prototype.sort(). Но его нужно использовать с умом!

Встроенный метод `.sort()`

По умолчанию .sort() сортирует элементы как строки! Это ловушка для новичков.

// Пример: как НЕ надо
const numbers: number[] = [10, 5, 80, 2];
numbers.sort();
console.log(numbers); // Выведет: [10, 2, 5, 80] — это неправильно!
// Потому что '10' как строка меньше, чем '2'

Чтобы сортировать числа правильно, нужно передать в .sort() функцию сравнения (компаратор).

// Правильная сортировка чисел по возрастанию
const numbers: number[] = [10, 5, 80, 2];
numbers.sort((a, b) => a - b);
console.log(numbers); // Выведет: [2, 5, 10, 80]

// По убыванию
numbers.sort((a, b) => b - a);
console.log(numbers); // Выведет: [80, 10, 5, 2]

Как это работает? Функция сравнения должна вернуть:

Отрицательное число, если a должно быть перед b.
Положительное число, если b должно быть перед a.
Ноль, если они равны.

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

Чаще всего мы сортируем не просто числа, а целые объекты (например, список пользователей).

interface User {
    name: string;
    age: number;
}

const users: User[] = [
    { name: "Аня", age: 25 },
    { name: "Боря", age: 18 },
    { name: "Витя", age: 30 }
];

// Сортируем по возрасту (от младшего к старшему)
users.sort((a, b) => a.age - b.age);
console.log(users);
// Выведет: [ { name: 'Боря', age: 18 }, { name: 'Аня', age: 25 }, { name: 'Витя', age: 30 } ]

// Сортируем по имени (в алфавитном порядке)
users.sort((a, b) => a.name.localeCompare(b.name));
console.log(users);
// Выведет: [ { name: 'Аня', age: 25 }, { name: 'Боря', age: 18 }, { name: 'Витя', age: 30 } ]

💡 Совет: Для строк всегда используй .localeCompare(). Она правильно обрабатывает буквы «ё», заглавные и строчные.

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

Теперь самое интересное. Мы напишем свои собственные алгоритмы сортировки на TypeScript. Каждый пример — рабочий и с подробными комментариями.

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

/**
 * Пузырьковая сортировка.
 * Проходим по массиву много раз.
 * На каждом проходе сравниваем соседние элементы.
 * Если левый больше правого — меняем их местами.
 * Самые большие числа «всплывают» в конец.
 */
function bubbleSort(arr: number[]): number[] {
    // Создаём копию массива, чтобы не менять оригинал
    const sorted = [...arr];
    const n = sorted.length;

    // Внешний цикл: сколько раз мы проходим по массиву
    for (let i = 0; i < n - 1; i++) {
        // Внутренний цикл: проходим по неотсортированной части
        // После каждого прохода самый большой элемент уже на своём месте в конце
        for (let j = 0; j < n - 1 - i; j++) {
            // Сравниваем два соседних элемента
            if (sorted[j] > sorted[j + 1]) {
                // Меняем их местами (swap)
                const temp = sorted[j];
                sorted[j] = sorted[j + 1];
                sorted[j + 1] = temp;
            }
        }
    }
    return sorted;
}

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

Пример 2: Пузырьковая сортировка с оптимизацией

Если массив уже отсортирован, зачем делать лишние проходы? Добавим флаг.

/**
 * Улучшенная пузырьковая сортировка.
 * Если за весь проход не было ни одной перестановки — массив уже отсортирован.
 */
function bubbleSortOptimized(arr: number[]): number[] {
    const sorted = [...arr];
    const n = sorted.length;
    let swapped: boolean; // Флаг: были ли перестановки

    for (let i = 0; i < n - 1; i++) {
        swapped = false; // Сбрасываем флаг в начале каждого прохода

        for (let j = 0; j < n - 1 - i; j++) {
            if (sorted[j] > sorted[j + 1]) {
                // Swap
                [sorted[j], sorted[j + 1]] = [sorted[j + 1], sorted[j]]; // Современный синтаксис!
                swapped = true; // Перестановка была
            }
        }

        // Если перестановок не было — выходим из цикла досрочно
        if (!swapped) {
            break;
        }
    }
    return sorted;
}

const almostSorted = [1, 2, 3, 5, 4, 6];
console.log("Оптимизированная сортировка:", bubbleSortOptimized(almostSorted));
// Вывод: [1, 2, 3, 4, 5, 6]

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

/**
 * Сортировка вставками.
 * Представь, что левая часть массива уже отсортирована.
 * Берём очередной элемент и «вставляем» его в нужное место среди отсортированных.
 */
function insertionSort(arr: number[]): number[] {
    const sorted = [...arr];
    const n = sorted.length;

    // Начинаем со второго элемента (индекс 1), т.к. первый элемент сам по себе уже отсортирован
    for (let i = 1; i < n; i++) {
        // Запоминаем текущий элемент, который будем вставлять
        const key = sorted[i];
        // Индекс предыдущего элемента
        let j = i - 1;

        // Сдвигаем все элементы, которые больше key, на одну позицию вправо
        while (j >= 0 && sorted[j] > key) {
            sorted[j + 1] = sorted[j];
            j = j - 1;
        }
        // Вставляем key на освободившееся место
        sorted[j + 1] = key;
    }
    return sorted;
}

const cards = [5, 2, 4, 6, 1, 3];
console.log("Сортировка вставками:", insertionSort(cards));
// Вывод: [1, 2, 3, 4, 5, 6]

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

/**
 * Быстрая сортировка (рекурсивная версия).
 * 1. Выбираем опорный элемент (pivot).
 * 2. Делим массив на две части: элементы меньше pivot и элементы больше pivot.
 * 3. Рекурсивно сортируем каждую часть.
 */
function quickSort(arr: number[]): number[] {
    // Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if (arr.length <= 1) {
        return arr;
    }

    // Выбираем опорный элемент (здесь — последний элемент)
    const pivot = arr[arr.length - 1];
    const left: number[] = [];   // Элементы меньше pivot
    const right: number[] = [];  // Элементы больше pivot

    // Проходим по всем элементам, кроме последнего (pivot)
    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)];
}

const unsorted = [3, 6, 8, 10, 1, 2, 1];
console.log("Быстрая сортировка:", quickSort(unsorted));
// Вывод: [1, 1, 2, 3, 6, 8, 10]

Пример 5: Быстрая сортировка «на месте» (In-Place Quick Sort)

Предыдущий пример создаёт новые массивы (left, right), что тратит память. Профессиональная версия сортирует прямо в исходном массиве.

/**
 * Быстрая сортировка "на месте" (In-Place).
 * Не создаёт новые массивы, а переставляет элементы внутри исходного.
 */
function quickSortInPlace(arr: number[], low: number = 0, high: number = arr.length - 1): void {
    if (low < high) {
        // Находим индекс опорного элемента после разделения
        const pivotIndex = partition(arr, low, high);
        // Рекурсивно сортируем левую и правую части
        quickSortInPlace(arr, low, pivotIndex - 1);
        quickSortInPlace(arr, pivotIndex + 1, high);
    }
}

// Вспомогательная функция для разделения массива
function partition(arr: number[], low: number, high: number): number {
    // Выбираем опорный элемент (здесь — последний)
    const pivot = arr[high];
    // Индекс для «границы» меньших элементов
    let i = low - 1;

    for (let j = low; j < high; j++) {
        // Если текущий элемент меньше или равен pivot
        if (arr[j] <= pivot) {
            i++;
            // Меняем местами arr[i] и arr[j]
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    // Ставим pivot на своё место (между меньшими и большими)
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1; // Возвращаем индекс pivot
}

const arrToSort = [10, 7, 8, 9, 1, 5];
quickSortInPlace(arrToSort);
console.log("In-Place Quick Sort:", arrToSort);
// Вывод: [1, 5, 7, 8, 9, 10]

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

Ещё один быстрый алгоритм. Он делит массив пополам до тех пор, пока не останутся массивы из одного элемента, а потом собирает их обратно, но уже отсортированными.

/**
 * Сортировка слиянием.
 * Делим массив пополам, рекурсивно сортируем половины, затем сливаем их.
 */
function mergeSort(arr: number[]): number[] {
    // Базовый случай
    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: number[], right: number[]): number[] {
    const result: number[] = [];
    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));
}

const data = [38, 27, 43, 3, 9, 82, 10];
console.log("Сортировка слиянием:", mergeSort(data));
// Вывод: [3, 9, 10, 27, 38, 43, 82]

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

В реальных проектах это нужно постоянно. Отсортируем пользователей сначала по возрасту, а потом по имени.

interface Student {
    name: string;
    age: number;
    grade: number;
}

const students: Student[] = [
    { name: "Иван", age: 17, grade: 4 },
    { name: "Мария", age: 16, grade: 5 },
    { name: "Петр", age: 17, grade: 3 },
    { name: "Анна", age: 16, grade: 4 }
];

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

console.log("Сортировка студентов:");
students.forEach(s => console.log(`${s.name}, ${s.age} лет, оценка: ${s.grade}`));
// Вывод:
// Анна, 16 лет, оценка: 4
// Мария, 16 лет, оценка: 5
// Иван, 17 лет, оценка: 4
// Петр, 17 лет, оценка: 3

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

Если ты уже знаешь Python или планируешь его учить, вот ключевые различия в подходах к сортировке.

Характеристика	TypeScript (JavaScript)	Python
Встроенная функция	`arr.sort()` — сортирует массив на месте (мутирует его). `arr.toSorted()` — возвращает новый массив (ES2023).	`list.sort()` — сортирует на месте. `sorted(list)` — возвращает новый список.
Сортировка чисел	Нужна функция сравнения: `arr.sort((a, b) => a - b)`. Иначе будет сортировать как строки.	Работает «из коробки»: `sorted([3, 1, 2])` → `[1, 2, 3]`. Никаких функций не нужно.
Сортировка строк	Используй `.localeCompare()` для правильной сортировки с учётом языка.	Используй аргумент `key=str.lower` или `locale.strxfrm` для сложных случаев.
Сортировка по ключу	Передаётся функция сравнения (компаратор). Гибко, но нужно писать больше кода.	Передаётся аргумент `key` — функция, которая возвращает значение для сравнения. Очень удобно: `sorted(students, key=lambda s: s.age)`.
Стабильность	Стабильная (с ES2019).	Стабильная.
Сложность алгоритма	Встроенный `.sort()` использует TimSort (O(n log n)).	Встроенный `sorted()` тоже использует TimSort (O(n log n)).

💡 Главное отличие: В Python сортировка «из коробки» работает интуитивно понятно. В TypeScript нужно всегда помнить про функцию сравнения для чисел. Но TypeScript даёт больше контроля над процессом сравнения.

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

Даже опытные программисты иногда спотыкаются на сортировке. Вот список самых частых граблей.

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

const nums = [1, 30, 4, 21];
nums.sort(); // Результат: [1, 21, 30, 4] — полная ерунда!

Решение: Всегда передавай (a, b) => a - b для чисел.

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

.sort() изменяет оригинальный массив. Если тебе нужно сохранить исходные данные, используй .toSorted() (новый метод) или сделай копию: [...arr].sort().

Ошибка 3: Неправильное сравнение строк с буквой «ё»

const words = ['ёлка', 'ель', 'еж'];
words.sort(); // Результат: ['ель', 'еж', 'ёлка'] — неправильно для русского языка

Решение: words.sort((a, b) => a.localeCompare(b, 'ru'));

Ошибка 4: Сортировка объектов без указания поля

const users = [{name: 'Аня'}, {name: 'Боря'}];
users.sort(); // Бесполезно, объекты не сравниваются напрямую

Решение: Всегда указывай поле для сравнения: users.sort((a, b) => a.name.localeCompare(b.name));

Ошибка 5: Путаница с порядком сортировки (возрастание/убывание)

a - b — возрастание. b - a — убывание. Запомни: если результат положительный — элементы меняются местами.

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

Как писать код сортировки, чтобы он был не только правильным, но и красивым, и быстрым?

Используй встроенный .sort() везде, где можно. Он написан профессионалами и оптимизирован лучше, чем твой собственный велосипед. Пиши свои алгоритмы только для учёбы или если нужна специфическая логика.
Всегда делай копию массива, если не хочешь менять оригинал. Используй спред-оператор: const sorted = [...original].sort(...).
Для сложной сортировки объектов пиши отдельную функцию-компаратор. Это сделает код чище.

// Плохо: громоздкая стрелочная функция прямо в sort
users.sort((a, b) => {
    if (a.age !== b.age) return a.age - b.age;
    return a.name.localeCompare(b.name);
});

// Хорошо: выносим логику в отдельную функцию
function compareUsers(a: User, b: User): number {
    if (a.age !== b.age) return a.age - b.age;
    return a.name.localeCompare(b.name);
}
users.sort(compareUsers);

Не бойся рекурсии в Quick Sort и Merge Sort. Но помни, что для очень больших массивов (миллионы элементов) рекурсия может переполнить стек. В таких случаях используют итеративные версии.
Типизируй всё! TypeScript для того и нужен. Если ты сортируешь массив чисел, укажи number[]. Компилятор поймает кучу ошибок за тебя.
Используй readonly для параметров функций. Это явно говорит, что функция не должна менять входной массив.

function safeSort(arr: readonly number[]): number[] {
    return [...arr].sort((a, b) => a - b);
}

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

Проверь, хорошо ли ты усвоил материал. Ответы спрятаны под спойлером — попробуй ответить сам, прежде чем подсматривать.

Что такое «стабильная сортировка» и почему это важно?
Почему встроенный .sort() в JavaScript/TypeScript сортирует числа как [1, 10, 2], а не как [1, 2, 10]?
Какая временная сложность у пузырьковой сортировки и у быстрой сортировки?
В чём разница между arr.sort() и arr.toSorted()?
Как отсортировать массив объектов по убыванию числового поля (например, по возрасту)?
Что такое «опорный элемент» (pivot) в быстрой сортировке?
Почему сортировка вставками может быть быстрее пузырьковой, хотя у обеих сложность O(n²)?
Какой метод сортировки использует подход «разделяй и властвуй»?
Что произойдёт, если передать в .sort() функцию сравнения, которая всегда возвращает 0?
Как отсортировать массив строк в обратном алфавитном порядке с учётом локали?

🔽 Показать ответы

Стабильная сортировка сохраняет относительный порядок равных элементов. Это важно, если ты сортируешь данные по одному полю, а потом по другому (например, сначала по имени, потом по дате).
Потому что по умолчанию .sort() преобразует все элементы в строки и сравнивает их как строки. Строка "10" меньше строки "2", потому что сравниваются первые символы: '1' < '2'.
Пузырьковая: O(n²). Быстрая: в среднем O(n log n), в худшем случае O(n²).
arr.sort() сортирует массив на месте (мутирует его) и возвращает его же. arr.toSorted() (новый метод ES2023) возвращает новый отсортированный массив, не изменяя исходный.
arr.sort((a, b) => b.age - a.age). Меняем местами a и b в вычитании.
Опорный элемент — это элемент, относительно которого массив делится на две части: меньшие и большие. От выбора pivot зависит скорость работы алгоритма.
Сортировка вставками делает меньше перестановок на почти отсортированных данных. Она «вставляет» элемент в нужное место, а не гоняет его через весь массив, как пузырёк.
Быстрая сортировка (Quick Sort) и сортировка слиянием (Merge Sort).
Массив останется в том же порядке, в котором был. Функция сравнения, возвращающая 0, говорит, что все элементы равны, поэтому сортировка ничего не делает.
arr.sort((a, b) => b.localeCompare(a, 'ru')); Меняем местами a и b в localeCompare.

Итог и что изучить дальше

Поздравляю! Ты только что прошёл ускоренный курс по алгоритмам сортировки на TypeScript. Ты узнал:

Что сортировка — это базовая операция, без которой не обходится ни одна программа.
Как работают три ключевых алгоритма: пузырьковый, вставками и быстрый.
Как правильно использовать встроенный метод .sort() и не попасть в ловушку со строками.
Как сортировать объекты и числа, и в чём разница с Python.

← Previous Regular Expressions in TypeScript: A Detailed Guid Next → Search Algorithms in TypeScript: A Detailed Guide