Алгоритм поразрядной сортировки в структуре данных

Что такое алгоритм поразрядной сортировки?

Сортировка по разрядам (Radix Sort) — это некомпаративный алгоритм сортировки. Он работает путем группировки.ping Отдельные цифры элементов, подлежащих сортировке. Затем используется устойчивый метод сортировки для организации элементов на основе их основания. Это линейный алгоритм сортировки.

Процесс сортировки включает в себя следующие свойства:

• Нахождение максимального элемента и вычисление количества цифр этого элемента. Это позволяет определить количество итераций, выполняемых процессом сортировки.
• Grouping отдельные цифры элементов, находящиеся на одной и той же значимой позиции в каждой итерации.
• Группаping Процесс начинается с младшего разряда и заканчивается старшим разрядом.
• Сортировка элементов на основе цифр, находящихся на соответствующей значащей позиции.
• Сохранение относительного порядка элементов с одинаковым значением ключа. Это свойство сортировки по разрядам делает её стабильной сортировкой.

В результате последней итерации возвращается полностью отсортированный список.

Работа алгоритма поразрядной сортировки

Список целых чисел для сортировки

Отсортируем список целых чисел на рисунке выше в порядке возрастания, используя поразрядную сортировку.

Вот шаги для выполнения сортировки по разрядам:

Шаг 1) Определите максимальный элемент в списке. В данном случае это 835.

Шаг 2) Посчитайте его цифры. У числа 835 3 цифры, поэтому количество итераций равно 3.

Шаг 3) Определите основание. Поскольку это десятичная дробь, основание равно 10.

Шаг 4) Запустите первую итерацию.

а) Первая итерация

Сортировка по последней цифре

На первой итерации мы рассматриваем единичное значение каждого элемента.

Шаг 1) Чтобы получить разрядность элементов, нужно взять остаток от деления целого числа на 10. Например, 623 по модулю 10 дает 3, а 248 по модулю 10 дает 8.

Шаг 2) Используйте сортировку подсчетом или другой стабильный метод сортировки, чтобы упорядочить целые числа по их младшему разряду. Из рисунка видно, что число 248 попадает в 8-ю группу, 623 — в 3-ю и так далее.

После первой итерации список теперь выглядит так.

Список после первой итерации

Список еще не отсортирован и требует дополнительных итераций.

б) Вторая итерация

Сортировка по цифрам в десятках

В этом варианте мы рассматриваем цифру в разряде десятков для процесса сортировки.

Шаг 1) Разделите целые числа на 10. Например, 248, разделенное на 10, дает 24.

Шаг 2) Умножьте результат шага 1 на 10. 24 по модулю 10 дает 4.

Шаг 3) Выполните шаг 2 из предыдущей итерации.

После второй итерации список теперь выглядит так:

Список после второй итерации

Список еще не полностью отсортирован, так как он еще не упорядочен по возрастанию.

в) Третья итерация

Сортировка по цифрам в разряде сотен.

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

Шаг 1) Разделите целые числа на 100. Например, 415, разделенное на 100, дает 4.

Шаг 2) Умножьте результат из шага 1 на 10. 4 по модулю 10 дает 4.

Шаг 3) Выполните шаг 3 из предыдущей итерации.

Список после третьей итерации

Список отсортирован в порядке возрастания. Заключительная итерация завершена, и процесс сортировки окончен.

Псевдокод алгоритма поразрядной сортировки

Вот псевдокод алгоритма сортировки по разрядам:

radixSortAlgo(arr as an array)
    Find the largest element in arr
    maximum = the element in arr that is the largest
    Find the number of digits in maximum
    k = the number of digits in maximum
    Create buckets of size 0-9 k times
    for j -> 0 to k
        Acquire the jth place of each element in arr. Here j = 0 represents the least significant digit.
        Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits in the jth place
    arr = sorted elements

C++ Программа для реализации поразрядной сортировки

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
    int maximum = arr[0];
    for (int i = 1; i < n; i++) {
        if (maximum < arr[i]) maximum = arr[i];
    }
    return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
    const int limit = 10;
    int result[size];
    int count[limit] = {0};
    // Calculating the count of each integer
    for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
    // Calculating the cumulative count
    for (int j = 1; j < limit; j++) {
        count[j] += count[j - 1];
    }
    // Sort the integers
    for (int j = size - 1; j >= 0; j--) {
        result[count[(arr[j] / position) % 10] - 1] = arr[j];
        count[(arr[j] / position) % 10]--;
    }
    for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
    // Get the largest element in the array
    int maximum = getMaximum(arr, size);
    for (int position = 1; maximum / position > 0; position *= 10)
        countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {162, 623, 835, 415, 248};
    int size = sizeof(arr) / sizeof(arr[0]);
    radixSortAlgo(arr, size);
    printResult(arr, size);
}

Выход:

162 248 415 623 835

Python Программа для алгоритма поразрядной сортировки

# Radix Sort in Python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10
    # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1
    # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]
    # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]

def radixSortAlgo(arr):
    # Acquiring the largest element in the array
    maximum = max(arr)
    # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

Выход:

[162, 248, 415, 623, 835]

Анализ сложности сортировки по разрядам

Следует учитывать два типа сложности: пространственную сложность и временную сложность.

• Пространственная сложность: O(n + b), где n — размер массива, а b — рассматриваемое основание.
• Временная сложность: O(d * (n + b)), где d — количество цифр наибольшего элемента в массиве.

Пространственная сложность поразрядной сортировки

При оценке пространственной сложности следует обратить внимание на две особенности:

• Количество элементов в массиве, n.
• Основание, используемое для представления элементов, b.

Иногда это основание может быть больше размера массива. Таким образом, общая сложность составляет O(n + b).

Следующие свойства элементов списка могут привести к неэффективному использованию пространства при сортировке по разрядам:

• Элементы с большим количеством цифр.
• База элементов большая, как 64-битные числа.

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

При использовании сортировки подсчетом в качестве подпрограммы каждая итерация занимает O(n + b) время. Если существует d итераций, общее время выполнения становится O(d * (n + b))Здесь «O» обозначает функцию сложности.

Линейность поразрядной сортировки

Сортировка по разрядам является линейной, когда:

• d является константой, где d — количество цифр наибольшего элемента.
• b не значительно больше, чем n.

Сравнение поразрядной сортировки с другими методами сортировки Algorithms

Сложность сортировки по разрядам зависит от размера числа. В лучшем и среднем случаях она составляет O(d * (n + b)). Производительность варьируется в зависимости от внутренней сортировки — стандартной является сортировка подсчетом, но подойдет любая стабильная сортировка.

Применение алгоритма поразрядной сортировки

Важные области применения сортировки по разрядам:

• Сортировка по разрядам может использоваться в качестве алгоритма поиска местоположения, когда речь идёт о больших диапазонах значений.
• Он используется для построения суффиксного массива в алгоритме DC3.
• Он используется в последовательных машинах с произвольным доступом, где записи индексируются идентификаторами фиксированной ширины.

Часто задаваемые вопросы (FAQ)