Автор оригинала: Muhammad Junaid Khalid.

Сортировка ведра в Python

Вступление

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

Сортировка по ведрам-это алгоритм сравнения , который присваивает элементы списка, которые мы хотим отсортировать в Ведрах или Бункерах . Содержимое этих ведер затем сортируется, как правило, с помощью другого алгоритма. После сортировки содержимое ведер добавляется, образуя отсортированную коллекцию.

Сортировку по ведрам можно рассматривать как подход scatter-order-gather к сортировке списка из-за того, что элементы сначала разбросаны в ведрах, упорядочены внутри них и, наконец, собраны в новый, отсортированный список.

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

Как работает Сортировка по Ведрам?

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

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

Посетите ведра по порядку. Как только содержимое каждого ведра будет отсортировано, при объединении они дадут список, в котором элементы будут расположены на основе ваших критериев.

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

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

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

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

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

Аналогично, следующий элемент будет проиндексирован на 0.22/0.2.1 . Так как это десятичное число, то мы его наполним. Это округляется до 1 , и наш элемент помещается во второе ведро:

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

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

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

Реализация сортировки ведра в 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 . Затем мы создали экземпляр списка пустых ведер и вставили элементы на основе их значения и размера каждого ведра.

После вставки мы вызываем 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

И с этим на месте давайте заполним список и выполним сортировку по ведру:

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]

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

Наихудшая сложность

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

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

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

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

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

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

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

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

Вывод

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