Изучите алгоритм сортировки подсчетом с помощью Python.

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

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

Хотя его основным преимуществом является тот факт, что он может выполняться за линейное время (сложность O(N)), сложность этого наилучшего сценария действительно зависит от диапазона значений во входных данных. множество. Его средняя сложность на самом деле составляет O(N+K), где N — количество значений, а K — количество возможных значений — диапазон значений. Его средняя сложность достигается, когда N и K одинаково доминируют. Его худшая сложность становится O(K), когда количество возможных значений K намного превышает количество элементов во входном массиве.

Рассмотрим числовой пример, скажем, arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4] и предположим, что нам нужно отсортировать это в порядке возрастания. Алгоритм достижения этой цели выглядит следующим образом:

  • мы строим выходной массив того же размера, что и входной массив, и инициализируем его элементы равными 0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  • мы определяем максимальный элемент во входном массиве. Этот элемент равен 9;
  • мы инициализируем список счетчиков вхождений размером max_element+1: count=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (10 элементов);
  • мы анализируем входной массив и заполняем массив count. В нашем случае каждый элемент от 0 до 9 повторяется ровно один раз, поэтому мы имеем counts=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
  • мы превращаем этот список подсчета вхождений в своего рода суммы префиксов, которые сообщат для каждого индекса i его правильную позицию в отсортированном массиве. Код, который достигает этого:
for i in range(1, max_element + 1):
    count[i] += count[i - 1]
  • Кстати, следует отметить, что если мы хотим добиться сортировки входного массива по убыванию, мы должны изменить приведенный выше код на:
for i in range(max_element - 1, -1, -1):
    count[i] += count[i + 1]
  • после этой обработки — по возрастанию, то есть — новый массив count выглядит так: count=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  • теперь идет фактическое построение отсортированного списка. Проходя по списку в обратном направлении, мы обрабатываем каждый элемент и уменьшаем его счетчик вхождений:
  1. i=9, count=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; мы устанавливаем output[count[arr[9]]-1] на значение arr[9]. Это означает, что output[4] = 4; мы уменьшаем count[arr[9]] на 1;
  2. i=8, count=[1, 2, 3, 4, 4, 6, 7, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 0, 0, 4, 0, 0, 0, 0, 0]; мы устанавливаем output[count[arr[8]]-1] на значение arr[8]. Это означает, что output[5]=5; мы уменьшаем count[arr[8]] на 1;
  3. i=7, count=[1, 2, 3, 4, 4, 5, 7, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 0, 0, 4, 5, 0, 0, 0, 0]; мы устанавливаем output[count[arr[7]]-1] на значение arr[7]. Это означает, что output[3]=3; мы уменьшаем count[arr[7]] на 1;
  4. i=6, count=[1, 2, 3, 3, 4, 5, 7, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 0, 3, 4, 5, 0, 0, 0, 0]; мы устанавливаем output[count[arr[6]]-1] на значение arr[6]. Это означает, что output[6]=6; мы уменьшаем count[arr[6]] на 1;
  5. i=5, count=[1, 2, 3, 3, 4, 5, 6, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 0, 3, 4, 5, 6, 0, 0, 0]; мы устанавливаем output[count[arr[5]]-1] на значение arr[5]. Это означает, что output[2]=2; мы уменьшаем count[arr[5]] на 1;
  6. i=4, count=[1, 2, 2, 3, 4, 5, 6, 8, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 2, 3, 4, 5, 6, 0, 0, 0]; мы устанавливаем output[count[arr[4]]-1] на значение arr[4]. Это означает, что output[7]=7; мы уменьшаем count[arr[4]] на 1;
  7. i=3, count=[1, 2, 2, 3, 4, 5, 6, 7, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 0, 2, 3, 4, 5, 6, 7, 0, 0]; мы устанавливаем output[count[arr[3]]-1] на значение arr[3]. Это означает, что output[1]=1; мы уменьшаем count[arr[3]] на 1;
  8. i=2, count=[1, 1, 2, 3, 4, 5, 6, 7, 9, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 1, 2, 3, 4, 5, 6, 7, 0, 0]; мы устанавливаем output[count[arr[2]]-1] на значение arr[2]. Это означает, что output[8]=8; мы уменьшаем count[arr[2]] на 1;
  9. i=1, count=[1, 1, 2, 3, 4, 5, 6, 7, 8, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]; мы устанавливаем output[count[arr[1]]-1] на значение arr[1]. Это означает, что output[0]=0; мы уменьшаем count[arr[1]] на 1;
  10. i=0, count=[0, 1, 2, 3, 4, 5, 6, 7, 8, 10], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4 ]; вывод=[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]; мы устанавливаем output[count[arr[0]]-1] на значение arr[0]. Это означает, что output[9]=9; мы уменьшаем count[arr[9]] на 1;
  11. count=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], arr=[9, 0, 8, 1, 7, 2, 6, 3, 5, 4]; вывод теперь [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. Это массив, который мы собираемся вернуть.

Полная реализация Python ниже:

def counting_sort(arr):
    """Main algorithm function."""
    # variable initialization and setup
    arr_length = len(arr)
    output = [0] * arr_length
    max_element = max(arr)
    count = [0] * (max_element + 1)
    # build occurrences list
    for i in range(arr_length):
        count[arr[i]] += 1
    # transform occurrences list into positions list
    for i in range(1, max_element + 1):
        count[i] += count[i - 1]
    # build output list
    for i in range(arr_length - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output

И это в основном все, что касается темы сортировки подсчетом. Я настоятельно рекомендую вам пойти туда и найти больше информации об этом, чтобы еще больше расширить свои знания по этому вопросу, но что я настоятельно рекомендую, если вы действительно хотите получить как можно больше от этой статьи, это попытаться переделывайте алгоритм шаг за шагом, уделяя столько времени, сколько вам нужно, чтобы понять его. Я считаю, что такого в последнее время в нашей жизни не так много. Мы не даем себе столько времени и терпения, чтобы расти, как раньше, упуская свой потенциал как личности. Но если мы не собираемся давать себе немного времени на переваривание вещей, я подозреваю, что никто другой не сделает это за нас.

Если оставить в стороне глубокие размышления о состоянии человека, я желаю всем вам оставаться в безопасности и счастливого кодирования! До скорого!

Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Получите эксклюзивный доступ к возможностям написания и советам в нашем сообществе Discord.