Блочная сортировка Описание сортировки - Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Алгоритм сортировки Идея алгоритма заключается в том, чтобы разбить отрезок [a, b) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах при помощи рекурсивного вызова той же функции. Отсортированный массив получается путём последовательного перечисления элементов каждого кармана. Плюсы и минусы алгоритма - Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).
- Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента.
Сложность алгоритма Реализация алгоритма сортировки - Функция checkAllDigits принимает на вход массив чисел(один из блоков сортировки) и проверяет, равны ли все его элементы.
- Функция summ принимает на вход массив чисел, и возвращает их сумму
- Функция input заполняет массив n случайных чисел
- Функция output выводит отсортированный массив на экран
- Основная функция сортировки bucketSort принимает на вход массив с числами. Далее идет проверка всех чисел в массиве. Если они все равны, или массив состоит из 1 числа, то функция вернет сам массив. Иначе массив разбивается на 2 блока, в одном из которых числа, меньшие среднего значения, в другом числа, большие среднего значения массива. Далее идет рекурсивный вызов функции для каждого из 2 блоков, после чего отсортированные блоки по порядку добавляются в итоговый массив.
|
Скачать 0.75 Mb.