{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 1 }, "content": [ { "type": "text", "text": "Что такое сортировка?" } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Короткий ответ" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Сортировка — это процесс упорядочивания элементов коллекции (массивов, списков) по заданному ключу или правилу сравнения. Она позволяет быстрее искать, агрегировать и обрабатывать данные. Эффективные сравнительные алгоритмы сортируют за O(n log n), а выбор конкретного алгоритма зависит от требований к стабильности, памяти и размера данных." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Подробный разбор" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Ключевые цели и термины" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Назначение: упорядочить элементы по ключу (число, строка, дата, составной ключ) для ускорения поиска, объединения и аналитики." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Стабильность: стабильная сортировка сохраняет исходный относительный порядок элементов с равными ключами." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "In-place vs out-of-place: in-place использует O(1) дополнительной памяти (кроме стека), out-of-place требует доп. массивы." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Внутренняя vs внешняя: внутренняя (in-memory) работает в ОЗУ; внешняя (external) — при данных, не помещающихся в память (файлы, потоки), обычно на основе сортировки слиянием с многопутевым слиянием." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Сравнительная vs несравнительная: сравнительная использует только сравнения (нижняя граница Ω(n log n)); несравнительная (подсчетом, поразрядная) требует дополнительные предпосылки о ключах и может быть быстрее — O(n + k)." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Часто используемые алгоритмы" } ] }, { "type": "orderedList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Вставками (Insertion Sort): O(n^2) в среднем и худшем, O(n) в лучшем (почти отсортировано); память O(1); стабильный; in-place. Хорош при n ≤ ~50–200 или почти отсортированных данных." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Слиянием (Merge Sort): O(n log n) всегда; память O(n); стабильный; out-of-place. Хорош для больших данных, при необходимости стабильности, для внешней сортировки и связных списков." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Быстрая (Quick Sort): среднее O(n log n), худшее O(n^2); память O(log n) за счет рекурсии; нестабильный; in-place. Часто самая быстрая на практике с хорошим выбором опорного элемента и оптимизациями." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Пирамидальная (Heap Sort): O(n log n) в среднем/худшем; память O(1); нестабильный; in-place. Предсказуемая худшая сложность без доп. памяти." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Подсчетом (Counting Sort): O(n + k); память O(n + k); стабильный при корректной реализации; out-of-place. Работает для целых ключей ограниченного диапазона k." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Поразрядная (Radix Sort): O(d·(n + b)), где d — число разрядов, b — база; память O(n + b); обычно стабильный; out-of-place. Для чисел/строк фиксированного формата." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Выбор алгоритма на практике" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нужна стабильность: Merge Sort/Timsort/Counting/Radix." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Минимум памяти: Quick Sort (in-place) или Heap Sort." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Почти отсортированные данные: Insertion Sort или гибрид (например, Timsort)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Ограниченный диапазон целых ключей: Counting/Radix (очень быстро)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Очень большие данные вне памяти: внешняя сортировка (многопутевое слияние)." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Примеры кода" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "JavaScript: сортировка с компаратором (стабильно по полю)" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Важное правило: компаратор должен возвращать отрицательное/ноль/положительное число, а не true/false." } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "const users = [\n { name: 'Аня', age: 25 },\n { name: 'Иван', age: 20 },\n { name: 'Павел', age: 25 },\n { name: 'Оля', age: 20 }\n];\n\n// Сначала по age по возрастанию, затем по name с учетом локали (стабильно)\nusers.sort((a, b) => {\n if (a.age !== b.age) return a.age - b.age;\n return a.name.localeCompare(b.name, 'ru');\n});\n\nconst nums = [10, 2, 3, 1];\n// Правильно: числовая сортировка\nnums.sort((a, b) => a - b);\n\n// Неправильно: возвращает true/false, что может дать некорректный порядок\n// nums.sort((a, b) => a < b);\n\n// Примечание: современные реализации JS (ES2019+) делают Array.prototype.sort стабильной." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Быстрая сортировка (QuickSort) in-place" } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "function quickSort(arr, left = 0, right = arr.length - 1) {\n if (left >= right) return arr;\n const pivot = arr[(left + right) >> 1];\n let i = left, j = right;\n while (i <= j) {\n while (arr[i] < pivot) i++;\n while (arr[j] > pivot) j--;\n if (i <= j) {\n [arr[i], arr[j]] = [arr[j], arr[i]];\n i++; j--;\n }\n }\n if (left < j) quickSort(arr, left, j);\n if (i < right) quickSort(arr, i, right);\n return arr;\n}\n\nconsole.log(quickSort([3, 6, 1, 5, 2, 4]));" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Сортировка слиянием (MergeSort) — стабильная" } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "function mergeSort(arr) {\n if (arr.length <= 1) return arr;\n const mid = arr.length >> 1;\n const left = mergeSort(arr.slice(0, mid));\n const right = mergeSort(arr.slice(mid));\n const res = [];\n let i = 0, j = 0;\n while (i < left.length && j < right.length) {\n if (left[i] <= right[j]) {\n res.push(left[i++]);\n } else {\n res.push(right[j++]);\n }\n }\n return res.concat(left.slice(i), right.slice(j));\n}\n\nconsole.log(mergeSort([5, 2, 4, 6, 1, 3]));" } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Типичные ошибки" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Компаратор возвращает true/false, а не число (JS). Должно быть: a - b или localeCompare." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Игнорирование локали при строках: 'ё'/'е', регистр, числовая сортировка строк ('10' < '2'). Используйте localeCompare или предварительную нормализацию." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Выбор O(n^2) алгоритмов на больших данных без необходимости (Bubble/Selection/Insertion на несортированных массивах)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Непродуманная память: Merge Sort требует O(n) дополнительной памяти; для очень больших массивов используйте внешнее слияние или in-place подходы." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Отсутствие стабильности там, где важен исходный порядок равных ключей (например, многокритериальная сортировка)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Плохой выбор опорного элемента в QuickSort может привести к O(n^2). Используйте медиану трёх, случайный pivot или гибридизацию." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Краткая памятка по сложностям" } ] }, { "type": "table", "content": [ { "type": "tableRow", "content": [ { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Алгоритм" } ] } ] }, { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Средняя" } ] } ] }, { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Худшая" } ] } ] }, { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Память" } ] } ] }, { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Стабильная" } ] } ] }, { "type": "tableHeader", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "In-place" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Пузырьковая" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(1)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Вставками" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(1)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Выбором" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(1)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Слиянием" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Быстрая (Quick)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n^2)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Пирамидальная (Heap)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n log n)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(1)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет (обычно)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Подсчетом (Counting)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n + k)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n + k)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n + k)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Да (если делать префиксные суммы)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет" } ] } ] } ] }, { "type": "tableRow", "content": [ { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Поразрядная (Radix)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(d·(n + b))" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(d·(n + b))" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "O(n + b)" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Обычно да" } ] } ] }, { "type": "tableCell", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Нет" } ] } ] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Итог" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Сортировка — базовый инструмент для работы с данными. Понимание стабильности, асимптотик, требований к памяти и природы ключей помогает осознанно выбирать алгоритм: Timsort/Merge для стабильности, Quick/Heap для in-place, Counting/Radix для целочисленных диапазонов. В прикладном коде особенно важно корректно задавать компаратор и учитывать локаль/тип ключей." } ] } ] }

Что такое сортировка?

Комментарии