Внедрение ковшеобразного сорта для чисел с плавающей точкой в Python

Введение в ковш-сорт для чисел с плавающей точкой

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

Основная идея проста: вместо сравнения каждой пары элементов (как в сортировке, например, форс-сорт или слияние), ковш-сорт сначала распределяет элементы по ведрам на основе их значений. Каждое ведро естественным образом группирует вместе узкий диапазон значений. После этого простой алгоритм сортировки — часто сортировка вставки или даже рекурсивный вызов к ведер-сорту — завершает работу. Наконец, ведра сцеплены для того, чтобы произвести сортированный массив.

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

Как работает Bucket Sort

Сорт ковша предполагает, что вход равномерно распределен в пределах известного диапазона, как правило . Алгоритм протекает в три фазы:

1. Инициализация: Создайте массив n пустых ведер, где n — это количество элементов.
2. Распределение: Для каждого элемента вычислите его индекс ведра (при условии, что значения находятся в )) и поместите элемент в это ведро.
3. Сортировка и конкатенация: Сортируйте каждое ведро индивидуально (используя любой стабильный или эффективный внутренний сорт), затем конкатенируйте ведра, чтобы получить окончательный сортированный массив.

Ключевое понимание заключается в том, что, поскольку данные равномерно распределены, каждое ведро получает примерно n / n = 1 элемент в среднем.

Обработка Edge Cases

Когда число с плавающей точкой точно равно 1,0, вычисленный индекс будет , что выходит за рамки.Обычным решением является зажим индекса до для таких значений. На практике, если ваши данные строго , этот крайний случай не возникает, но разумно остерегаться его.

Внедрение Bucket Sort в Python

Ниже приведена чистая, готовая к производству реализация типа ковша для чисел с плавающей запятой в диапазоне .

def bucket_sort(arr):
 """Sort an array of floats uniformly distributed in [0, 1)."""
 n = len(arr)
 if n <= 1:
 return arr

 # Create empty buckets
 buckets = [[] for _ in range(n)]

 # Distribute elements into buckets
 for num in arr:
 index = int(num * n)
 # Guard against floating-point index = n (e.g., when num == 1.0)
 if index == n:
 index = n - 1
 buckets[index].append(num)

 # Sort each bucket and concatenate
 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket)) # Python's Timsort is efficient

 return sorted_arr

Функция использует встроенный Python для сортировки каждого ведра. Для ведер, которые являются небольшими (обычно 0-2 элемента), это очень быстро. Для использования в производстве вы можете заменить сортировкой вставки для еще более низких накладных расходов на крошечные ведра.

Сорт ковша для произвольных диапазонов

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

def bucket_sort_scaled(arr, min_val=None, max_val=None):
 if not arr:
 return arr
 if min_val is None:
 min_val = min(arr)
 if max_val is None:
 max_val = max(arr)

 # Guard against identical values
 if max_val == min_val:
 return arr

 n = len(arr)
 buckets = [[] for _ in range(n)]

 for num in arr:
 # Normalize to [0, 1)
 normalized = (num - min_val) / (max_val - min_val)
 index = int(normalized * n)
 if index == n:
 index = n - 1
 buckets[index].append(num)

 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket))
 return sorted_arr

Эта версия более общая, но требует знания или вычисления диапазона. Она хорошо работает, когда распределение данных примерно одинаково в этом диапазоне.

Анализ сложности

Понимание вычислительной стоимости ковша является важным для принятия решения о том, когда его использовать.

Сложность времени

• Лучший случай (однородно распределенные данные): O(n + k), где k — это количество ведер n.Распределение — O(n), и сортировка каждого ведра занимает в среднем постоянное время, поэтому в целом O(n).
• Средний случай: O(n + n2/k), если использовать сорт вставки для ведер.k = n, это становится O(n).
• Худший случай:O(n2), когда все элементы попадают в одно и то же ведро.Это происходит, когда данные не распределены равномерно или когда диапазон очень мал по отношению к числу элементов.

Космическая сложность

Для этого требуется O(n + k) дополнительное пространство для ведер и их содержимого.k = n, это O(n). Используемое пространство сравнимо с пространством для слияний и выше, чем у таких видов, как сортировка на месте.

Преимущества и случаи использования

Сорт ковша сияет в конкретных сценариях, где его предположения:

• Единообразно распределенные данные с плавающей точкой — например, показания датчиков, результаты моделирования Монте-Карло или нормализованные вероятности.
• Большие наборы данных — O(n) средняя производительность делает его привлекательным для сортировки миллионов поплавков, где сортировки сравнения были бы менее эффективными.
• Внешняя сортировка — когда данные находятся на диске, ведра могут обрабатываться независимо и записываться в отдельные файлы, а затем сцепляться.
• Параллельные и графические вычисления — каждое ведро можно сортировать независимо, что позволяет проводить массивный параллелизм.

def insertion_sort(arr):
 for i in range(1, len(arr)):
 key = arr[i]
 j = i - 1
 while j >= 0 and arr[j] > key:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key

def bucket_sort_insertion(arr):
 n = len(arr)
 if n <= 1:
 return arr
 buckets = [[] for _ in range(n)]
 for num in arr:
 index = int(num * n)
 if index == n:
 index = n - 1
 buckets[index].append(num)
 sorted_arr = []
 for bucket in buckets:
 insertion_sort(bucket)
 sorted_arr.extend(bucket)
 return sorted_arr