2.7 KiB
Executable File
Алгоритм в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения. Сложность алгоритма: O(n).
Алгоритм
Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).
Идея алгоритма заключается в том, чтобы разбить отрезок [0, 1) на $n$ одинаковых отрезков (карманов), и разделить по этим карманам $n$ входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путём последовательного перечисления элементов каждого кармана.
Пример
!
В виде кода
def block_sort(arr, block_size=5):
if not arr:
return arr
min_val = min(arr)
max_val = max(arr)
block_count = (max_val - min_val) // block_size + 1
blocks = [[] for _ in range(block_count)]
for x in arr:
index = (x - min_val) // block_size
blocks[index].append(x)
result = []
for block in blocks:
block.sort()
result.extend(block)
return result