Uvod

Razvrščanje je bistvena operacija v računalništvu, ki vključuje razvrščanje elementov v določen vrstni red, kot je številčni ali abecedni vrstni red. Razviti so bili različni algoritmi za razvrščanje, vsak s kazalniki časa in učinkovitosti. Linearno časovno razvrščanje je podmnožica algoritmov za razvrščanje s pomembno prednostjo: razvrstijo lahko dani nabor elementov v linearnem času, čas izvajanja se povečuje linearno z velikostjo vnosa.

int niz

Najbolj znan algoritem linearnega časovnega razvrščanja je padajoče razvrščanje. Računalniško razvrščanje je še posebej učinkovito, če je obseg vhodnih elementov znan in razmeroma majhen. To odpravlja potrebo po primerjavi elementov, glavni zamudni operaciji v mnogih drugih algoritmih za razvrščanje. Z uporabo znanja o vhodni domeni računalniško razvrščanje doseže linearno časovno kompleksnost. Numerično razvrščanje najprej pregleda vhodno matriko, da določi število vsakega elementa. Te številke nato uporabi za izračun pravilnih položajev elementov v urejeni tabeli rezultatov. Algoritem je sestavljen iz naslednjih korakov:

1. Če želite določiti obseg, določite najmanjšo in največjo vrednost vhodne matrike.
2. Ustvarite delovni list, inicializiran z velikostjo obsega in ničlami.
3. Preglejte vhodno matriko in povečajte vsak najdeni element.
4. Spremenite delovni list tako, da izračunate kumulativno vsoto, da dobite pravilne položaje za vsak element.
5. Ustvarite izhodno polje enake velikosti kot vhodno polje.
6. Ponovno premaknite vhodno matriko in postavite vsak element na pravilen položaj v izhodni matriki glede na delovni list.
7. Tabela rezultatov zdaj vsebuje razvrščene elemente.

Glavna prednost padajočega razvrščanja je, da doseže linearno časovno kompleksnost O(n), zaradi česar je zelo učinkovito za velike vhodne velikosti. Vendar je njegova uporabnost omejena na scenarije, kjer je izbira vhodnih elementov znana vnaprej in relativno majhna.

Pomembno je omeniti, da imajo drugi algoritmi za razvrščanje, kot sta hitro razvrščanje ali spajanje, običajno časovno kompleksnost O(n log n), kar velja za učinkovito za številne praktične aplikacije. Algoritmi za linearno časovno razvrščanje, kot je numerično razvrščanje, nudijo alternativo, kadar določene omejitve ali lastnosti vnosa omogočajo uporabo linearne časovne kompleksnosti.

Zgodovina

Algoritmi za linearno časovno razvrščanje imajo v računalništvu bogato zgodovino. Razvoj linearnega časovnega reda sega v sredino 20. stoletja, prispevki znanstvenikov in matematikov pa so bili pomembni. Eden najzgodnejših algoritmov linearnega časovnega razvrščanja je razvrščanje po vedrih, ki ga je leta 1954 predlagal Harold H. Seward. Razvrščanje po vedrih razdeli vhodne elemente na končno število veder in nato razvrsti vsako vedro posebej. Ta algoritem ima linearno časovno kompleksnost, če je porazdelitev vhodnih elementov relativno enakomerna.

Leta 1959 je Kenneth E. Iverson predstavil algoritem radix, ki dosega linearno časovno kompleksnost. Radix razvrsti elemente po njihovih številkah ali predznakih od najmanj pomembnega do najpomembnejšega. Uporablja robustne algoritme za razvrščanje, kot je številsko ali vedro razvrščanje, za razvrščanje elementov na vsaki lokaciji števke. Razvrščanje po sistemu Radix je postalo priljubljeno v dobi luknjanih kartic in zgodnjih računalniških sistemov. Vendar pa je najbolj znan linearni algoritem za časovno razvrščanje štetje, ki sta ga predstavila Harold H. Seward in Peter Elias leta 1954, kasneje pa ga je neodvisno ponovno odkril Harold H. 'Bobby' Johnson leta 1961. Numerično razvrščanje je bilo deležno precejšnje pozornosti.

To je še posebej učinkovito, če je obseg vhodnih elementov znan in relativno majhen. Zgodovina linearnega časovnega razvrščanja se je nadaljevala z razvojem drugih specializiranih algoritmov. Na primer, leta 1987 je Hanan Samet predlagal binarno porazdelitveno drevesno razvrščanje, linearni algoritem časovnega razvrščanja za večdimenzionalne podatke. Z leti so raziskovalci še naprej preučevali in izboljševali algoritme linearnega razporejanja, pri čemer so se osredotočali na specifične scenarije in omejitve. Čeprav se algoritmi, kot sta hitro razvrščanje in združevanje, pogosteje uporabljajo zaradi svoje učinkovitosti v več scenarijih, algoritmi za linearno časovno razvrščanje zagotavljajo dragocene alternative, kadar določene okoliščine omogočajo izkoriščanje kompleksnosti linearnega časa. Na splošno je za zgodovino linearnega časovnega razvrščanja značilno iskanje učinkovitih algoritmov, ki lahko razvrstijo velike podatkovne nize v linearnem času, s čimer presežejo omejitve algoritmov za razvrščanje, ki temeljijo na primerjavi. Prispevki različnih raziskovalcev so utrli pot razvoju in razumevanju teh specializiranih tehnik razvrščanja.

Vrste linearnega časovnega razvrščanja

Obstaja več različnih algoritmov linearnega časovnega razvrščanja. Dve glavni vrsti sta algoritmi, ki temeljijo na štetju, in algoritmi, ki temeljijo na korenu. Tu so najpogostejši algoritmi linearnega časovnega razvrščanja, razvrščeni glede na naslednje vrste:

Algoritmi na osnovi štetja

Razvrščanje na podlagi štetja:Counting-Based je neprimerjalni algoritem za razvrščanje. Šteje pojavljanje vsakega posameznega elementa v vhodni matriki in te informacije uporablja za določitev pravilnega položaja vsakega elementa v razvrščeni izhodni matriki. Razvrščanje na podlagi štetja predvideva, da so vhodni elementi cela števila ali da jih je mogoče dodati celim številom.

Algoritmi na osnovi Radixa

Razvrsti Radix:Radix Sort je algoritem za razvrščanje, ki ne temelji na primerjavi in ​​razvršča elemente po njihovih številkah ali znakih. Šteje vsako število ali znak v elementih od najmanj pomembnega števila do najpomembnejšega. Radikalno razvrščanje predpostavlja, da so vhodni elementi cela števila ali nizi.Razvrstitev vedra:Bucket Sort je različica Radix Sort, ki deli elemente v fiksne skupine glede na njihov obseg ali porazdelitev. Vsak segment je razvrščen ločeno z uporabo drugačnega algoritma za razvrščanje ali rekurzivnega bin-sortiranja.MSD (Most Significant Digit) Radix Razvrščanje:MSD Radix Sort je različica radix sorta, ki začne razvrščati elemente na podlagi njihovih najpomembnejših. Rekurzivno razdeli elemente v podskupine glede na vrednost trenutnega števila in uporabi MSD Radix Sort za vsako podskupino, dokler niso prešteta vsa števila.LSD (najmanj pomembna cifra) Radix Razvrščanje:LSD Radix Sort je še ena različica, ki začne razvrščati elemente na podlagi njihovega najmanjšega pomena. Rekurzivno razvršča elemente na podlagi vsake številke od skrajne desne proti skrajni levi, kar proizvede razvrščen rezultat. Algoritmi za razvrščanje, ki temeljijo na štetju in korenih, dosežejo linearno časovno kompleksnost z izkoriščanjem posebnih lastnosti vhodnih elementov, kot je njihov obseg ali reprezentativna struktura (npr. številke ali znaki). Vendar se lahko njihova uporabnost razlikuje glede na značilnosti vhodnih podatkov.

Prednosti linearnega časovnega razvrščanja

Algoritmi linearnega časovnega razvrščanja, kot je numerično razvrščanje, ponujajo več prednosti v določenih scenarijih.

Učinkovito za velike vnosne velikosti:Časovna kompleksnost algoritmov za linearno razvrščanje časa je O(n), kar pomeni, da čas delovanja narašča linearno z velikostjo vnosa. Zaradi tega so zelo učinkoviti za velike nabore podatkov v primerjavi z algoritmi za razvrščanje, ki temeljijo na primerjavi, kot so algoritmi za hitro razvrščanje ali spajanje, katerih časovna kompleksnost je običajno O(n log n).Brez primerjalnih operacij:Algoritmi za linearno časovno razvrščanje, kot je razvrščanje po številu, se ne zanašajo na osnovno primerjavo, temveč uporabljajo specifične atribute ali informacije o vhodnih elementih, kot je njihov obseg ali porazdelitev. Zaradi te funkcije so ugodne, ko so stroški primerjave visoki, na primer pri kompleksnih objektih ali dragih primerjalnih operacijah.Primernost za posebne vhodne lastnosti:Algoritmi za linearno časovno razvrščanje imajo pogosto posebne zahteve ali predpostavke o vhodnih elementih. Če želite na primer izračunati vrstni red razvrščanja, morate vnaprej poznati obseg vhodnih elementov. Ko so ti pogoji izpolnjeni, lahko algoritmi za linearno časovno razvrščanje ponudijo pomembne prednosti v zmogljivosti pred splošnimi algoritmi za razvrščanje.Stabilna sorta:Številni algoritmi za linearno časovno razvrščanje, vključno z numeričnim in radiksnim razvrščanjem, so sami po sebi stabilni. Doslednost pomeni, da elementi s podvojenimi ključi ali vrednostmi ohranjajo relativni red v razvrščenem izhodu. To je lahko ključnega pomena pri razvrščanju predmetov ali zapisov z več atributi ali kadar je bistvenega pomena ohranjanje izvirnega vrstnega reda elementov enake vrednosti.Enostavnost uporabe:Algoritme linearnega časovnega razvrščanja, kot je razvrščanje s številčenjem, je pogosto razmeroma enostavno implementirati v primerjavi z bolj zapletenimi algoritmi za razvrščanje, ki temeljijo na primerjavi. Lažje jih je razumeti in odpraviti napake, zaradi česar so primerni za situacije, kjer sta zaželeni preprostost in jasnost.

Slabosti linearnega časovnega razvrščanja

Čeprav imajo algoritmi linearnega razporejanja svoje prednosti, imajo tudi določene omejitve in slabosti:

Omejitvene zahteve za vnos:Algoritmi za linearno časovno razvrščanje imajo pogosto posebne zahteve ali predpostavke o vhodnih elementih. Če želite na primer izračunati vrstni red razvrščanja, morate vnaprej poznati obseg vhodnih elementov. Ta omejitev omejuje njihovo uporabnost na situacije, kjer so ti pogoji izpolnjeni. Zahteve po pomnilniku lahko postanejo nepraktične ali presežejo razpoložljive vire, če je obseg obsežen ali neznan.Dodatne prostorske zahteve:Nekateri algoritmi linearnega časovnega razvrščanja, kot je numerično razvrščanje, zahtevajo dodaten prostor za shranjevanje drugih nizov ali podatkovnih struktur. Potreben prostor je pogosto sorazmeren s številom vhodnih elementov. To je lahko pomanjkljivost, kadar je uporaba pomnilnika težava, zlasti ko imate opravka z velikimi nabori podatkov ali omejenimi pomnilniškimi viri.Pomanjkanje vsestranskosti:Algoritmi za linearno časovno razvrščanje so specializirani algoritmi, zasnovani za posebne scenarije ali omejitve. Morda bodo morali biti primernejši in učinkovitejši za splošne naloge razvrščanja ali različne porazdelitve vnosa. Algoritmi za razvrščanje, ki temeljijo na primerjavi, kot sta hitro razvrščanje ali združevanje, so bolj vsestranski in lahko obravnavajo širši obseg vhodnega obsega.Neučinkovito za majhne obsege ali redke podatke:Algoritmi za linearno časovno razvrščanje, kot je oštevilčenje, so najučinkovitejši, ko je obseg vhodnih elementov majhen in gosto porazdeljen. Če je obseg obsežen ali so podatki redki (tj. le nekaj različnih vrednosti), lahko algoritem prihrani čas in napor pri obdelavi praznih ali redko poseljenih delov vhodnega obsega.Omejeno na določene vrste podatkov:Algoritmi za linearno časovno razvrščanje, kot je razvrščanje po številu, so v prvi vrsti zasnovani za razvrščanje nenegativnih celih števil ali predmetov ključ-vrednost. Morda niso primerni za razvrščanje drugih tipov podatkov, kot so števila s plavajočo vejico, nizi ali kompleksne podatkovne strukture. Prilagajanje algoritmov linearnega časovnega razvrščanja za obravnavo različnih tipov podatkov ali primerjalnih funkcij po meri lahko zahteva dodatno predhodno obdelavo ali spremembe.

Pri izbiri sortirnega algoritma je nujno skrbno upoštevati posebnosti vhodnih podatkov in zahteve problema sortiranja. Čeprav linearni algoritmi za razporejanje ponujajo prednosti v posebnih scenarijih, so le včasih najprimernejša ali najučinkovitejša izbira.

Uporaba algoritmov za linearno časovno razvrščanje

Algoritmi za linearno časovno razvrščanje so učinkoviti in imajo veliko aplikacij na različnih področjih. Tukaj je nekaj tipičnih aplikacij linearnega časovnega reda:

Razvrščanje majhnih celih števil:Algoritmi linearnega časovnega razvrščanja, kot sta razvrščanje po štetju in razvrščanje po korenu, so idealni za razvrščanje nizov celih števil, ko je obseg vrednosti. Ti algoritmi dosegajo linearno časovno zapletenost s predpostavkami o vhodnih podatkih, kar jim omogoča, da obidejo razvrščanje, ki temelji na primerjavi.Razvrščanje nizov:Algoritme linearnega časovnega razvrščanja je mogoče uporabiti tudi za učinkovito razvrščanje nizov. Z upoštevanjem edinstvenih lastnosti nizov, kot so njihova dolžina ali znaki, lahko algoritmi, kot je Radix Sort, dosežejo linearno časovno kompleksnost pri razvrščanju nizov.Funkcije baze podatkov:Razvrščanje je bistvena funkcija algoritmov linearnega časovnega razvrščanja, ki lahko učinkovito razvrstijo velike nize podatkov na podlagi določenih stolpcev ali polj. To omogoča hitrejšo obdelavo poizvedb in boljšo zmogljivost pri operacijah baze podatkov.Ustvarjanje histogramov:Histogrami so bistveni za različne statistične naloge in naloge analize podatkov. Algoritmi linearnega časovnega razvrščanja, kot je numerično razvrščanje, lahko ustvarijo histograme z učinkovitim štetjem pojavitev elementov v naboru podatkov.Zunanje razvrščanje:Tehnika zunanjega razvrščanja se uporablja v scenarijih, kjer se podatki ne morejo popolnoma prilegati pomnilniku. Algoritmi za linearno časovno razvrščanje, kot sta External Radix Sort ali External Counting Sort, lahko učinkovito razvrstijo velike nize podatkov, shranjene na disku ali drugih zunanjih napravah za shranjevanje.Načrtovanje dogodkov:Algoritmi za linearno razvrščanje časa lahko načrtujejo dogodke glede na njihov začetni ali končni čas. Razvrščanje dogodkov v naraščajočem vrstnem redu olajša prepoznavanje konfliktov, prekrivajočih se obdobij ali iskanje naslednjega razpoložljivega obdobja.Analiziranje dnevniških datotek:Analiza dnevniških datotek je pogosta naloga pri sistemski administraciji in odpravljanju napak. Algoritme linearnega časovnega razvrščanja je mogoče uporabiti za razvrščanje dnevnikov na podlagi časovnih žigov, kar olajša prepoznavanje vzorcev, anomalij ali iskanje določenih dogodkov.Stiskanje podatkov:Razvrščanje ima bistveno vlogo pri različnih tehnikah stiskanja podatkov. Algoritmi, kot sta Burrows-Wheeler Transform (BWT) ali Move-To-Front Transform (MTF), se zanašajo na linearno časovno urejanje za preurejanje podatkov za izboljšanje učinkovitosti stiskanja. To je le nekaj primerov uporabe algoritmov linearnega časovnega razvrščanja.

Implementacija linearnega časovnega razvrščanja v C++

Tukaj je primer programa, ki izvaja Counting Sort, ki je linearni algoritem za razvrščanje časa:

 #include #include using namespace std; void countingSort(vector&amp; arr) { // Find the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // Create a count array to store the count of each element vector count(max_val + 1, 0); // Count the occurrences of each element for (int num : arr) { count[num]++; } // Compute the prefix sum for (int i = 1; i <count.size(); i++) { count[i] +="count[i" - 1]; } create a sorted output array vector output(arr.size()); place the elements in order for (int i="arr.size()" 1;>= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Copy the sorted elements back to the original array for (int i = 0; i <arr.size(); i++) { arr[i]="output[i];" } int main() vector arr="{4," 2, 8, 3, 1}; sort the array using counting countingsort(arr); print sorted cout << 'sorted array: '; for (int num : arr) ' endl; return 0; < pre> <p> <strong>Sample Output</strong> </p> <pre> Sorted array: 1 2 2 3 3 4 8 </pre> <p>This indicates that the input array has been sorted in ascending order using the Counting Sort algorithm, resulting in the sorted array [1, 2, 2, 3, 3, 4, 8].</p> <p>In this C++ program, the counting sort function takes a reference to the vector arr and runs the counting sort routine. It finds the table&apos;s maximum value to determine the worksheet&apos;s size. It then counts each element&apos;s occurrence and calculates the worksheet&apos;s prefix sum. Then, it creates a result vector and puts the elements in order according to the worksheet. Finally, it copies the sorted elements back into the original array. In the primary function, the example array {4, 2, 2, 8, 3, 3, 1} is sorted by the enumeration sort algorithm and printed as a sorted matrix. Note that the program uses libraries to work with vectors and find the maximum element of an array using the max_element function.</p> <hr></arr.size();></count.size();>

To pomeni, da je bila vhodna matrika razvrščena v naraščajočem vrstnem redu z uporabo algoritma Counting Sort, rezultat pa je razvrščena matrika [1, 2, 2, 3, 3, 4, 8].

V tem programu C++ se funkcija razvrščanja s štetjem sklicuje na vektor arr in zažene rutino razvrščanja s štetjem. Poišče največjo vrednost tabele, da določi velikost delovnega lista. Nato prešteje pojavnost vsakega elementa in izračuna vsoto predpone delovnega lista. Nato ustvari vektor rezultata in postavi elemente v vrstni red glede na delovni list. Na koncu kopira razvrščene elemente nazaj v izvirno matriko. V primarni funkciji je primer matrike {4, 2, 2, 8, 3, 3, 1} razvrščen z algoritmom za razvrščanje po številu in natisnjen kot razvrščena matrika. Upoštevajte, da program uporablja knjižnice za delo z vektorji in iskanje največjega elementa matrike s funkcijo max_element.