Radix-sorteeralgoritme in gegevensstructuur

Wat is het Radix sorteeralgoritme?

Radix Sort is een niet-vergelijkend sorteeralgoritme. Het werkt door de afzonderlijke cijfers van de te sorteren elementen te groeperen. Vervolgens wordt een stabiele sorteertechniek gebruikt om de elementen te ordenen op basis van hun radix. Het is een lineair sorteeralgoritme.

Het sorteerproces omvat de volgende eigenschappen:

Het maximale element vinden en het aantal cijfers van dat element verkrijgen. Het geeft ons het aantal iteraties dat het sorteerproces zal volgen.
Groepeer de individuele cijfers van de elementen op dezelfde significante positie in elke iteratie.
Het groeperingsproces begint bij het minst significante cijfer en eindigt bij het meest significante cijfer.
De elementen sorteren op basis van cijfers op die significante positie.
Het behouden van de relatieve volgorde van elementen die dezelfde sleutelwaarde hebben. Deze eigenschap van de radix-soort maakt het een stabiele sortering.

De laatste iteratie geeft ons een volledig gesorteerde lijst.

Werking van het Radix Sort-algoritme

Laten we proberen de lijst met gehele getallen in de bovenstaande afbeelding in oplopende volgorde te sorteren met behulp van het Radix Sort-algoritme.

Hier zijn de stappen om het Radix-sorteerproces uit te voeren:

Stap 1) Identificeer het element met de maximale waarde in de lijst. In dit geval is dat 835.

Stap 2) Bereken het aantal cijfers van het maximale element. 835 heeft precies 3 cijfers.

Stap 3) Bepaal het aantal iteraties op basis van stap 2. 835 heeft 3 cijfers, wat betekent dat het aantal iteraties 3 zal zijn.

Stap 4) Bepaal de basis van de elementen. Omdat dit een decimaal systeem is, is de grondtal 10.

Stap 5) Start de eerste iteratie.

a) Eerste iteratie

In de eerste iteratie houden we rekening met de eenheidswaarde van elk element.

Stap 1) Wijzig het gehele getal met 10 om de eenheidsplaats van de elementen te krijgen. 623 mod 10 geeft ons bijvoorbeeld de waarde 3, en 248 mod 10 geeft ons 8.

Stap 2) Gebruik telsortering of een andere stabiele sortering om de gehele getallen te ordenen op basis van hun minst significante cijfer. Zoals uit de figuur blijkt, zal 248 op de 8e emmer vallen. 623 zal op de derde emmer vallen, enzovoort.

Na de eerste iteratie ziet de lijst er nu als volgt uit.

Zoals u in de bovenstaande afbeelding kunt zien, is de lijst nog niet gesorteerd en is er meer iteratie nodig om volledig te kunnen worden gesorteerd.

b) Tweede iteratie

In deze iteratie beschouwen we het cijfer bij de 10^th plaats voor het sorteerproces.

Stap 1) Deel de gehele getallen door 10. 248 gedeeld door 10 geeft ons 24.

Stap 2) Mod de uitvoer van stap 1 bij 10. 24 mod 10 geeft ons 4.

Stap 3) Volg stap 2 van de vorige iteratie.

Na de tweede iteratie ziet de lijst er nu als volgt uit

U kunt aan de bovenstaande figuur zien dat de lijst nog steeds niet volledig is gesorteerd, aangezien deze nog niet in oplopende volgorde staat.

c) Derde iteratie

Voor de laatste iteratie willen we het meest significante cijfer verkrijgen. In dit geval is dat de 100^thplaats voor elk van de gehele getallen in de lijst.

Stap 1) Deel de gehele getallen door 100... 415 gedeeld door 100 geeft ons 4.

Stap 2) Mod het resultaat van stap 1 bij 10. 4 mod 10 geeft ons weer 4.

Stap 3) Volg stap 3 van de vorige iteratie.

Zoals we kunnen zien, is de lijst nu in oplopende volgorde gesorteerd. De laatste iteratie is voltooid en het sorteerproces is nu voltooid.

Pseudocode van Radix Sorteeralgoritme

Hier is de pseudocode voor het Radix Sort-algoritme

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++ Programma om Radix Sort te implementeren

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

Output:

162 248 415 623 835

Python Programma voor Radix Sorteeralgoritme

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

Output:

[162,248,415,623,835]

Complexiteitsanalyse van Radix Sort

Er zijn twee soorten complexiteit: ruimtelijke complexiteit en tijdscomplexiteit.

Ruimtecomplexiteit: O(n+b) waarbij n de grootte van de matrix is en b de beschouwde basis.
Tijdcomplexiteit: O(d*(n+b)) waarbij d het aantal cijfers is van het grootste element in de matrix.

Ruimtecomplexiteit van radixsortering

Twee kenmerken waarop u zich moet concentreren voor ruimtelijke complexiteit

Aantal elementen in de array, n.
De basis voor het weergeven van de elementen, b.

Soms kan deze basis groter zijn dan de grootte van de array.

De totale complexiteit is dus O(n+b).

De volgende eigenschappen van de elementen in de lijst kunnen de radixsorteerruimte inefficiënt maken:

Elementen met een groot aantal cijfers.
De basis van de elementen is groot, zoals 64-bits getallen.

Tijdcomplexiteit van radixsortering

U kunt het tellen als een subroutine gebruiken, aangezien elke iteratie zal dureneO(n+b) tijd. Als er iteraties bestaan, wordt de totale looptijd O(d*(n+b)). Hierbij staat “O” voor de complexiteitsfunctie.

Lineariteit van Radix-sortering

Radix Sortering is lineair wanneer

d is constant, waarbij d het aantal cijfers van het grootste element is.
b is niet veel groter dan n.

Vergelijkingen van Radix Sort met andere vergelijkende algoritmen

Zoals we hebben gezien, is de complexiteit van de Radix sort gebaseerd op een woord- of nummergrootte. Het zal dezelfde complexiteit hebben voor de gemiddelde en beste gevallen. En dat is O(d*(n+b)). Het verschilt ook afhankelijk van de sorteertechniek die u in het midden gebruikt. U kunt bijvoorbeeld counting sort of quick sort gebruiken voor het tussenliggende sorteeralgoritme binnen de Radix sort.

Toepassingen van het Radix Sort-algoritme

Belangrijke toepassingen van Radix Sort zijn:

Radix Sort kan worden gebruikt als algoritme voor het vinden van locaties waarbij grote waardenbereiken worden gebruikt.
Het wordt gebruikt bij het construeren van een achtervoegselarray in het DC3-algoritme.
Het wordt gebruikt in een sequentiële, willekeurig toegankelijke machine in een typische computer waar gegevens worden ingevoerd.

Je houdt misschien van: