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

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

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

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

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

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

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

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

Ето стъпките за извършване на процеса на сортиране по радикс:

Стъпка 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 е броят на цифрите на най-големия елемент в масива.

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

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

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

Понякога тази база може да бъде по-голяма от размера на масива.

Следователно общата сложност е O(n+b).

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

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

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

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

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

Radix Sort е линейно, когато

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

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

Както видяхме, сложността на сортирането по Radix се основава на размера на думата или числото. Ще има същата сложност за средния и най-добрия случай. И това е O(d*(n+b)). Освен това се различава според техниката на сортиране, която използвате в средата. Например, можете да използвате сортиране с преброяване или бързо сортиране за алгоритъма за междинно сортиране вътре в сортирането по Radix.

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

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

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