Algorytm sortowania radiacyjnego w strukturze danych

Co to jest algorytm sortowania radiacyjnego?

Sortowanie Radix to algorytm sortowania nieporównawczego. Działa poprzez grupowanie poszczególnych cyfr elementów przeznaczonych do sortowania. Następnie stosuje się stabilną technikę sortowania w celu uporządkowania elementów na podstawie ich podstawy. Jest to algorytm sortowania liniowego.

Proces sortowania obejmuje następujące właściwości:

• Znalezienie elementu maksymalnego i uzyskanie liczby cyfr tego elementu. Daje nam to liczbę iteracji, po których nastąpi proces sortowania.
• Grupuj poszczególne cyfry elementów na tej samej znaczącej pozycji w każdej iteracji.
• Proces grupowania rozpocznie się od cyfry najmniej znaczącej i zakończy na cyfrze najbardziej znaczącej.
• Sortowanie elementów na podstawie cyfr w tej znaczącej pozycji.
• Utrzymywanie względnej kolejności elementów mających tę samą wartość klucza. Ta właściwość sortowania radix sprawia, że ​​jest to sortowanie stabilne.

Ostatnia iteracja da nam całkowicie posortowaną listę.

Działanie algorytmu sortowania Radix

Spróbujmy posortować listę liczb całkowitych na powyższym rysunku w kolejności rosnącej, korzystając z algorytmu Radix Sort.

Oto kroki, aby przeprowadzić proces sortowania Radix:

Krok 1) Zidentyfikuj element o maksymalnej wartości na liście. W tym przypadku jest to 835.

Krok 2) Oblicz liczbę cyfr elementu maksymalnego. Liczba 835 ma dokładnie 3 cyfry.

Krok 3) Określ liczbę iteracji na podstawie kroku 2. 835 ma 3 cyfry, co oznacza, że ​​liczba iteracji wyniesie 3.

Krok 4) Określ podstawę elementów. Ponieważ jest to system dziesiętny, podstawą będzie 10.

Krok 5) Rozpocznij pierwszą iterację.

a) Pierwsza iteracja

W pierwszej iteracji rozważamy jednostkową wartość miejsca każdego elementu.

Krok 1) Zmodyfikuj liczbę całkowitą o 10, aby uzyskać miejsce jednostkowe elementów. Na przykład 623 mod 10 daje nam wartość 3, a 248 mod 10 daje nam 8.

Krok 2) Użyj sortowania zliczającego lub innego stabilnego sortowania, aby uporządkować liczby całkowite według ich najmniej znaczącej cyfry. Jak widać z rysunku, 248 spadnie na ósme wiadro. 8 spadnie na trzecie wiadro i tak dalej.

Po pierwszej iteracji lista wygląda teraz tak.

Jak widać na powyższym rysunku, lista nie jest jeszcze posortowana i wymaga dalszych iteracji, aby została w pełni posortowana.

b) Druga iteracja

W tej iteracji rozważymy cyfrę 10^th miejsce procesu sortowania.

Krok 1) Podziel liczby całkowite przez 10. 248 podzielone przez 10 daje nam 24.

Krok 2) Zmodyfikuj wyjście kroku 1 na 10. 24 mod 10 daje nam 4.

Krok 3) Wykonaj krok 2 z poprzedniej iteracji.

Po drugiej iteracji lista wygląda teraz tak

Z powyższego rysunku widać, że lista nadal nie jest całkowicie posortowana, ponieważ nie jest jeszcze ułożona w porządku rosnącym.

c) Trzecia iteracja

W ostatniej iteracji chcemy uzyskać najbardziej znaczącą cyfrę. W tym przypadku jest to 100^th miejsce dla każdej liczby całkowitej na liście.

Krok 1) Podziel liczby całkowite przez 100… 415 podzielone przez 100 daje nam 4.

Krok 2) Zmodyfikuj wynik z kroku 1 na 10. 4 mod 10 daje nam ponownie 4.

Krok 3) Wykonaj krok 3 z poprzedniej iteracji.

Jak widzimy, lista jest teraz posortowana rosnąco. Ostatnia iteracja została zakończona i proces sortowania został zakończony.

Pseudokod algorytmu sortowania radiacyjnego

Oto pseudokod algorytmu sortowania 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 of the elements in the jthplace
   arr = sorted elements

C++ Program do implementacji sortowania radiacyjnego

#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);
}

Wyjście:

162 248 415 623 835

Python Program do algorytmu sortowania 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)

Wyjście:

[162,248,415,623,835]

Analiza złożoności sortowania radiksowego

Należy wziąć pod uwagę dwa typy złożoności: złożoność przestrzenną i złożoność czasową.

• Złożoność przestrzenna: O(n+b), gdzie n jest rozmiarem tablicy, a b jest rozpatrywaną bazą.
• Złożoność czasowa: O(d*(n+b)), gdzie d jest liczbą cyfr największego elementu w tablicy.

Złożoność przestrzenna sortowania radiksowego

Dwie funkcje, na których należy się skupić w kontekście złożoności przestrzeni

• Liczba elementów w tablicy, n.
• Baza do reprezentacji elementów, b.

Czasami ta podstawa może być większa niż rozmiar tablicy.

Całkowita złożoność wynosi zatem O(n+b).

Następujące właściwości elementów listy mogą sprawić, że sortowanie radiksowe będzie nieefektywne:

• Elementy z dużą liczbą cyfr.
• Podstawa elementów jest duża, jak liczby 64-bitowe.

Złożoność czasowa sortowania radiksowego

Możesz użyć sortowania przez zliczanie jako podprogramu, ponieważ będzie trwała każda iteracjami O(n+b) czas. Jeśli istnieją różnice, całkowity czas działania wynosi O(d*(n+b)). Tutaj „O” oznacza funkcję złożoności.

Liniowość sortowania radiacyjnego

Sortowanie radiacyjne jest liniowe, gdy

• d jest stała, gdzie d jest liczbą cyfr największego elementu.
• b nie jest w dużym stopniu większy w porównaniu do n.

Porównanie sortowania radiksowego z innymi algorytmami porównawczymi

Jak widzieliśmy, złożoność sortowania Radix opiera się na rozmiarze słowa lub liczby. Będzie miała taką samą złożoność dla przeciętnego i najlepszego przypadku. I to jest O(d*(n+b)). Ponadto różni się w zależności od techniki sortowania, której używasz w środku. Na przykład możesz użyć sortowania zliczającego lub szybkiego sortowania dla pośredniego algorytmu sortowania wewnątrz sortowania Radix.

Zastosowania algorytmu sortowania Radix

Ważne zastosowania sortowania radiacyjnego to:

• Sortowanie Radix może być używane jako algorytm wyszukiwania lokalizacji, gdy używane są duże zakresy wartości.
• Służy do konstruowania tablicy sufiksów w algorytmie DC3.
• Używa się go w sekwencyjnych maszynach o swobodnym dostępie, obecnych w typowym komputerze, w których rekordy są wprowadzane za pomocą kluczy.