Всем привет! Следуя Сортировке выбором, я решил использовать алгоритм сортировки сегментом. Его название очень наводит на размышления, поскольку алгоритм основан на распределении элементов массива по ряду сегментов, а затем сортировке каждого сегмента либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения этого самого алгоритма сортировки по сегментам — хотя мы не будем этого делать. не охватывать рекурсивный подход. В конце концов, эти отсортированные сегменты объединятся в полностью отсортированный массив. Итак, вкратце, алгоритм состоит из 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
Это не обычные простые и понятные алгоритмы сортировки, с которыми мы до сих пор сталкивались, но и этот тоже довольно легко понять. Ждем следующего! Как всегда, оставайтесь в безопасности и счастливого кодирования!