Radix-lajittelualgoritmi tietorakenteessa

Mikä on Radix-lajittelualgoritmi?

Radix Sort on ei-vertaileva lajittelualgoritmi. Se toimii ryhmittelemällä lajitettavien elementtien yksittäiset numerot. Sitten käytetään vakaata lajittelutekniikkaa elementtien järjestämiseen niiden kantaluvun perusteella. Se on lineaarinen lajittelualgoritmi.

Lajitteluprosessi sisältää seuraavat ominaisuudet:

  • Löytää maksimielementin ja hankkia kyseisen elementin numeroiden lukumäärä. Se antaa meille iteraatioiden lukumäärän, jota lajitteluprosessi seuraa.
  • Ryhmittele elementtien yksittäiset numerot samaan merkitsevään kohtaan kussakin iteraatiossa.
  • Ryhmittely alkaa vähiten merkitsevästä numerosta ja päättyy merkittävimpään numeroon.
  • Elementtien lajittelu kyseisen merkitsevän kohdan numeroiden perusteella.
  • Saman avainarvon omaavien elementtien suhteellisen järjestyksen ylläpitäminen. Tämä kantalukulajittelun ominaisuus tekee siitä vakaan lajittelun.

Viimeinen iteraatio antaa meille täysin järjestetyn luettelon.

Radix-lajittelualgoritmin toiminta

Radix-lajittelualgoritmin toiminta
Luettelo järjestettävistä kokonaisluvuista

Yritetään lajitella yllä olevan kuvan kokonaislukuluettelo nousevaan järjestykseen käyttämällä Radix Sort -algoritmia.

Tässä on vaiheet, joilla voit suorittaa Radix-lajitteluprosessin:

Vaihe 1) Tunnista elementti, jolla on suurin arvo luettelosta. Tässä tapauksessa se on 835.

Vaihe 2) Laske maksimielementin numeroiden lukumäärä. 835:ssä on tarkalleen 3 numeroa.

Vaihe 3) Määritä iteraatioiden määrä vaiheen 2 perusteella. 835:ssä on 3 numeroa, mikä tarkoittaa, että iteraatioiden määrä on 3.

Vaihe 4) Määritä elementtien kanta. Koska tämä on desimaalijärjestelmä, kantaluku on 10.

Vaihe 5) Aloita ensimmäinen iteraatio.

a) Ensimmäinen iteraatio

Radix-lajittelualgoritmin toiminta
Lajittelu viimeisen numeron mukaan

Ensimmäisessä iteraatiossa otetaan huomioon kunkin elementin yksikköpaikka-arvo.

Vaihe 1) Muokkaa kokonaislukua 10:llä saadaksesi elementtien yksikköpaikan. Esimerkiksi 623 mod 10 antaa meille arvon 3 ja 248 mod 10 antaa meille 8.

Vaihe 2) Järjestä kokonaisluvut pienimmän merkitsevän numeron mukaan käyttämällä laskenta- tai muuta vakaata lajittelua. Kuten kuvasta näkyy, 248 putoaa 8. ämpäriin. 623 putoaa 3. ämpäriin ja niin edelleen.

Ensimmäisen iteroinnin jälkeen lista näyttää nyt tältä.

Radix-lajittelualgoritmin toiminta
Luettelo ensimmäisen iteraation jälkeen

Kuten yllä annetusta kuvasta näkyy, luetteloa ei ole vielä lajiteltu ja se vaatii enemmän iterointia, jotta se olisi täysin lajiteltu.

b) Toinen iteraatio

Radix-lajittelualgoritmin toiminta
Lajittelu kymmenien numeroiden perusteella

Tässä iteraatiossa tarkastelemme numeroa 10:ssäth paikka lajittelua varten.

Vaihe 1) Jaa kokonaisluvut 10:llä. 248 jaettuna 10:llä antaa meille 24.

Vaihe 2) Muuta vaiheen 1 tulos 10:llä. 24 mod 10 antaa meille 4.

Vaihe 3) Noudata edellisen iteroinnin vaihetta 2.

Toisen iteroinnin jälkeen lista näyttää nyt tältä

Radix-lajittelualgoritmin toiminta
Lista toisen iteroinnin jälkeen

Yllä annetusta kuvasta näet, että lista ei ole vieläkään täysin lajiteltu, koska se ei ole vielä nousevassa järjestyksessä.

c) Kolmas iteraatio

Radix-lajittelualgoritmin toiminta
Lajittelu satojen paikkojen numeroiden perusteella

Viimeistä iteraatiota varten haluamme saada merkittävimmän luvun. Tässä tapauksessa se on 100th paikka jokaiselle luettelon kokonaisluvulle.

Vaihe 1) Jaa kokonaisluvut 100:lla… 415 jaettuna 100:lla antaa meille 4.

Vaihe 2) Muuta vaiheen 1 tulosta 10:llä. 4 mod 10 antaa meille jälleen 4.

Vaihe 3) Noudata edellisen iteroinnin vaihetta 3.

Radix-lajittelualgoritmin toiminta
Lista kolmannen iteraation jälkeen

Kuten näemme, luettelo on nyt järjestetty nousevaan järjestykseen. Viimeinen iteraatio on suoritettu, ja lajitteluprosessi on nyt valmis.

Radix-lajittelualgoritmin pseudokoodi

Tässä on pseudokoodi Radix-lajittelualgoritmille

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++ Ohjelma Radix-lajittelun toteuttamiseksi

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

lähtö:

162 248 415 623 835

Python Ohjelma Radix-lajittelualgoritmille

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

lähtö:

[162,248,415,623,835]

Radix-lajittelun monimutkaisuusanalyysi

On olemassa kahdenlaisia ​​​​monimutkaisuutta, jotka on otettava huomioon, tilan monimutkaisuus ja aika monimutkaisuus.

  • Avaruuden kompleksisuus: O(n+b) missä n on taulukon koko ja b on tarkasteltu kanta.
  • Aikamonimutkaisuus: O(d*(n+b)), missä d on taulukon suurimman elementin numeroiden lukumäärä.

Radix-lajittelun tilan monimutkaisuus

Kaksi ominaisuutta, joihin kannattaa keskittyä tilan monimutkaisuuden vuoksi

  • Elementtien lukumäärä taulukossa, n.
  • Perus elementtien esittämiselle, b.

Joskus tämä kanta voi olla suurempi kuin taulukon koko.

Kokonaiskompleksisuus on siis O(n+b).

Seuraavat luettelon elementtien ominaisuudet voivat tehdä kantalajittelutilan tehottoman:

  • Elementit, joissa on suuri määrä numeroita.
  • Elementtien kanta on suuri, kuten 64-bittiset numerot.

Radix-lajittelun aika monimutkaisuus

Voit käyttää laskenta-lajittelua aliohjelmana, koska jokainen iteraatio kestääe O(n+b) aika. Jos d iteraatioita on olemassa, kokonaisajoajasta tulee O(d*(n+b)). Tässä "O" tarkoittaa monimutkaisuusfunktiota.

Radix-lajittelun lineaarisuus

Radix Sort on lineaarinen kun

  • d on vakio, missä d on suurimman alkion numeroiden lukumäärä.
  • b ei ole suuressa määrin suurempi verrattuna n.

Radix-lajittelun vertailut muihin vertailualgoritmeihin

Kuten olemme nähneet, Radix-lajittelun monimutkaisuus perustuu sanan tai numeron kokoon. Se on yhtä monimutkainen keskimääräisissä ja parhaissa tapauksissa. Ja se on O(d*(n+b)). Se vaihtelee myös keskellä käyttämäsi lajittelutekniikan mukaan. Voit esimerkiksi käyttää laskevaa lajittelua tai pikalajittelua välilajittelualgoritmiin kantalukulajittelun sisällä.

Radix-lajittelualgoritmin sovellukset

Radix Sortin tärkeitä sovelluksia ovat:

  • Radix Sortia voidaan käyttää paikannusalgoritmina, jossa käytetään suuria arvoalueita.
  • Sitä käytetään DC3-algoritmin päätetaulukon muodostamiseen.
  • Sitä käytetään peräkkäisessä, satunnaiskäyttöisessä koneessa, joka on tyypillisessä tietokoneessa, jossa tietueet avataan.