Teller sort kompleksitet

Hva er tellende sort?

Tellingssort illustreres best med sortering av heltall. I C/C ++ og Java er karakterene heltall og kan sorteres i måten heltalene blir sortert. Tenk på følgende usorterte liste over heltall:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Denne listen er sortert i stigende rekkefølge. Det kan gis (mottatt av Sorter -programmet) som en matrise. Den består av positive tall større enn eller lik 0.

Legg merke til at det høyeste heltallet er 20. Så, 20 + 1 = 21, må nye array -lokasjoner leveres. Den ekstra 1 er for muligheten for at et av heltallene skal sorteres er 0. Husk at Sorter -programmet ikke vet at tallene skal sorteres på forhånd. Så muligheten for å ha 0 bør lages.

For hver indeks for den nye matrisen som tilsvarer en verdi i den gitte listen, tildeles antall forekomst av verdien i den gitte listen som verdien for den nye arraycellen. Det vil si at den nye matrisen består av tellere. Den forrige usorterte listen er representert som følger:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	1. 3	14	15	16	17	18	19	20

Denne tabellen representerer en matrise som er den nye rekke tellere. På dette stadiet er det to matriser: den gitte rekkeen av den usorterte listen og utvalget av tellere kalt Count Array.

I tabellen har den andre raden indeksene. Den første raden har tellingene. Hver telling er antall forekomster av den tilsvarende indeksen som er funnet som verdien i den usorterte listen.

For indeksene 0 til 7 (inkluderende) er tellingen 0. Dette er fordi ingen av disse indeksene er en verdi i den gitte usorterte listen. Indeks 8 oppstår en gang på listen, så tellingen er 1. Indeks 9 forekommer null ganger på listen, så tellingen er 0. Indeksen 10 oppstår en gang på listen, så tellingen er 1. Indeksen 12 forekommer tre ganger på listen, så tellingen er 3. Indeksen 13 forekommer null ganger på listen, så tellingen er 0. Dette fortsetter til indeksen 20 med en telling på 1 mens indeksen 18 har en telling på 2.

Den sorterte listen er som følger:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Dette kan fås fra grev (ny) matrise som følger:

Flytter fra venstre til høyre, hvis verdien av en indeks er 0, er den verdien ikke i den gitte usorterte listen (Array). Hvis verdien er 1, skriv inn indeksen en gang. Hvis verdien er 2, skriver du indeksen to ganger. Hvis verdien er 3, skriver du indeksen tre ganger. Hvis verdien er 4, skriv inn indeksen 4 ganger, og så videre. Alle disse kan gjøres tilbake på den gitte usorterte matrisen (liste).

Teller sorteringsalgoritme

• Gi en matrise hvis lengde er det maksimale antallet i den usorterte listen, pluss 1 (for å redegjøre for en mulig 0 på listen). Indeksen for denne matrisen er en mulig verdi i den usorterte listen.
• Les telleoppstillingen fra venstre til høyre, skriv deretter indeksen hvis verdien ikke er 0 og antall ganger for indeksens celleverdi.

Operasjoner

Algoritmen har to trinn. For den forrige gitte listen har det første trinnet 10 hovedoperasjoner fordi antall elementer i den usorterte listen er 10. Det andre trinnet har 21 hovedoperasjoner fordi den maksimale verdien i den usorterte listen er 20 (den ekstra 1 er for en mulig 0 -verdi). Så antallet hovedoperasjoner anses som følger:

O (10 + 20)

Hvor 10 er antall elementer i den usorterte listen og 20 er den maksimale verdien i den usorterte listen. Den tilsatte 1 til 20 blir ignorert på dette tidspunktet, men husk at den må kodes.

Tidskompleksitet for å telle sortering

Tidskompleksitet er det omtrentlige antallet hovedoperasjoner for noen kode. Tidskompleksitet indikerer hastigheten på koden. Tidskompleksiteten for tellende sort er gitt som følger:

O (n + m)

Hvor n er antall elementer (lengde eller størrelse) på den gitte usorterte matrisen, og m er maksimal verdi i den gitte usorterte matrisen. Den ekstra 1 til M blir ignorert på dette tidspunktet. Big-O med sin parentes og innhold blir referert til som Big-O-notasjonen.

Merk at for å oppnå maksimal verdi i matrisen, må noen operasjoner skje i koden. Imidlertid blir disse operasjonene ignorert når du siterer tidskompleksiteten.

Tellingsprisen må ha alle elementene opprinnelig laget som null. Alle disse operasjonene blir også ignorert når du siterer tidskompleksiteten for tellingssorteringen.

Minneplass

Legg merke til at i den forrige tellende matrisen er alle tellingene på 0 overflødige. Selv om rommene deres er overflødige i minnet, må de være der. Tellingssorteringen tar unødvendig minneplass generelt. Ingenting gjøres normalt for å unngå de overflødige stedene. Hvis minimumsverdien i den gitte usorterte matrisen kan være kjent, kan den begynnende delen av tellearrayen utelates for å redusere plassen. Imidlertid kan ikke den ispedd nuller i tellearrayen utelates.

Merk: Det er også romkompleksitet, men det blir ikke adressert i denne artikkelen.

Koding i c

En tellende sortfunksjon på C -dataspråket er som følger:

void Countingsort (int arr [], int n)
int maks = 0;
for (int i = 0; i max)
maks = arr [i];


int count [max+1];
for (int i = 0; i< max+1; i++)
telle [i] = 0;

// n
for (int i = 0; i< n; i++)
telle [arr [i]] = count [arr [i]] + 1; // legg til 1 for hver forekomst

// m
int k = 0; // indeks for gitt matrise
for (int i = 0; iif (count [i] != 0)
for (int j = 0; jarr [k] = i; // å sette tilbake sortert verdi i gitt matrise
K ++;

Den nestede for-loop og inngang er følgende:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Det er faktisk 24 store operasjoner og ikke 20. Den ekstra 3 + 1 = 4 -operasjonen blir ignorert når du siterer tidskompleksiteten for tellingssorteringen.

En passende C hovedfunksjon er som følger:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
Countingsort (arr, n);
for (int i = 0; iprintf ("%d", arr [i]);
printf ("\ n");
retur 0;

Utgangen er:

8 10 12 12 12 14 16 18 18 20

Konklusjon

Tidskompleksiteten for tellende sort er:

O (n + m)

Der M vanligvis er større enn N, er N antall elementer (lengde) på den gitte usorterte listen, og M er det maksimale elementet i den gitte usorterte listen.