Алгоритъм за сортиране по Radix в структурата на данните

Какво представлява алгоритъмът за сортиране по Radix?

Radix Sort е несравнителен алгоритъм за сортиране. Той работи по групов принцип.ping отделните цифри на елементите, които ще бъдат сортирани. След това се използва стабилна техника за сортиране, за да се организират елементите въз основа на тяхната систематична система. Това е линеен алгоритъм за сортиране.

Процесът на сортиране включва следните свойства:

• Намиране на максималния елемент и получаване на броя цифри на този елемент. Това дава броя итерации, които процесът на сортиране извършва.
• Grouping отделните цифри на елементите на една и съща значима позиция във всяка итерация.
• Групатаping Процесът започва от най-малко значимата цифра и завършва с най-значимата цифра.
• Сортиране на елементите въз основа на цифрите на тази значима позиция.
• Поддържане на относителния ред на елементите, които имат една и съща ключова стойност. Това свойство на Radix Sort го прави стабилно сортиране.

Последната итерация връща напълно сортиран списък.

Работа на алгоритъма за сортиране Radix

Списък с цели числа за сортиране

Нека сортираме списъка с цели числа на горната фигура във възходящ ред, използвайки Radix Sort.

Ето стъпките за извършване на процеса на сортиране по 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]

Анализ на сложността на Radix Sort

Има два вида сложност, които трябва да се вземат предвид: пространствена сложност и времева сложност.

• Сложност на пространството: O(n + b), където n е размерът на масива, а b е разглежданата база.
• Времева сложност: O(d * (n + b)), където d е броят на цифрите на най-големия елемент в масива.

Пространствена сложност на Radix Sort

Две характеристики, върху които да се съсредоточим, за да определим пространствената сложност:

• Брой елементи в масива, n.
• Основата, използвана за представяне на елементите, b.

Понякога тази база може да бъде по-голяма от размера на масива. Следователно общата сложност е O(n + b).

Следните свойства на елементите в списъка могат да направят Radix Sort пространството неефективно:

• Елементи с голям брой цифри.
• Базата от елементи е голяма, като 64-битови числа.

Времева сложност на Radix сортиране

Използвайки сортиране с броене като подпрограма, всяка итерация отнема O(n + b) време. Ако има д итерации, общото време на работа става O(d * (n + b))Тук „O“ означава функцията на сложност.

Линейност на Radix сортиране

Radix сортирането е линейно, когато:

• d е константа, където d е броят на цифрите на най-големия елемент.
• b не е значително по-голям от n.

Сравнение на Radix сортиране с други видове сортиране Algorithms

Сложността на Radix Sort зависи от размера на числото. Най-добрият и средният случай са O(d * (n + b)). Производителността варира в зависимост от вътрешното сортиране — сортирането с броене е стандартно, но всяко стабилно сортиране работи.

Приложения на алгоритъма за сортиране Radix

Важни приложения на Radix Sort са:

• Radix Sort може да се използва като алгоритъм за намиране на местоположение, когато са включени големи диапазони от стойности.
• Използва се за изграждане на суфиксен масив в алгоритъма DC3.
• Използва се в последователни машини с произволен достъп, където записите се ключове с идентификатори с фиксирана ширина.

Въпроси и Отговори