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

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

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

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

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

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

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

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

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

Крок 1) Визначте елемент із максимальним значенням у списку. У цьому випадку це 835.

Крок 2) Обчислити кількість цифр максимального елемента. 835 має рівно 3 цифри.

Крок 3) Визначте кількість ітерацій на основі кроку 2. 835 має 3 цифри, тобто кількість ітерацій буде 3.

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

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

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

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

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

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

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

Як ви можете бачити з наведеного вище малюнка, список ще не відсортовано, і для його повного сортування потрібні додаткові ітерації.

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

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

Крок 1) Розділіть цілі числа на 10. 248 поділити на 10 дає нам 24.

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

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

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

Ви можете побачити на наведеному вище малюнку, що список ще не відсортовано повністю, оскільки він ще не в порядку зростання.

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

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

Крок 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 j^th 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 of the elements in the j^thplace
   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 integers
  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 using 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


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

вихід:

[162,248,415,623,835]

Аналіз складності Radix Sort

Є два типи складності, які слід враховувати, просторову складність і часову складність.

Просторова складність: O(n+b), де n — розмір масиву, а b — розглянута база.
Часова складність: O(d*(n+b)), де d – кількість цифр найбільшого елемента в масиві.

Просторова складність сортування за коренем

Дві функції, на які варто зосередитися для збільшення простору

Кількість елементів у масиві, n.
Основа для представлення елементів, b.

Іноді ця база може перевищувати розмір масиву.

Таким чином, загальна складність дорівнює O(n+b).

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

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

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

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

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

Radix Sort є лінійним, коли

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

Порівняння Radix Sort з іншими порівняльними алгоритмами

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

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

Важливими застосуваннями Radix Sort є:

Radix Sort можна використовувати як алгоритм пошуку розташування, де використовуються великі діапазони значень.
Він використовується для побудови суфіксного масиву в алгоритмі DC3.
Він використовується в послідовній машині з довільним доступом, наявній у типовому комп’ютері, де записи вводяться ключами.

Вам може сподобатися: