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
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
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ä.
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
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ä
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
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.
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.