Вступление

В этом руководстве мы погрузимся в теорию и реализацию Bucket Sort в Python.

Bucket Sort - это алгоритм типа сравнения, который назначает элементы списка, которые мы хотим отсортировать, в Buckets или Bins . Затем содержимое этих сегментов сортируется, как правило, с помощью другого алгоритма. После сортировки содержимое корзин складывается, образуя отсортированную коллекцию.

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

Мы реализуем Bucket Sort в Python и проанализируем ее временную сложность.

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

Прежде чем перейти к его точной реализации, давайте пройдемся по этапам алгоритма:

1. Составьте список пустых корзин. Ведро инициализируется для каждого элемента в массиве.
2. Пройдитесь по списку сегментов и вставьте элементы из массива. Место вставки каждого элемента зависит от входного списка и самого большого элемента в нем. Мы можем получить 0..n элементов в каждой корзине. Это будет подробно описано в визуальном представлении алгоритма.
3. Отсортируйте каждое непустое ведро. Вы можете сделать это с помощью любого алгоритма сортировки. Поскольку мы работаем с небольшим набором данных, в каждом сегменте не будет много элементов, поэтому сортировка вставкой творит для нас чудеса.
4. Посещайте ведра по порядку. После того, как содержимое каждой корзины отсортировано, при объединении они будут давать список, в котором элементы упорядочены в соответствии с вашими критериями.

Давайте посмотрим на визуальное представление того, как работает алгоритм. Например, предположим, что это список ввода:

{.ezlazyload}

Самый большой элемент - 1.2 , а длина списка - 6 . Используя эти два, мы определим оптимальный size каждого ведра. Мы получим это число, разделив самый большой элемент на длину списка. В нашем случае это 1.2/6 что равно 0.2 .

Разделив значение элемента на этот size , мы получим индекс для соответствующей корзины каждого элемента.

Теперь мы создадим пустые ведра. У нас будет столько же корзин, сколько элементов в нашем списке:

{.ezlazyload}

Мы вставим элементы в соответствующие корзины. Принимая во внимание первый элемент - 1.2/0.2 = 6 , индекс соответствующего сегмента равен 6 . Если этот результат больше или равен длине списка, мы просто вычтем 1 и он отлично впишется в список. Это происходит только с самым большим числом, поскольку мы получили size , разделив самый большой элемент на длину.

Мы поместим этот элемент в корзину с индексом 5 :

{.ezlazyload}

Точно так же следующий элемент будет проиндексирован как 0.22/0.2 = 1.1 . Поскольку это десятичное число, мы его опустим. Это округляется до 1 , и наш элемент помещается во вторую корзину:

{.ezlazyload}

Этот процесс повторяется до тех пор, пока мы не поместим последний элемент в соответствующее ведро. Наши ведра теперь выглядят примерно так:

{.ezlazyload}

Теперь мы отсортируем содержимое каждой непустой корзины. Мы будем использовать сортировку вставкой, поскольку она не имеет себе равных с такими небольшими списками. После сортировки вставкой сегменты выглядят следующим образом:

{.ezlazyload}

Теперь это просто вопрос обхода непустых сегментов и объединения элементов в список. Они отсортированы и готовы к работе:

{.ezlazyload}

Реализация Bucket Sort в Python

Разобравшись с этим, давайте продолжим и реализуем алгоритм на Python. Начнем с самой функции bucket_sort() :

 def bucket_sort(input_list): 
 # Find maximum value in the list and use length of the list to determine which value in the list goes into which bucket 
 max_value = max(input_list) 
 size = max_value/len(input_list) 
 
 # Create n empty buckets where n is equal to the length of the input list 
 buckets_list= [] 
 for x in range(len(input_list)): 
 buckets_list.append([]) 
 
 # Put list elements into different buckets based on the size 
 for i in range(len(input_list)): 
 j = int (input_list[i] / size) 
 if j != len (input_list): 
 buckets_list[j].append(input_list[i]) 
 else: 
 buckets_list[len(input_list) - 1].append(input_list[i]) 
 
 # Sort elements within the buckets using Insertion Sort 
 for z in range(len(input_list)): 
 insertion_sort(buckets_list[z]) 
 
 # Concatenate buckets with sorted elements into a single list 
 final_output = [] 
 for x in range(len (input_list)): 
 final_output = final_output + buckets_list[x] 
 return final_output 

Реализация довольно проста. Мы рассчитали параметр size Затем мы создали список пустых сегментов и вставленных элементов на основе их значения и size каждого сегмента.

После вставки мы вызываем insertion_sort() для каждого из сегментов:

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

И с этим, давайте заполним список и выполним для него Bucket Sort:

 def main(): 
 input_list = [1.20, 0.22, 0.43, 0.36,0.39,0.27] 
 print('ORIGINAL LIST:') 
 print(input_list) 
 sorted_list = bucket_sort(input_list) 
 print('SORTED LIST:') 
 print(sorted_list) 

Запуск этого кода вернет:

 Original list: [1.2, 0.22, 0.43, 0.36, 0.39, 0.27] 
 Sorted list: [0.22, 0.27, 0.36, 0.39, 0.43, 1.2] 

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

Сложность наихудшего случая

Если коллекция, с которой мы работаем, имеет небольшой диапазон (например, та, что была в нашем примере) - часто бывает много элементов в одной корзине, где много корзин пусто.

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

Поскольку мы используем сортировку вставкой, ее наихудшая сложность проявляется, когда список находится в обратном порядке. Таким образом, сложность наихудшего случая для Bucket Sort также составляет O (n ^2^ ) .

Сложность в лучшем случае

В лучшем случае все элементы уже отсортированы. Кроме того, элементы распределены равномерно. Это означает, что в каждой корзине будет одинаковое количество элементов.

При этом создание ведер займет O (n), а сортировка вставкой займет O (k) , что даст нам сложность O (n + k).

Средняя сложность

Средний случай встречается в подавляющем большинстве реальных коллекций. Когда коллекция, которую мы хотим отсортировать, является случайной . В этом случае Bucket Sort требует O (n) для завершения, что делает ее очень эффективной .

Заключение

Подводя итог, мы начали с ознакомления с тем, что такое Bucket sort, и продолжили обсуждение того, что нам нужно знать, прежде чем мы перейдем к ее реализации на Python. После внедрения мы провели быстрый анализ сложности.