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:

• Finding the maximum element and getting the number of digits of that element. This gives the number of iterations the sorting process performs.
• Grouping the individual digits of the elements at the same significant position in each iteration.
• The grouping process starts from the least significant digit and ends at the most significant digit.
• Sorting the elements based on the digits at that significant position.
• Maintaining the relative order of elements that have the same key value. This property of Radix Sort makes it a stable sort.

The final iteration returns a completely sorted list.

Działanie algorytmu sortowania Radix

Lista liczb całkowitych do posortowania

Let us sort the list of integers in the above figure in ascending order using Radix Sort.

Here are the steps to perform the Radix Sort process:

Krok 1) Identify the maximum element in the list. Here it is 835.

Krok 2) Count its digits. 835 has 3 digits, so the number of iterations is 3.

Krok 3) Determine the base. Since this is decimal, the base is 10.

Krok 4) Rozpocznij pierwszą iterację.

a) Pierwsza iteracja

Sortowanie według ostatniej cyfry

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

Krok 1) Mod the integer by 10 to get the unit place of the elements. For example, 623 mod 10 gives 3, and 248 mod 10 gives 8.

Krok 2) Use counting sort or another stable sort to organize the integers according to their least significant digit. From the figure, 248 falls into the 8th bucket, 623 falls into the 3rd bucket, and so on.

Po pierwszej iteracji lista wygląda teraz tak.

Lista po pierwszej iteracji

The list is not sorted yet and requires more iterations.

b) Druga iteracja

Sortowanie na podstawie cyfr na miejscu dziesiątek

In this iteration, we consider the digit in the tens place for the sorting process.

Krok 1) Divide the integers by 10. For example, 248 divided by 10 gives 24.

Krok 2) Mod the output of Step 1 by 10. 24 mod 10 gives 4.

Krok 3) Follow Step 2 from the previous iteration.

After the second iteration, the list now looks like this:

Lista po drugiej iteracji

The list is still not sorted completely as it is not in ascending order yet.

c) Trzecia iteracja

Sorting based on the digits at hundreds place

For the final iteration, we want to get the most significant digit. In this case, it is the hundreds place for each of the integers in the list.

Krok 1) Divide the integers by 100. For example, 415 divided by 100 gives 4.

Krok 2) Mod the result from Step 1 by 10. 4 mod 10 gives 4.

Krok 3) Follow Step 3 from the previous iteration.

Lista po trzeciej iteracji

The list is now sorted in ascending order. The final iteration has been completed, and the sorting process is finished.

Pseudokod algorytmu sortowania radiacyjnego

Here is the pseudocode for the Radix Sort Algorithm:

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

Wyjście:

162 248 415 623 835

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

Wyjście:

[162, 248, 415, 623, 835]

Complexity Analysis of Radix Sort

There are two types of complexity to consider: space complexity and time complexity.

• Złożoność kosmiczna: O(n + b) where n is the size of the array and b is the base considered.
• Złożoność czasowa: O(d * (n + b)) where d is the number of digits of the largest element in the array.

Złożoność przestrzenna sortowania radiksowego

Two features to focus on for space complexity:

• Liczba elementów w tablicy, n.
• The base used to represent the elements, b.

Sometimes this base can be greater than the size of the array. The overall complexity is thus O(n + b).

The following properties of the elements in the list can make Radix Sort space inefficient:

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

Złożoność czasowa sortowania radiksowego

Using counting sort as a subroutine, each iteration takes O(n + b) czas. Jeśli istnieją różnice, całkowity czas działania wynosi O(d * (n + b)). Here, “O” denotes the complexity function.

Liniowość sortowania radiacyjnego

Radix Sort is linear when:

• d jest stała, gdzie d jest liczbą cyfr największego elementu.
• b is not significantly larger than n.

Comparison of Radix Sort with Other Sorting Algorithms

Radix Sort’s complexity depends on the number size. Best-case and average-case are both O(d * (n + b)). Performance varies with the inner sort — counting sort is standard, but any stable sort works.

Zastosowania algorytmu sortowania Radix

Important applications of Radix Sort are:

• Radix Sort can be used as a location-finding algorithm where large ranges of values are involved.
• It is used to construct a suffix array in the DC3 algorithm.
• It is used in sequential, random-access machines where records are keyed by fixed-width identifiers.

FAQ