Всем привет! Следуя Сортировке выбором, я решил использовать алгоритм сортировки сегментом. Его название очень наводит на размышления, поскольку алгоритм основан на распределении элементов массива по ряду сегментов, а затем сортировке каждого сегмента либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения этого самого алгоритма сортировки по сегментам — хотя мы не будем этого делать. не охватывать рекурсивный подход. В конце концов, эти отсортированные сегменты объединятся в полностью отсортированный массив. Итак, вкратце, алгоритм состоит из 4 шагов:

  1. Создайте массив пустых ведер;
  2. Поместите все элементы массива в ведра;
  3. Сортируйте каждое ведро;
  4. Пройдитесь по всем корзинам по порядку и постройте полностью отсортированный массив.

С точки зрения сложности его сложность в лучшем и среднем случае составляет O(N+K), где K — количество сегментов, а N — количество элементов во входном массиве.

Между тем, стоит отметить, что его сложность в худшем случае является квадратичной (O(N²)). В худшем случае все элементы массива попадут в одно ведро. В этом случае сложность очень сильно зависит от алгоритма сортировки, который мы выбираем для сортировки ведра. На этот раз воспользуемся уже рассмотренным алгоритмом сортировки для сегментной сортировки — Insertion Sort. Этот конкретный алгоритм имеет квадратичную среднюю сложность, поэтому сложность Bucket Sort в худшем случае по этой причине также является квадратичной.

Приведем пример: учитывая, что arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4] и что мы хотим отсортировать его в порядке возрастания, используя число из 5 сегментов, мы будем действовать так :

  • инициализировать результирующий массив пустым списком, а список сегментов — списком из 5 пустых списков: [[], [], [], [], []];
  • вычислить размер ведра: (max_element — min_element) / no_of_buckets. Это даст нам 1,8;
  • начните разбрасывать элементы в ведрах, один за другим. Для этого нам нужно вычислить индекс — ведро, в которое попадет наш элемент. Используя (element — min_element) / bucket_size, мы определяем корзину, в которую мы должны поместить элемент. Однако следует отметить, что если наш элемент окажется максимальным элементом, это вычисление даст индекс, выходящий за пределы. В нашем случае это будет 9. Минимальный элемент будет 0, и, используя размер корзины 1,8, мы получим индекс 9 / 1,8, что даст нам 5. Теперь, поскольку в массиве корзин всего 5 корзин (0…4) корзины номер 5 не существует, поэтому нам нужно уменьшить этот результат на 1, но только для этой конкретной ситуации;
  • в конце процесса разбрасывания элементов корзины будут выглядеть так: [[0, 1], [2, 3], [5, 4], [7, 6], [9, 8]];
  • теперь пришло время отсортировать ведра по отдельности, а затем добавить их по порядку в результирующий массив:
  • добавление ведра [0, 1], теперь массив [0, 1];
  • добавление ведра [2, 3], теперь массив [0, 1, 2, 3];
  • добавление ведра [4, 5], теперь массив [0, 1, 2, 3, 4, 5];
  • добавление ведра [6, 7], теперь массив [0, 1, 2, 3, 4, 5, 6, 7];
  • добавление ведра [8, 9], теперь массив [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  • мы можем безопасно вернуть отсортированный массив. Полный код Python ниже.
def insertion_sort(arr):
    """Algorithm for sorting the buckets."""
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1
        while j >= 0 and temp < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp
    return arr

def bucket_sort(arr):
    """Main sorting algorithm function."""
    # variable initialization
    # no_of_buckets can be an input arg instead of local var
    result = []
    no_of_buckets = 5
    buckets = [[] for i in range(no_of_buckets)]
    max_elem, min_elem = max(arr), min(arr)
    bucket_size = (max_elem - min_elem) / no_of_buckets
    # distribute elements in corresponding buckets
    for element in arr:
        index = int((element - min_elem) / bucket_size)
        index -= 1 if element == max_elem else 0
        buckets[index].append(element)
    # sort the buckets one by one, then add them to the result
    for bucket in buckets:
        result.extend(insertion_sort(bucket))
    return result

Это не обычные простые и понятные алгоритмы сортировки, с которыми мы до сих пор сталкивались, но и этот тоже довольно легко понять. Ждем следующего! Как всегда, оставайтесь в безопасности и счастливого кодирования!