Ievads

Kārtošana ir būtiska darbība datorzinātnēs, kas ietver elementu sakārtošanu noteiktā secībā, piemēram, ciparu vai alfabētiskā secībā. Ir izstrādāti dažādi šķirošanas algoritmi, katrs ar laika un efektivitātes rādītājiem. Lineārā laika šķirošana ir šķirošanas algoritmu apakškopa ar būtisku priekšrocību: tie var kārtot noteiktu elementu kopu lineārā laikā, izpildes laiks lineāri palielinās līdz ar ievades lielumu.

Vispazīstamākais lineārās laika šķirošanas algoritms ir dilstošā kārtošana. Skaitļošanas šķirošana ir īpaši efektīva, ja ir zināms ievades elementu diapazons un tas ir salīdzinoši mazs. Tas novērš nepieciešamību salīdzināt elementus, kas ir galvenā laikietilpīgā darbība daudzos citos šķirošanas algoritmos. Izmantojot ievades domēna zināšanas, skaitļošanas šķirošana sasniedz lineāru laika sarežģītību. Skaitliskā kārtošana vispirms skenē ievades masīvu, lai noteiktu katra elementa skaitu. Pēc tam tā izmanto šos skaitļus, lai aprēķinātu elementu pareizās pozīcijas sakārtotajā rezultātu tabulā. Algoritms sastāv no šādām darbībām:

1. Lai noteiktu diapazonu, nosakiet ievades masīva minimālās un maksimālās vērtības.
2. Izveidojiet darblapu, kas inicializēta ar diapazona lielumu un nullēm.
3. Atkārtojiet ievades masīvu un palieliniet katru atrasto elementu.
4. Modificējiet darblapu, aprēķinot kumulatīvo kopsummu, lai iegūtu katra elementa pareizās pozīcijas.
5. Izveidojiet izvades masīvu, kas ir tāda paša izmēra kā ievades masīvs.
6. Vēlreiz pārvietojiet ievades masīvu, novietojot katru elementu pareizajā pozīcijā izvades masīvā, pamatojoties uz darblapu.
7. Rezultātu tabulā tagad ir sakārtoti elementi.

Dilstošās kārtošanas galvenā priekšrocība ir tā, ka tiek sasniegta lineāra laika sarežģītība O(n), kas padara to ļoti efektīvu lieliem ievades izmēriem. Tomēr tā pielietojamība ir ierobežota ar scenārijiem, kuros ievades elementu izvēle ir iepriekš zināma un salīdzinoši neliela.

Ir svarīgi atzīmēt, ka citiem šķirošanas algoritmiem, piemēram, ātrajai šķirošanai vai sapludināšanai, laika sarežģītība parasti ir O (n log n), kas tiek uzskatīta par efektīvu daudzos praktiskos lietojumos. Lineārā laika šķirošanas algoritmi, piemēram, skaitliskā šķirošana, nodrošina alternatīvu, ja noteikti ievades ierobežojumi vai īpašības ļauj izmantot lineāro laika sarežģītību.

Vēsture

Lineārās laika šķirošanas algoritmiem ir bagāta vēsture datorzinātnēs. Lineārās laika kārtības attīstība ir meklējama 20. gadsimta vidū, un zinātnieku un matemātiķu ieguldījums bija nozīmīgs. Viens no agrākajiem lineārās laika kārtošanas algoritmiem ir kārtošana segmentā, ko 1954. gadā ierosināja Harolds H. Sevards. Kausu kārtošana sadala ievades elementus ierobežotā skaitā segmentu un pēc tam šķiro katru segmentu atsevišķi. Šim algoritmam ir lineāra laika sarežģītība, ja ievades elementu sadalījums ir samērā vienmērīgs.

1959. gadā Kenets E. Aiversons ieviesa radix algoritmu, kas sasniedz lineāro laika sarežģītību. Radix kārto elementus pēc to skaita vai zīmēm no vismazākā līdz visnozīmīgākajam. Tas izmanto spēcīgus šķirošanas algoritmus, piemēram, ciparu vai segmentu kārtošanu, lai kārtotu elementus katrā cipara vietā. Radix šķirošana kļuva populāra perfokaršu un agrīno datorsistēmu laikmetā. Tomēr vispazīstamākais lineārās laika šķirošanas algoritms ir uzskaitījums, ko 1954. gadā ieviesa Harolds H. Sevards un Pīters Eliass, bet vēlāk neatkarīgi no jauna atklāja Harolds H. Bobijs Džonsons 1961. gadā. Skaitliskajai šķirošanai ir pievērsta liela uzmanība.

alfabēts numurēts

Tas ir īpaši efektīvi, ja ievades elementu diapazons ir zināms un salīdzinoši mazs. Lineārās laika šķirošanas vēsture turpinājās, izstrādājot citus specializētus algoritmus. Piemēram, 1987. gadā Hanans Samets ierosināja bināro sadalījuma koku šķirošanu, lineāro laika šķirošanas algoritmu daudzdimensiju datiem. Gadu gaitā pētnieki ir turpinājuši pētīt un uzlabot lineāros plānošanas algoritmus, koncentrējoties uz konkrētiem scenārijiem un ierobežojumiem. Lai gan algoritmi, piemēram, ātrā kārtošana un sapludināšana, tiek plaši izmantoti to efektivitātes dēļ vairākos scenārijos, lineārā laika šķirošanas algoritmi nodrošina vērtīgas alternatīvas, ja noteikti apstākļi ļauj izmantot lineārā laika sarežģītību. Kopumā lineārās laika šķirošanas vēsturi raksturo efektīvu algoritmu meklēšana, kas var kārtot lielas datu kopas lineārā laikā, pārvarot uz salīdzinājumu balstītu šķirošanas algoritmu ierobežojumus. Dažādu pētnieku ieguldījums pavēra ceļu šo specializēto šķirošanas metožu izstrādei un izpratnei.

Lineārās laika šķirošanas veidi

Ir vairāki dažādi lineārās laika šķirošanas algoritmi. Divi galvenie veidi ir uz skaitīšanu balstīti algoritmi un uz radix balstīti algoritmi. Šeit ir visizplatītākie lineārās laika šķirošanas algoritmi, kas klasificēti pēc šādiem veidiem:

Uz skaitīšanu balstīti algoritmi

Uzskaites kārtošana:Skaitīšanas pamatā ir nesalīdzinošs šķirošanas algoritms. Tas uzskaita katra konkrētā elementa rašanos ievades masīvā un izmanto šo informāciju, lai noteiktu katra elementa pareizo pozīciju sakārtotajā izvades masīvā. Uzskaites kārtošana pieņem, ka ievades elementi ir veseli skaitļi vai tos var pievienot veseliem skaitļiem.

Uz radiksiem balstīti algoritmi

Kārtot Radix:Radix Sort ir uz salīdzināšanu nebalstīts kārtošanas algoritms, kas kārto elementus pēc to skaitļiem vai rakstzīmēm. Tas saskaita katru elementos esošo skaitli vai zīmi no vismazāk nozīmīgākā skaitļa līdz visnozīmīgākajam. Radikālā kārtošana pieņem, ka ievades elementi ir veseli skaitļi vai virknes.Kausu kārtošana:Bucket Sort ir Radix Sort variants, kas sadala elementus fiksētās grupās, pamatojoties uz to diapazonu vai sadalījumu. Katrs segments tiek kārtots atsevišķi, izmantojot atšķirīgu kārtošanas algoritmu vai rekursīvi kārtošanu.MSD (visnozīmīgākais cipars) radiksu kārtošana:MSD Radix Sort ir radix kārtošanas variants, kas sāk kārtot elementus, pamatojoties uz to nozīmīgākajiem Tas rekursīvi sadala elementus apakšgrupās, pamatojoties uz pašreizējā skaitļa vērtību, un piemēro MSD Radix Sort katrai apakšgrupai, līdz visi skaitļi ir saskaitīti.LSD (vismazāk nozīmīgais cipars) radiksu kārtošana:LSD Radix Sort ir vēl viens variants, kas sāk kārtot elementus, pamatojoties uz to mazāk nozīmīgo. Tas rekursīvi kārto elementus, pamatojoties uz katru numuru, no galējā labā līdz galam kreisajam, radot sakārtotu rezultātu. Gan uz skaitīšanu, gan saknes kārtošanas algoritmi panāk lineāru laika sarežģītību, izmantojot konkrētas ievades elementu īpašības, piemēram, to diapazonu vai attēlojuma struktūru (piemēram, skaitļus vai rakstzīmes). Tomēr to pielietojamība var atšķirties atkarībā no ievades datu īpašībām.

Lineārās laika šķirošanas priekšrocības

Lineārā laika šķirošanas algoritmi, piemēram, skaitliskā šķirošana, konkrētos scenārijos piedāvā vairākas priekšrocības.

Efektīva lieliem ievades izmēriem:Lineārā laika šķirošanas algoritmu laika sarežģītība ir O(n), kas nozīmē, ka darbības laiks lineāri palielinās līdz ar ievades lielumu. Tas padara tos ļoti efektīvus lielām datu kopām salīdzinājumā ar uz salīdzināšanu balstītiem šķirošanas algoritmiem, piemēram, ātrās kārtošanas vai sapludināšanas algoritmiem, kuru laika sarežģītība parasti ir O(n log n).Nav salīdzināšanas darbību:Lineārā laika šķirošanas algoritmi, piemēram, uzskaites kārtošana, nepaļaujas uz elementāru salīdzināšanu Tā vietā tie izmanto īpašus atribūtus vai informāciju par ievades elementiem, piemēram, to apjomu vai sadalījumu. Šī funkcija padara tos izdevīgus, ja salīdzināšanas izmaksas ir augstas, piemēram, sarežģītiem objektiem vai dārgām salīdzināšanas darbībām.Piemērotība noteiktām ievades īpašībām:Lineārā laika šķirošanas algoritmiem bieži ir noteiktas prasības vai pieņēmumi par ievades elementiem. Piemēram, lai aprēķinātu kārtošanas secību, iepriekš jāzina ievades elementu diapazons. Ja šie nosacījumi ir izpildīti, lineārā laika šķirošanas algoritmi var piedāvāt ievērojamas veiktspējas priekšrocības salīdzinājumā ar vispārējiem šķirošanas algoritmiem.Stabila šķirošana:Daudzi lineārā laika šķirošanas algoritmi, tostarp skaitļu un radix kārtošana, pēc būtības ir stabili. Konsekvence nozīmē, ka elementi ar dublētām atslēgām vai vērtībām saglabā relatīvo kārtību sakārtotajā izvadē. Tas var būt ļoti svarīgi, kārtojot objektus vai ierakstus ar vairākiem atribūtiem vai ja ir svarīgi saglabāt vienādas vērtības elementu sākotnējo secību.Lietošanas ērtums:Lineārās laika šķirošanas algoritmus, piemēram, uzskaitījumu šķirošanu, bieži ir salīdzinoši viegli ieviest, salīdzinot ar sarežģītākiem, uz salīdzināšanu balstītiem šķirošanas algoritmiem. Tos var būt vieglāk saprast un atkļūdot, padarot tos piemērotus situācijām, kurās ir vēlama vienkāršība un skaidrība.

Lineārās laika šķirošanas trūkumi

Lai gan lineārās plānošanas algoritmiem ir savas priekšrocības, tiem ir arī noteikti ierobežojumi un trūkumi:

Ierobežojošās ievades prasības:Lineārā laika šķirošanas algoritmiem bieži ir noteiktas prasības vai pieņēmumi par ievades elementiem. Piemēram, lai aprēķinātu kārtošanas secību, iepriekš jāzina ievades elementu diapazons. Šis ierobežojums ierobežo to piemērojamību situācijās, kad šie nosacījumi ir izpildīti. Atmiņas prasības var kļūt nepraktiskas vai pārsniegt pieejamos resursus, ja diapazons ir plašs vai nezināms.Papildu telpas prasības:Dažiem lineārās laika šķirošanas algoritmiem, piemēram, skaitliskajai kārtošanai, ir nepieciešama papildu vieta citu masīvu vai datu struktūru glabāšanai. Nepieciešamā vieta bieži vien ir proporcionāla ievades elementu skaitam. Tas var būt trūkums, ja atmiņas lietojums ir problēma, it īpaši, ja tiek izmantotas lielas datu kopas vai ierobežoti atmiņas resursi.Daudzpusības trūkums:Lineārā laika šķirošanas algoritmi ir specializēti algoritmi, kas izstrādāti konkrētiem scenārijiem vai ierobežojumiem. Tiem var būt jābūt piemērotākiem un efektīvākiem vispārīgiem kārtošanas uzdevumiem vai dažādiem ievades sadalījumiem. Uz salīdzinājumu balstīti šķirošanas algoritmi, piemēram, ātrā kārtošana vai sapludināšana, ir daudzpusīgāki un var apstrādāt plašāku ievades diapazonu.Neefektīvi maziem diapazoniem vai retiem datiem:Lineārā laika šķirošanas algoritmi, piemēram, uzskaitīšana, ir visefektīvākie, ja ievades elementu diapazons ir mazs un blīvi sadalīts. Ja diapazons ir plašs vai dati ir maz (t.i., tikai dažas atšķirīgas vērtības), algoritms var ietaupīt laiku un pūles, apstrādājot tukšas vai reti apdzīvotas ievades diapazona daļas.Tikai konkrētiem datu veidiem:Lineārā laika kārtošanas algoritmi, piemēram, uzskaites kārtošana, galvenokārt ir paredzēti nenegatīvu veselu skaitļu vai atslēgas vērtību objektu kārtošanai. Tie var nebūt piemēroti citu datu tipu, piemēram, peldošā komata skaitļu, virkņu vai sarežģītu datu struktūru kārtošanai. Lineārā laika šķirošanas algoritmu pielāgošana dažādu datu tipu vai pielāgotu salīdzināšanas funkciju apstrādei var prasīt papildu priekšapstrādi vai modifikācijas.

Izvēloties šķirošanas algoritmu, ir svarīgi rūpīgi apsvērt ievades datu specifiku un šķirošanas problēmas prasības. Lai gan lineārās plānošanas algoritmi piedāvā priekšrocības konkrētos scenārijos, tie tikai dažreiz ir vispiemērotākā vai efektīvākā izvēle.

Lineārā laika šķirošanas algoritmu pielietojumi

Lineārā laika šķirošanas algoritmi ir efektīvi, un tiem ir daudz pielietojumu dažādās jomās. Šeit ir daži tipiski lineārās laika secības lietojumi:

Maza diapazona veselu skaitļu kārtošana:Lineārā laika šķirošanas algoritmi, piemēram, skaitīšanas kārtošana un kārtošana ar radiksi, ir ideāli piemēroti veselu skaitļu masīvu kārtošanai, ja vērtību diapazons ir Šie algoritmi panāk lineāro laika sarežģītību, izdarot pieņēmumus par ievades datiem, ļaujot tiem apiet uz salīdzināšanu balstītu kārtošanu.Virknes šķirošana:Lineāro laika šķirošanas algoritmus var izmantot arī, lai efektīvi kārtotu virknes. Izmantojot virkņu unikālas īpašības, piemēram, to garumu vai rakstzīmes, algoritmi, piemēram, Radix Sort, var panākt lineāru laika sarežģītību, kārtojot virknes.Datu bāzes funkcijas:Kārtošana ir būtiska funkcija Lineārā laika šķirošanas algoritmi var efektīvi kārtot lielas datu kopas, pamatojoties uz konkrētām kolonnām vai laukiem. Tas nodrošina ātrāku vaicājumu apstrādi un labāku datu bāzes darbību veiktspēju.Histogrammu izveide:Histogrammas ir būtiskas dažādiem statistikas un datu analīzes uzdevumiem. Lineārā laika šķirošanas algoritmi, piemēram, skaitliskā šķirošana, var ģenerēt histogrammas, efektīvi saskaitot elementu sastopamības datu kopā.Ārējā šķirošana:Ārējā šķirošanas tehnika tiek izmantota gadījumos, kad dati nevar pilnībā ietilpt atmiņā. Lineārā laika šķirošanas algoritmi, piemēram, External Radix Sort vai External Counting Sort, var efektīvi kārtot lielas datu kopas, kas saglabātas diskā vai citās ārējās atmiņas ierīcēs.Pasākumu plānošana:Lineārā laika šķirošanas algoritmi var ieplānot notikumus, pamatojoties uz to sākuma vai beigu laiku. Notikumu kārtošana augošā secībā atvieglo konfliktu, periodu pārklāšanās vai nākamā pieejamā perioda atrašanu.Žurnāla failu analīze:Žurnāla failu analīze ir izplatīts uzdevums sistēmas administrēšanā un atkļūdošanā. Lineāro laika šķirošanas algoritmus var izmantot, lai kārtotu žurnālus, pamatojoties uz laikspiedoliem, tādējādi atvieglojot modeļu, anomāliju identificēšanu vai konkrētu notikumu meklēšanu.Datu saspiešana:Šķirošanai ir būtiska loma dažādās datu saspiešanas metodēs. Algoritmi, piemēram, Burrows-Wheeler Transform (BWT) vai Move-To-Front Transform (MTF), paļaujas uz lineāro laika secību, lai pārkārtotu datus, lai uzlabotu saspiešanas efektivitāti. Šie ir tikai daži lineārās laika šķirošanas algoritmu lietojumu piemēri.

Lineārā laika šķirošanas ieviešana programmā C++

Šeit ir programmas piemērs, kas ievieš skaitīšanas kārtošanu, kas ir lineāra laika šķirošanas algoritms:

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

Tas norāda, ka ievades masīvs ir sakārtots augošā secībā, izmantojot skaitīšanas kārtošanas algoritmu, kā rezultātā iegūts sakārtotais masīvs [1, 2, 2, 3, 3, 4, 8].

Šajā C++ programmā skaitīšanas kārtošanas funkcija izmanto atsauci uz vektoru arr un palaiž skaitīšanas kārtošanas rutīnu. Tas atrod tabulas maksimālo vērtību, lai noteiktu darblapas izmēru. Pēc tam tā saskaita katra elementa rašanos un aprēķina darblapas prefiksa summu. Pēc tam tas izveido rezultāta vektoru un sakārto elementus atbilstoši darblapai. Visbeidzot, tas kopē sakārtotos elementus atpakaļ sākotnējā masīvā. Primārajā funkcijā piemēru masīvs {4, 2, 2, 8, 3, 3, 1} tiek sakārtots pēc uzskaitījuma kārtošanas algoritma un tiek izdrukāts kā sakārtota matrica. Ņemiet vērā, ka programma izmanto bibliotēkas, lai strādātu ar vektoriem un atrastu maksimālo masīva elementu, izmantojot funkciju max_element.