Bucket Sort (Блочная сортировка / Карманная сортировка)
Краткое описание
Алгоритм распределительной сортировки, который разделяет массив на конечное число корзин (buckets), сортирует каждую корзину отдельно (обычно Insertion Sort), а затем объединяет их. Эффективен когда входные данные равномерно распределены по диапазону значений, давая линейное время O(n+k) в среднем случае.
Когда использовать
- Равномерное распределение данных — когда элементы распределены примерно равномерно по диапазону значений (например, случайные числа с плавающей точкой от 0 до 1)
- Известный диапазон значений — когда заранее известны минимум и максимум
- Числа с плавающей точкой — особенно эффективен для float/double в диапазоне [0, 1)
- Параллелизация возможна — корзины можно сортировать независимо и параллельно
- Внешняя сортировка — когда данные слишком велики для памяти, можно распределить по файлам
- Линейная производительность важна — при хорошем распределении работает за O(n)
Когда не стоит использовать:
- Неравномерное распределение данных — все элементы могут попасть в одну корзину, что даст O(n²)
- Неизвестный диапазон — сложно определить границы корзин
- Ограниченная память — требует O(n+k) дополнительной памяти для корзин
- Маленькие массивы — накладные расходы на создание корзин не окупятся
- Данные сложного типа — трудно определить функцию распределения по корзинам
С объяснением логики работы
/**
* Bucket Sort для чисел с плавающей точкой в диапазоне [0, 1)
*
* Идея:
* 1. Создаём k пустых корзин (buckets)
* 2. Распределяем элементы по корзинам
* 3. Сортируем каждую корзину (обычно Insertion Sort)
* 4. Объединяем корзины по порядку
*/
/**
* Bucket Sort для чисел в диапазоне [0, 1)
*/
function bucketSortFloat(arr) {
if (arr.length <= 1) return arr;
const n = arr.length;
// ШАГ 1: Создаём пустые корзины
// Количество корзин = n (эмпирически оптимально)
const buckets = Array.from({length: n}, () => []);
// ШАГ 2: Распределяем элементы по корзинам
// Функция распределения: bucket_index = floor(value * n)
// Для value в [0, 1): bucket_index будет в [0, n)
for (let i = 0; i < n; i++) {
const value = arr[i];
// Вычисляем индекс корзины
// Примеры: 0.15 → bucket 1, 0.75 → bucket 7 (при n=10)
// clamp: при value === 1.0 floor(value*n) === n (выход за границы)
const bucketIndex = Math.min(Math.floor(value * n), n - 1);
// Добавляем элемент в соответствующую корзину
buckets[bucketIndex].push(value);
}
// ШАГ 3: Сортируем каждую корзину
// Используем Insertion Sort, так как корзины обычно малы
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
}
// ШАГ 4: Объединяем отсортированные корзины
let index = 0;
for (let i = 0; i < buckets.length; i++) {
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
return arr;
}
/**
* Insertion Sort для сортировки корзин
*/
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
// Пример использования
const floatNumbers = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51];
console.log("Исходный массив:", floatNumbers);
bucketSortFloat(floatNumbers);
console.log("Отсортированный массив:", floatNumbers);
/**
* Универсальный Bucket Sort для целых чисел в произвольном диапазоне
*/
function bucketSort(arr) {
if (arr.length <= 1) return arr;
const n = arr.length;
// Находим минимум и максимум для определения диапазона
let min = arr[0];
let max = arr[0];
for (let i = 1; i < n; i++) {
if (arr[i] < min) min = arr[i];
if (arr[i] > max) max = arr[i];
}
// Если все элементы одинаковые
if (min === max) return arr;
// Определяем размер каждой корзины
const range = max - min + 1;
const bucketCount = Math.max(Math.floor(Math.sqrt(n)), 1);
const bucketSize = Math.ceil(range / bucketCount);
// Создаём корзины
const buckets = Array.from({length: bucketCount}, () => []);
// Распределяем элементы по корзинам
for (let i = 0; i < n; i++) {
const bucketIndex = Math.min(
Math.floor((arr[i] - min) / bucketSize),
bucketCount - 1
);
buckets[bucketIndex].push(arr[i]);
}
// Сортируем каждую корзину и объединяем
let index = 0;
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
return arr;
}
// Пример с целыми числами
const integers = [64, 34, 25, 12, 22, 11, 90, 88, 45];
console.log("Исходный массив:", integers);
bucketSort(integers);
console.log("Отсортированный массив:", integers);
/**
* ПОЧЕМУ BUCKET SORT ЭФФЕКТИВЕН:
*
* При равномерном распределении:
* - Каждая корзина получает примерно n/k элементов
* - Сортировка одной корзины: O((n/k)²) используя Insertion Sort
* - Всего k корзин: k * O((n/k)²) = O(n²/k)
* - При k ≈ n: O(n²/n) = O(n)
*
* Сравнение с Quick Sort:
* - Quick Sort: всегда O(n log n)
* - Bucket Sort: O(n) при хорошем распределении
*
* НО: при плохом распределении (все в одной корзине) → O(n²)
*/
/**
* Пример с плохим распределением:
*/
const badDistribution = [0.01, 0.02, 0.03, 0.04, 0.05]; // Все в bucket 0
// bucketSortFloat будет O(n²), так как все элементы в одной корзине
/**
* Пример с хорошим распределением:
*/
const goodDistribution = [0.1, 0.3, 0.5, 0.7, 0.9]; // Равномерно распределены
// bucketSortFloat будет O(n), так как по 1 элементу в корзинеС анализом сложностей
/**
* Bucket Sort с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n + k) — равномерное распределение, где k — число корзин
* - Средний случай: O(n + n²/k + k) ≈ O(n) при k = n
* - Худший случай: O(n²) — все элементы в одной корзине
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(n + k) — массивы для корзин и элементы
*
* ОСОБЕННОСТИ:
* - Стабильный (при использовании стабильной сортировки для корзин)
* - Не in-place (требует дополнительную память)
* - Распределительная сортировка (distribution sort)
*/
function bucketSortFloat(arr) {
if (arr.length <= 1) return arr;
const n = arr.length;
// ШАГ 1: Создание корзин — O(n) время и память
// Создаём n пустых корзин (массивов)
const buckets = Array.from({length: n}, () => []);
// ШАГ 2: Распределение элементов — O(n)
// Один проход по массиву
for (let i = 0; i < n; i++) {
const value = arr[i];
const bucketIndex = Math.min(Math.floor(value * n), n - 1);
// Добавление в массив: O(1) amortized
buckets[bucketIndex].push(value);
}
// ШАГ 3: Сортировка корзин
// АНАЛИЗ:
// Пусть bucket i содержит n_i элементов
// Сумма всех n_i = n (все элементы распределены)
//
// Сортировка bucket i используя Insertion Sort: O(n_i²)
// Суммарное время: ∑ O(n_i²)
//
// ЛУЧШИЙ СЛУЧАЙ (равномерное распределение):
// - Каждая корзина содержит ~n/n = 1 элемент
// - ∑ O(1²) = O(n) * O(1) = O(n)
//
// СРЕДНИЙ СЛУЧАЙ (случайное равномерное распределение):
// - E[n_i] = n/k где k — число корзин
// - E[∑ n_i²] = n + n(n-1)/k при k=n: E[∑ n_i²] = 2n
// - ∑ O(n_i²) = O(2n) = O(n)
//
// ХУДШИЙ СЛУЧАЙ (все в одной корзине):
// - Одна корзина содержит n элементов
// - O(n²)
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
}
// ШАГ 4: Объединение корзин — O(n)
// Копируем все n элементов обратно
let index = 0;
for (let i = 0; i < buckets.length; i++) {
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
// ИТОГОВАЯ СЛОЖНОСТЬ:
// Время: O(n) создание + O(n) распределение + O(∑n_i²) сортировка + O(n) объединение
// = O(n + ∑n_i²)
// = O(n) в среднем при равномерном распределении
// = O(n²) в худшем
// Память: O(n + k) для корзин
return arr;
}
function insertionSort(arr) {
// Временная сложность: O(n²) где n — размер arr
// Пространственная сложность: O(1)
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
/**
* Универсальный Bucket Sort с детальным анализом
*/
function bucketSort(arr) {
if (arr.length <= 1) return arr;
const n = arr.length;
// Поиск min/max: O(n)
let min = arr[0];
let max = arr[0];
for (let i = 1; i < n; i++) {
if (arr[i] < min) min = arr[i];
if (arr[i] > max) max = arr[i];
}
if (min === max) return arr;
// ВЫБОР КОЛИЧЕСТВА КОРЗИН
// Эмпирически оптимально: k = √n
// - При k = 1: деградирует до Insertion Sort O(n²)
// - При k = n: каждый элемент в своей корзине, но накладные расходы
// - При k = √n: баланс между числом корзин и их размером
const range = max - min + 1;
const bucketCount = Math.max(Math.floor(Math.sqrt(n)), 1);
const bucketSize = Math.ceil(range / bucketCount);
// Создание корзин: O(k)
const buckets = Array.from({length: bucketCount}, () => []);
// Распределение: O(n)
for (let i = 0; i < n; i++) {
const bucketIndex = Math.min(
Math.floor((arr[i] - min) / bucketSize),
bucketCount - 1
);
buckets[bucketIndex].push(arr[i]);
}
// Сортировка и объединение: O(n + ∑n_i²)
let index = 0;
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
return arr;
}
/**
* МАТЕМАТИЧЕСКИЙ АНАЛИЗ СРЕДНЕГО СЛУЧАЯ
*
* Предположения:
* - n элементов
* - k = n корзин
* - Элементы равномерно распределены
*
* Вероятность попадания элемента в bucket i: p = 1/n
*
* Матожидание числа элементов в bucket i:
* E[n_i] = n * p = n * (1/n) = 1
*
* Дисперсия числа элементов в bucket i:
* Var[n_i] = n * p * (1-p) ≈ 1
*
* Матожидание суммы квадратов:
* E[∑ n_i²] = ∑ E[n_i²]
* = ∑ (Var[n_i] + E[n_i]²)
* = n * (1 + 1)
* = 2n
*
* Средняя сложность: O(2n) = O(n)
*/
/**
* СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ:
*
* Bucket Sort vs Quick Sort:
* ✓ Bucket Sort: O(n) в среднем при равномерном распределении
* ✗ Bucket Sort: O(n²) в худшем, требует O(n) памяти
* ✓ Quick Sort: O(n log n) в среднем, O(log n) памяти
* ✗ Quick Sort: O(n²) в худшем
*
* Bucket Sort vs Radix Sort:
* ✓ Bucket Sort: работает с float
* ✗ Bucket Sort: требует равномерное распределение
* ✓ Radix Sort: предсказуемая O(d·n)
* ✗ Radix Sort: только целые числа/строки
*
* Bucket Sort vs Counting Sort:
* ✓ Bucket Sort: работает с любым диапазоном
* ✗ Bucket Sort: не O(n+k) гарантированно
* ✓ Counting Sort: гарантированная O(n+k)
* ✗ Counting Sort: только малый диапазон целых
*/
// ПРИМЕРЫ ПРОИЗВОДИТЕЛЬНОСТИ:
// ЛУЧШИЙ СЛУЧАЙ: равномерное распределение
function testBestCase() {
const n = 10000;
const arr = Array.from({length: n}, () => Math.random());
console.time('Bucket Sort (Best)');
bucketSortFloat(arr);
console.timeEnd('Bucket Sort (Best)');
// Ожидается: O(n) ≈ 10ms
}
// ХУДШИЙ СЛУЧАЙ: все в одной корзине
function testWorstCase() {
const n = 10000;
const arr = Array.from({length: n}, () => 0.001 + Math.random() * 0.001);
console.time('Bucket Sort (Worst)');
bucketSortFloat(arr);
console.timeEnd('Bucket Sort (Worst)');
// Ожидается: O(n²) ≈ 100-200ms
}
// РЕАЛЬНЫЙ ПРИМЕР: оценки студентов (0-100)
function sortGrades() {
const grades = [95, 87, 91, 87, 95, 82, 91, 87, 95, 91, 78, 85, 92];
// Нормализуем в [0, 1)
const normalized = grades.map(g => g / 100);
bucketSortFloat(normalized);
const sorted = normalized.map(g => Math.round(g * 100));
console.log('Sorted grades:', sorted);
}