11.8 Блочная сортировка¶
Рассмотренные выше алгоритмы сортировки относятся к "сортировкам на основе сравнений": они упорядочивают данные, сравнивая элементы друг с другом. Временная сложность таких алгоритмов не может быть лучше \(O(n \log n)\) . Далее мы рассмотрим несколько "сортировок без сравнений", чья временная сложность может достигать линейного порядка.
Блочная сортировка (bucket sort) является типичным применением стратегии "разделяй и властвуй". Она задает несколько упорядоченных по диапазонам блоков, каждый блок соответствует некоторому диапазону значений; затем данные равномерно распределяются по блокам, внутри каждого блока выполняется сортировка, а в конце результаты блоков объединяются по порядку.
11.8.1 Алгоритм¶
Рассмотрим массив длины \(n\), элементы которого являются числами с плавающей запятой из диапазона \([0, 1)\) . Процесс блочной сортировки показан на рисунке 11-13.
- Инициализировать \(k\) блоков и распределить \(n\) элементов по этим \(k\) блокам.
- Отсортировать каждый блок по отдельности (здесь используется встроенная функция сортировки языка программирования).
- Объединить результаты в порядке следования блоков от меньшего к большему.
Рисунок 11-13 Процесс блочной сортировки
Код приведен ниже:
bucket_sort.py
def bucket_sort(nums: list[float]):
"""Сортировка корзинами"""
# Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
k = len(nums) // 2
buckets = [[] for _ in range(k)]
# 1. Распределить элементы массива по корзинам
for num in nums:
# Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
i = int(num * k)
# Добавить num в корзину i
buckets[i].append(num)
# 2. Выполнить сортировку внутри каждой корзины
for bucket in buckets:
# Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort()
# 3. Обойти корзины и объединить результаты
i = 0
for bucket in buckets:
for num in bucket:
nums[i] = num
i += 1
bucket_sort.cpp
/* Сортировка корзинами */
void bucketSort(vector<float> &nums) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
int k = nums.size() / 2;
vector<vector<float>> buckets(k);
// 1. Распределить элементы массива по корзинам
for (float num : nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
int i = num * k;
// Добавить num в корзину bucket_idx
buckets[i].push_back(num);
}
// 2. Выполнить сортировку внутри каждой корзины
for (vector<float> &bucket : buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
sort(bucket.begin(), bucket.end());
}
// 3. Обойти корзины и объединить результаты
int i = 0;
for (vector<float> &bucket : buckets) {
for (float num : bucket) {
nums[i++] = num;
}
}
}
bucket_sort.java
/* Сортировка корзинами */
void bucketSort(float[] nums) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
int k = nums.length / 2;
List<List<Float>> buckets = new ArrayList<>();
for (int i = 0; i < k; i++) {
buckets.add(new ArrayList<>());
}
// 1. Распределить элементы массива по корзинам
for (float num : nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
int i = (int) (num * k);
// Добавить num в корзину i
buckets.get(i).add(num);
}
// 2. Выполнить сортировку внутри каждой корзины
for (List<Float> bucket : buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
Collections.sort(bucket);
}
// 3. Обойти корзины и объединить результаты
int i = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
nums[i++] = num;
}
}
}
bucket_sort.cs
/* Сортировка корзинами */
void BucketSort(float[] nums) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
int k = nums.Length / 2;
List<List<float>> buckets = [];
for (int i = 0; i < k; i++) {
buckets.Add([]);
}
// 1. Распределить элементы массива по корзинам
foreach (float num in nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
int i = (int)(num * k);
// Добавить num в корзину i
buckets[i].Add(num);
}
// 2. Выполнить сортировку внутри каждой корзины
foreach (List<float> bucket in buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.Sort();
}
// 3. Обойти корзины и объединить результаты
int j = 0;
foreach (List<float> bucket in buckets) {
foreach (float num in bucket) {
nums[j++] = num;
}
}
}
bucket_sort.go
/* Сортировка корзинами */
func bucketSort(nums []float64) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
k := len(nums) / 2
buckets := make([][]float64, k)
for i := 0; i < k; i++ {
buckets[i] = make([]float64, 0)
}
// 1. Распределить элементы массива по корзинам
for _, num := range nums {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
i := int(num * float64(k))
// Добавить num в корзину i
buckets[i] = append(buckets[i], num)
}
// 2. Выполнить сортировку внутри каждой корзины
for i := 0; i < k; i++ {
// Использовать встроенную функцию сортировки среза; ее также можно заменить другим алгоритмом сортировки
sort.Float64s(buckets[i])
}
// 3. Обойти корзины и объединить результаты
i := 0
for _, bucket := range buckets {
for _, num := range bucket {
nums[i] = num
i++
}
}
}
bucket_sort.swift
/* Сортировка корзинами */
func bucketSort(nums: inout [Double]) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
let k = nums.count / 2
var buckets = (0 ..< k).map { _ in [Double]() }
// 1. Распределить элементы массива по корзинам
for num in nums {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
let i = Int(num * Double(k))
// Добавить num в корзину i
buckets[i].append(num)
}
// 2. Выполнить сортировку внутри каждой корзины
for i in buckets.indices {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
buckets[i].sort()
}
// 3. Обойти корзины и объединить результаты
var i = nums.startIndex
for bucket in buckets {
for num in bucket {
nums[i] = num
i += 1
}
}
}
bucket_sort.js
/* Сортировка корзинами */
function bucketSort(nums) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
const k = nums.length / 2;
const buckets = [];
for (let i = 0; i < k; i++) {
buckets.push([]);
}
// 1. Распределить элементы массива по корзинам
for (const num of nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
const i = Math.floor(num * k);
// Добавить num в корзину i
buckets[i].push(num);
}
// 2. Выполнить сортировку внутри каждой корзины
for (const bucket of buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort((a, b) => a - b);
}
// 3. Обойти корзины и объединить результаты
let i = 0;
for (const bucket of buckets) {
for (const num of bucket) {
nums[i++] = num;
}
}
}
bucket_sort.ts
/* Сортировка корзинами */
function bucketSort(nums: number[]): void {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
const k = nums.length / 2;
const buckets: number[][] = [];
for (let i = 0; i < k; i++) {
buckets.push([]);
}
// 1. Распределить элементы массива по корзинам
for (const num of nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
const i = Math.floor(num * k);
// Добавить num в корзину i
buckets[i].push(num);
}
// 2. Выполнить сортировку внутри каждой корзины
for (const bucket of buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort((a, b) => a - b);
}
// 3. Обойти корзины и объединить результаты
let i = 0;
for (const bucket of buckets) {
for (const num of bucket) {
nums[i++] = num;
}
}
}
bucket_sort.dart
/* Сортировка корзинами */
void bucketSort(List<double> nums) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
int k = nums.length ~/ 2;
List<List<double>> buckets = List.generate(k, (index) => []);
// 1. Распределить элементы массива по корзинам
for (double _num in nums) {
// Входные данные находятся в диапазоне [0, 1), используем _num * k для отображения в диапазон индексов [0, k-1]
int i = (_num * k).toInt();
// Добавить _num в корзину bucket_idx
buckets[i].add(_num);
}
// 2. Выполнить сортировку внутри каждой корзины
for (List<double> bucket in buckets) {
bucket.sort();
}
// 3. Обойти корзины и объединить результаты
int i = 0;
for (List<double> bucket in buckets) {
for (double _num in bucket) {
nums[i++] = _num;
}
}
}
bucket_sort.rs
/* Сортировка корзинами */
fn bucket_sort(nums: &mut [f64]) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
let k = nums.len() / 2;
let mut buckets = vec![vec![]; k];
// 1. Распределить элементы массива по корзинам
for &num in nums.iter() {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
let i = (num * k as f64) as usize;
// Добавить num в корзину i
buckets[i].push(num);
}
// 2. Выполнить сортировку внутри каждой корзины
for bucket in &mut buckets {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
}
// 3. Обойти корзины и объединить результаты
let mut i = 0;
for bucket in buckets.iter() {
for &num in bucket.iter() {
nums[i] = num;
i += 1;
}
}
}
bucket_sort.c
/* Сортировка корзинами */
void bucketSort(float nums[], int n) {
int k = n / 2; // Инициализировать k = n/2 корзин
int *sizes = malloc(k * sizeof(int)); // Записать размер каждой корзины
float **buckets = malloc(k * sizeof(float *)); // Массив динамических массивов (корзины)
// Предварительно выделить достаточно места для каждой корзины
for (int i = 0; i < k; ++i) {
buckets[i] = (float *)malloc(n * sizeof(float));
sizes[i] = 0;
}
// 1. Распределить элементы массива по корзинам
for (int i = 0; i < n; ++i) {
int idx = (int)(nums[i] * k);
buckets[idx][sizes[idx]++] = nums[i];
}
// 2. Выполнить сортировку внутри каждой корзины
for (int i = 0; i < k; ++i) {
qsort(buckets[i], sizes[i], sizeof(float), compare);
}
// 3. Объединить отсортированные корзины
int idx = 0;
for (int i = 0; i < k; ++i) {
for (int j = 0; j < sizes[i]; ++j) {
nums[idx++] = buckets[i][j];
}
// Освободить память
free(buckets[i]);
}
}
bucket_sort.kt
/* Сортировка корзинами */
fun bucketSort(nums: FloatArray) {
// Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
val k = nums.size / 2
val buckets = mutableListOf<MutableList<Float>>()
for (i in 0..<k) {
buckets.add(mutableListOf())
}
// 1. Распределить элементы массива по корзинам
for (num in nums) {
// Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
val i = (num * k).toInt()
// Добавить num в корзину i
buckets[i].add(num)
}
// 2. Выполнить сортировку внутри каждой корзины
for (bucket in buckets) {
// Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort()
}
// 3. Обойти корзины и объединить результаты
var i = 0
for (bucket in buckets) {
for (num in bucket) {
nums[i++] = num
}
}
}
bucket_sort.rb
### Сортировка корзинами ###
def bucket_sort(nums)
# Инициализировать k = n/2 корзин, предполагая распределение 2 элементов в каждую корзину
k = nums.length / 2
buckets = Array.new(k) { [] }
# 1. Распределить элементы массива по корзинам
nums.each do |num|
# Входные данные лежат в диапазоне [0, 1); использовать num * k для отображения в диапазон индексов [0, k-1]
i = (num * k).to_i
# Добавить num в корзину i
buckets[i] << num
end
# 2. Выполнить сортировку внутри каждой корзины
buckets.each do |bucket|
# Использовать встроенную функцию сортировки; ее также можно заменить другим алгоритмом сортировки
bucket.sort!
end
# 3. Обойти корзины и объединить результаты
i = 0
buckets.each do |bucket|
bucket.each do |num|
nums[i] = num
i += 1
end
end
end
Визуализация кода
11.8.2 Характеристики алгоритма¶
Блочная сортировка подходит для обработки очень больших объемов данных. Например, если вход содержит 1 миллион элементов и из-за ограничений памяти система не может загрузить их все сразу, можно разбить данные на 1000 блоков, отсортировать каждый блок отдельно, а затем объединить результаты.
- Временная сложность равна \(O(n + k)\) : если элементы распределены по блокам равномерно, то в каждом блоке будет \(\frac{n}{k}\) элементов. Если сортировка одного блока требует \(O(\frac{n}{k} \log\frac{n}{k})\) времени, то сортировка всех блоков потребует \(O(n \log\frac{n}{k})\) времени. Когда число блоков \(k\) достаточно велико, временная сложность приближается к \(O(n)\) . На объединение результатов требуется \(O(n + k)\) времени, потому что нужно пройти по всем блокам и элементам. В худшем случае все данные попадут в один блок, и если сортировка этого блока использует \(O(n^2)\) времени, общая сложность также станет \(O(n^2)\) .
- Пространственная сложность равна \(O(n + k)\), сортировка не выполняется на месте: требуются дополнительные блоки в количестве \(k\) и место для всех \(n\) элементов внутри них.
- Является ли блочная сортировка стабильной, зависит от того, стабилен ли алгоритм сортировки внутри каждого блока.
11.8.3 Как добиться равномерного распределения¶
Теоретически временная сложность блочной сортировки может достигать \(O(n)\) ; ключ к этому - как можно более равномерно распределить элементы по блокам. На практике данные часто распределены неравномерно. Например, если нужно распределить все товары на Taobao по 10 блокам цен, количество товаров дешевле 100 юаней может быть очень большим, а товаров дороже 1000 юаней - очень маленьким. Если просто разбить диапазон цен на 10 равных частей, число товаров в каждом блоке будет сильно различаться.
Чтобы добиться более равномерного распределения, можно сначала задать грубую линию раздела и приблизительно распределить данные по 3 блокам. После этого блоки с большим числом товаров можно снова делить на 3 блока и продолжать процесс до тех пор, пока число элементов в каждом блоке не станет примерно одинаковым.
Как показано на рисунке 11-14, по сути этот метод строит рекурсивное дерево, цель которого - сделать значения в листьях как можно более равномерными. Конечно, совсем не обязательно каждый раз делить данные именно на 3 блока; конкретную схему разбиения можно выбирать в зависимости от свойств данных.
Рисунок 11-14 Рекурсивное разбиение по блокам
Если нам заранее известна вероятностная модель распределения цен товаров, то границы каждого блока можно задавать в соответствии с этим распределением. Важно отметить, что фактическое распределение данных не обязательно специально измерять - его можно приблизить некоторой вероятностной моделью исходя из свойств данных.
Как показано на рисунке 11-15, если предположить, что цены товаров подчиняются нормальному распределению, то можно разумно задать интервалы цен и тем самым распределить товары по блокам достаточно равномерно.
Рисунок 11-15 Разбиение блоков по вероятностному распределению