Алгоритм радикального сортування в структурі даних

Що таке алгоритм сортування Radix?

Radix Sort — це непорівняльний алгоритм сортування. Він працює за груповим принципом.ping окремі цифри елементів, що підлягають сортуванню. Потім для впорядкування елементів на основі їхньої основи числення використовується метод стабільного сортування. Це лінійний алгоритм сортування.

Процес сортування включає такі властивості:

• Знаходження максимального елемента та отримання кількості цифр цього елемента. Це дає кількість ітерацій, які виконує процес сортування.
• Гроуping окремі цифри елементів на одній і тій самій значущій позиції в кожній ітерації.
• Групаping Процес починається з найменш значущої цифри та закінчується на найстаршій.
• Сортування елементів на основі цифр у цій значущій позиції.
• Збереження відносного порядку елементів, які мають однакове значення ключа. Ця властивість сортування за радісом робить його стабільним сортуванням.

Остання ітерація повертає повністю відсортований список.

Робота алгоритму сортування Radix

Список цілих чисел для сортування

Давайте відсортуємо список цілих чисел на рисунку вище у порядку зростання, використовуючи сортування за даними Radix.

Ось кроки для виконання процесу сортування за радісом:

Крок 1) Визначте максимальний елемент у списку. Ось це 835.

Крок 2) Порахуйте його цифри. Число 835 має 3 цифри, тому кількість ітерацій дорівнює 3.

Крок 3) Визначте основу. Оскільки це десяткове число, то основа дорівнює 10.

Крок 4) Почніть першу ітерацію.

а) Перша ітерація

Сортування за останньою цифрою

У першій ітерації ми розглядаємо одиничне розрядне значення кожного елемента.

Крок 1) Модифікуйте ціле число на 10, щоб отримати розряд одиниць елементів. Наприклад, 623 mod 10 дає 3, а 248 mod 10 дає 8.

Крок 2) Використайте сортування підрахунком або інше стабільне сортування, щоб упорядкувати цілі числа за їх найменшою значущою цифрою. Згідно з рисунком, 248 потрапляє до 8-го корита, 623 потрапляє до 3-го корита тощо.

Після першої ітерації список тепер виглядає так.

Список після першої ітерації

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

б) Друга ітерація

Сортування на основі розряду десятків

У цій ітерації ми розглядаємо цифру в розряді десятків для процесу сортування.

Крок 1) Поділіть цілі числа на 10. Наприклад, 248 поділено на 10 дає 24.

Крок 2) Вивід кроку 1 модифікуємо на 10. 24 mod 10 дає 4.

Крок 3) Виконайте крок 2 з попередньої ітерації.

Після другої ітерації список тепер виглядає так:

Список після другої ітерації

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

в) Третя ітерація

Сортування на основі цифр у розряді сотень

Для останньої ітерації нам потрібно отримати найстаршу цифру. У цьому випадку це розряд сотень для кожного цілого числа у списку.

Крок 1) Поділіть цілі числа на 100. Наприклад, 415 поділено на 100 дає 4.

Крок 2) Результат з кроку 1 модифікуємо на 10. 4 mod 10 дає 4.

Крок 3) Виконайте крок 3 з попередньої ітерації.

Список після третьої ітерації

Список тепер відсортовано у порядку зростання. Фінальна ітерація завершена, і процес сортування завершено.

Псевдокод алгоритму сортування Radix

Ось псевдокод алгоритму сортування Radix:

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++ Програма для впровадження Radix Sort

#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

# 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).

Наступні властивості елементів у списку можуть зробити простір сортування Radix неефективним:

• Елементи з великою кількістю цифр.
• База елементів велика, як 64-розрядні числа.

Часова складність сортування за принципом

Використовуючи сортування підрахунком як підпрограму, кожна ітерація виконує O(n + b) час. Якщо існує d ітерацій, загальний час роботи стає O(d * (n + b))Тут «O» позначає функцію складності.

Лінійність Radix Sort

Сортування по радиксу є лінійним, коли:

• d постійна, де d кількість цифр найбільшого елемента.
• b не є значно більшим за n.

Порівняння сортування за радісом з іншими видами сортування Algorithms

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

Застосування алгоритму сортування Radix

Важливими застосуваннями сортування за радісом є:

• Радиксну сортування можна використовувати як алгоритм пошуку місцезнаходження, коли задіяні великі діапазони значень.
• Він використовується для побудови масиву суфіксів в алгоритмі DC3.
• Він використовується в послідовних машинах з довільним доступом, де записи мають ключі за допомогою ідентифікаторів фіксованої ширини.

Поширені запитання