Algorytm sortowania radiacyjnego w strukturze danych

Co to jest algorytm sortowania radiacyjnego?

Sortowanie radiksowe to algorytm sortowania nieporównawczego. Działa poprzez grupowanieping Poszczególne cyfry elementów, które mają zostać posortowane. Następnie stosuje się stabilną technikę sortowania, aby uporządkować elementy na podstawie ich podstawy. Jest to liniowy algorytm sortowania.

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.
• Grouping Proces 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.