Radix Sort

En radiks eller base er en representasjon av et tall som viser hvor mange sifre som er nødvendige for å representere et posisjonsnummer. For eksempel, for å representere det binære tallet, er radixverdien 2 (vi representerer det binære enten med 0 eller 1). For å representere desimaltallet er radixverdien 10 (vi representerer desimaltallet med tall 0 til 9).

Hvordan Redix Sort -algoritmen fungerer

La oss anta at vi har følgende array -liste, og vi vil sortere denne matrisen ved å bruke Radix -sorteringen:

Vi bruker to konsepter til i denne algoritmen, som er:

1. 1. Minst betydelig siffer
   2. Mest betydningsfulle siffer

1. Minst betydelig siffer (LSD): Eksponentverdien til et desimaltall som er ekstremt nær den høyre posisjonen blir referert til som LSD.

For eksempel har desimaltallet "2563" den minst betydningsfulle sifferverdien på "3".

2. Mest betydningsfulle siffer (MSD): MSD er LSDs eksakte inverse. En MSD-verdi er den ikke-null venstre sifferet til et hvilket som helst desimaltall.

For eksempel har desimaltallet “2563” den viktigste sifferverdien på “2”.

Trinn 1: Se etter det viktigste elementet (maksimal verdi)

Som vi allerede vet, fungerer denne algoritmen på sifrene for å sortere tallene. Så for det krever denne algoritmen maksimalt antall sifre for iterasjonen. Vårt første trinn er å finne ut det maksimale antall elementer i denne matrisen. Etter å ha funnet den maksimale verdien av en matrise, må vi telle antall sifre i det tallet for iterasjonene.

Trinn 2: Tell antall sifre av det maksimale elementet

Vi må telle antall sifre av det maksimale elementet i en matrise, for da kan vi finne ut hvor mange iterasjoner vi trenger for å sortere matrisen.

Så som vi allerede fant ut, er det maksimale elementet 167 og antall sifre er 3. Vi trenger tre iterasjoner for å sortere matrisen.

Trinn 3: Sortering av elementene med minst betydelig siffer

Det første sifferarrangementet gjøres av det minst betydningsfulle sifferet. Fra følgende bilde kan vi se at alle de minste, minst betydelige sifrene er ordnet på venstre side. I dette tilfellet fokuserer vi bare på det minst betydningsfulle sifferet.

En ting vi kan legge merke til her er at noen sifre automatisk blir sortert, selv om enhetssifrene deres er forskjellige, men de andre er de samme.

For eksempel, Tallene 36 i indeksposisjon 7 og nummer 32 i indeksposisjon 3 har begge forskjellige enhetssifre, men har samme andre nummer, som er 3. Åpenbart kommer nummer 32 før nummer 36. Etter de første elementarrangementene kan vi se at nå, 32 kommer før 36 som automatisk blir sortert.

Trinn 4: Sortering av elementene i henhold til neste siffer (TENS -siffer)

Nå ordner vi elementene i matrisen gjennom det tiende stedsifret. Som vi allerede vet, må denne sorteringen være ferdig i 3 iterasjoner fordi det maksimale antall elementer har 3 sifre. Dette er vår andre iterasjon, og vi kan anta at de fleste av matriseelementene er sortert etter denne iterasjonen.

De gitte resultatene viser at de fleste av matriseelementene allerede er sortert (under 100). Hvis vi bare hadde to sifre som vårt maksimale antall, er bare to iterasjoner nok til å få den sorterte matrisen.

Trinn 5: Sortering av elementene basert på det viktigste sifferet

Nå går vi inn i den tredje iterasjonen basert på det viktigste sifferet (hundrevis). Denne iterasjonen sorterer de tre sifrede elementene i matrisen. Etter denne iterasjonen er alle elementer i matrisen i sortert rekkefølge.

Etter å ha arrangert elementene basert på MSD, er vår matrise nå fullstendig sortert.

Vi forsto konseptene til Radix Sort -algoritmen. Men vi trenger en algoritme til for å implementere radix -sorteringen, og det er Teller sorteringsalgoritme. La oss forstå dette teller sorteringsalgoritme.

Teller sorteringsalgoritme

Vi forklarer nå hvert trinn i tellende sorteringsalgoritmen.

Den medfølgende matrisen er vår input matrise, og tallene som vises over matrisen er indeksnumrene til de tilsvarende elementene.

Trinn 1: Søk i det maksimale elementet

Det første trinnet i tellende sorteringsalgoritme er å søke etter det maksimale elementet i hele matrisen. Den beste måten å søke etter det maksimale elementet er å krysse hele matrisen og sammenligne elementene i hver iterasjon - det større verdielementet blir oppdatert til slutten av matrisen.

I løpet av det første trinnet fant vi ut at makselementet er 9 i indeksposisjon 8.

Trinn 2: Lag en ny rekke sammenlignbare størrelser

Vi lager et nytt utvalg av lignende størrelser. Som vi allerede vet, er den maksimale verdien av matrisen 9, så det vil være totalt 10 elementer. Som et resultat krever vi en maksimal arraystørrelse på + 1.

Som vi kan se i forrige bilde, har vi en total matrisestørrelse på 10 med verdier på 0. I neste trinn fyller vi denne telleoppstillingen med sorterte elementer.

Trinn 3: Fyll den nye matrisen i henhold til hyppigheten til hvert element

I dette trinnet teller vi hvert element, og fyller i henhold til frekvensen ut de tilsvarende verdiene i matrisen.

For eksempel, Som vi ser er element 6 til stede to ganger i inngangsarrayen. Så vi oppgir frekvensverdien på 2 ved indeks 6.

Trinn 4: Bestem den kumulative frekvensen

Nå teller vi den kumulative frekvensen av den fylte matrisen. Denne kumulative frekvensen brukes senere for å sortere inngangsarrayen.

Vi kan beregne den kumulative frekvensen ved å legge til gjeldende verdi til den forrige indeksverdien, som vist i følgende skjermbilde:

Den siste verdien av matrisen i den kumulative matrisen må være det totale antallet elementer.

Trinn 5: Sorterer matrisen med kommutativ frekvens

Nå bruker vi den kumulative frekvensarrayen for å kartlegge hvert arrayelement for å produsere en sortert matrise.

For eksempel, det første elementet i matrisen 5 som vi velger. Deretter den tilsvarende kumulative frekvensverdien ved indeks 5 som har en verdi på 7. Vi reduserer verdien med 1 og fikk 6. Vi plasserer verdien 5 i indeksen på 6 -posisjonen og reduserer også den kumulative frekvensen ved indeks 5 med 1.

Den kumulative frekvensen er ved indeks 5 etter å ha blitt redusert av en.

La oss forstå dette konseptet med ett eksempel til.

Neste element i matrisen er 2. Vi velger indeksverdien på 2 i kommutativ frekvensarray. Vi reduserer verdien ved indeks 2 og får 1. Vi plasserer matriselementet 2 i indeksposisjon 1. På slutten reduserer vi frekvensverdien ved indeks 2 med 1, som vist på følgende skjermbilde:

Fra forrige sorterte matrise kan vi se at bare ett sted er igjen før 2 (indeksposisjon 1) og en verdi mindre enn 2 i den originale matrisen, som er 1. Så det går på riktig måte å sortere matrisen.

Vi trenger ikke å huske å redusere den kumulative verdien ved hver iterasjon. Etter to av de tidligere iterasjonene ser den kumulative matrisen ut som følgende:

Trinn 6: Endelig matrise

Vi kjører trinn 5 til hvert matriseelementer er fylt ut i den sorterte matrisen. Etter at den er fylt, ser vårt utvalg slik ut:

C ++ Program for Radix Sort -algoritme

Dette eksemplet er basert på forklaringen i denne Linux -hintopplæringen

#inkludere
ved hjelp av navneområdet STD;
void Radixsortalgo (int a [], int size_of_a)
// I det første trinnet (trinn 1) fina maksimalverdien i matrisen.
int maksimumsnummer = a [0];
for (int i = 1; iMaximumNumber = max (maksimumsnummer, a [i]);

// I det andre trinnet (trinn 2) beregner vi antall sifre av
// det maksimale elementet i matrisen
int DigitsCount = 0;
mens (maksimumsnummer> 0)
DigitScount ++;
Maximumnumber /= 10;

// Vi oppdaterer nå en ny matrise (trinn 3,4 og 5)
for (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// dette er en count_array som brukes til tellingsprisen
// for å sortere sifre 0 til 9.
int count_array [10];
memset (count_array, 0, sizeof (count_array));
// beregne hyppigheten til hvert element i matrisen
for (int j = 0; jint num = (a [j]/pwr) % 10;
count_array [num] ++;

// dette er en komulerende frekvens
for (int j = 1; j<10;j++)
count_array [j] += count_array [j-1];

// Vi kartlegger frekvensarrayen med hvert element
// av matrisen for å finne ut ønsket posisjon i den oppdaterte matrisen
for (int j = size_of_a-1; j> = 0; j-)
int num = (a [j]/pwr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Nå oppdaterer vi matrisen med den nye matrisen
for (int j = 0; ja [j] = new_a [j];

// Endelig skriver vi ut det sorterte array -resultatet
for (int j = 0; jcout<cout<
int main ()
// Denne rekke verdier vil bli sortert ved hjelp av Radix Sort -algoritmen.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// vi beregner størrelsen på matrisen
int size_of_a = sizeof (a)/sizeof (size_of_a);
// Ring til Radix Sort algoritmmetode
RadixSortalgo (A, størrelse_of_a);
retur 1;

Utgang fra å kjøre C+ radix sortering

linuxhint@desktop: ~ $ ./Radix
3 6 10 16 38 51 91 155 755 811
linuxhint@desktop: ~ $

Tidskompleksitet av radix sorteringsalgoritme

La oss beregne tidskompleksiteten til radix -sorteringsalgoritmen.

Trinn 1: For å beregne det maksimale antall elementer i hele matrisen, krysser vi hele matrisen. Så den totale tiden som kreves er O (n).

Trinn 2: La oss anta at de totale sifrene i det maksimale antallet er k. Så den totale tiden som tas for å beregne antall sifre i maksimalt antall er o (k).

Trinn 3 til 5: Disse trinnene fungerer på sifrene i seg selv, så de tar o (k) ganger sammen med å telle sorteringsalgoritmen ved hver iterasjon - o (k * n).

Som et resultat er den totale tidskompleksiteten O (k * n).

Konklusjon

Vi studerte radix -sortering og tellingsalgoritme. Det er forskjellige typer sorteringsalgoritmer som er tilgjengelige på markedet. Den beste algoritmen avhenger også av kravene. Det er ikke lett å si hvilken algoritme som er best. Men på grunnlag av tidskompleksiteten prøver vi å finne ut av den beste algoritmen. Og på grunnlag av det er Radix Sort også en av de beste algoritmene for sortering.