TechCodeview

Įvadas

Rūšiavimas yra esminė informatikos operacija, apimanti elementų išdėstymą tam tikra tvarka, pavyzdžiui, skaitine arba abėcėlės tvarka. Sukurti įvairūs rūšiavimo algoritmai, kurių kiekvienas turi laiko ir efektyvumo rodiklius. Linijinis laiko rūšiavimas yra rūšiavimo algoritmų poaibis, turintis didelį pranašumą: jie gali rūšiuoti tam tikrą elementų rinkinį tiesiniu laiku, vykdymo laikas tiesiškai didėja atsižvelgiant į įvesties dydį.

Geriausiai žinomas linijinio laiko rūšiavimo algoritmas yra rūšiavimas mažėjančia tvarka. Skaičiavimo rūšiavimas yra ypač efektyvus, kai žinomas įvesties elementų diapazonas ir palyginti mažas. Tai pašalina būtinybę lyginti elementus – tai pagrindinė daugelio kitų rūšiavimo algoritmų daug laiko reikalaujanti operacija. Naudojant įvesties srities žinias, skaičiavimo rūšiavimas pasiekia linijinį laiko sudėtingumą. Skaičių rūšiavimas pirmiausia nuskaito įvesties masyvą, kad nustatytų kiekvieno elemento skaičių. Tada jis naudoja šiuos skaičius, kad apskaičiuotų teisingas elementų pozicijas užsakytų rezultatų lentelėje. Algoritmas susideda iš šių žingsnių:

1. Norėdami nustatyti diapazoną, nustatykite mažiausią ir didžiausią įvesties masyvo reikšmes.
2. Sukurkite darbalapį, inicijuotą diapazono dydžiu ir nuliais.
3. Pakartokite įvesties masyvą ir padidinkite kiekvieną rastą elementą.
4. Modifikuokite darbalapį apskaičiuodami bendrą bendrą sumą, kad gautumėte teisingas kiekvieno elemento pozicijas.
5. Sukurkite tokio pat dydžio išvesties masyvą kaip įvesties masyvas.
6. Dar kartą perkelkite įvesties masyvą, įdėdami kiekvieną elementą į teisingą padėtį išvesties masyve pagal darbalapį.
7. Rezultatų lentelėje dabar yra surūšiuoti elementai.

Pagrindinis mažėjančio rūšiavimo pranašumas yra tas, kad jis pasiekia tiesinį laiko sudėtingumą O (n), todėl jis yra labai efektyvus dideliems įvesties dydžiams. Tačiau jo pritaikymas apsiriboja scenarijais, kai įvesties elementų pasirinkimas yra žinomas iš anksto ir palyginti mažas.

Svarbu pažymėti, kad kitų rūšiavimo algoritmų, tokių kaip greitas rūšiavimas arba sujungimas, laiko sudėtingumas paprastai yra O (n log n), kuris laikomas efektyviu daugeliui praktinių pritaikymų. Linijinio laiko rūšiavimo algoritmai, tokie kaip skaitmeninis rūšiavimas, yra alternatyva, kai tam tikri įvesties apribojimai arba savybės leidžia naudoti tiesinį laiko sudėtingumą.

Istorija

Linijinio laiko rūšiavimo algoritmai turi turtingą kompiuterių mokslo istoriją. Linijinės laiko tvarkos raidą galima atsekti iki XX amžiaus vidurio, o mokslininkų ir matematikų indėlis buvo reikšmingas. Vienas iš ankstyviausių linijinio laiko rūšiavimo algoritmų yra rūšiavimas pagal segmentą, kurį 1954 m. pasiūlė Haroldas H. Sewardas. Rūšiuojant pagal segmentą įvesties elementai padalijami į baigtinį segmentų skaičių ir tada rūšiuojami kiekvienas segmentas atskirai. Šis algoritmas turi linijinį laiko sudėtingumą, jei įvesties elementų pasiskirstymas yra gana tolygus.

1959 m. Kennethas E. Iversonas pristatė radikso algoritmą, kuris pasiekia tiesinį laiko sudėtingumą. Radix rūšiuoja elementus pagal jų skaičių arba ženklus nuo mažiausiai reikšmingo iki reikšmingiausio. Elementams rūšiuoti kiekvienoje skaitmens vietoje naudojami patikimi rūšiavimo algoritmai, pvz., skaitmeninis arba segmentinis rūšiavimas. Radix rūšiavimas išpopuliarėjo perfokortelių ir ankstyvųjų kompiuterių sistemų eroje. Tačiau geriausiai žinomas linijinio laiko rūšiavimo algoritmas yra išvardijimas, kurį 1954 m. pristatė Haroldas H. Sewardas ir Peteris Eliasas, o vėliau savarankiškai iš naujo atrado Haroldas H. 'Bobby' Johnsonas 1961 m. Skaitmeniniam rūšiavimui buvo skiriamas didelis dėmesys.

Tai ypač efektyvu, kai žinomas ir palyginti mažas įvesties elementų diapazonas. Linijinio laiko rūšiavimo istorija tęsėsi kuriant kitus specializuotus algoritmus. Pavyzdžiui, 1987 m. Hananas Sametas pasiūlė dvejetainį skirstinio medžio rūšiavimą – linijinį laiko rūšiavimo algoritmą daugiamačiams duomenims. Bėgant metams mokslininkai toliau tyrinėjo ir tobulino linijinius planavimo algoritmus, sutelkdami dėmesį į konkrečius scenarijus ir apribojimus. Nors algoritmai, tokie kaip greitasis rūšiavimas ir sujungimas, yra plačiau naudojami dėl jų efektyvumo daugiau scenarijų, linijinio laiko rūšiavimo algoritmai suteikia vertingų alternatyvų, kai tam tikros aplinkybės leidžia išnaudoti tiesinio laiko sudėtingumą. Apskritai linijinio laiko rūšiavimo istorijai būdinga ieškoti efektyvių algoritmų, galinčių surūšiuoti didelius duomenų rinkinius tiesiniu laiku, įveikiant palyginimu pagrįstų rūšiavimo algoritmų apribojimus. Įvairių tyrinėtojų indėlis atvėrė kelią šių specializuotų rūšiavimo metodų kūrimui ir supratimui.

Linijinio laiko rūšiavimo tipai

Yra keli skirtingi linijinio laiko rūšiavimo algoritmai. Du pagrindiniai tipai yra skaičiavimu pagrįsti algoritmai ir radiksu pagrįsti algoritmai. Čia pateikiami dažniausiai naudojami linijinio laiko rūšiavimo algoritmai, klasifikuojami pagal šiuos tipus:

Skaičiavimu pagrįsti algoritmai

Rūšiavimas pagal skaičiavimą:Skaičiavimu pagrįstas yra nelyginamojo rūšiavimo algoritmas. Jis skaičiuoja kiekvieno konkretaus elemento atsiradimą įvesties masyve ir naudoja šią informaciją, kad nustatytų teisingą kiekvieno elemento padėtį surūšiuotame išvesties masyve. Skaičiavimu pagrįstas rūšiavimas daro prielaidą, kad įvesties elementai yra sveikieji skaičiai arba juos galima pridėti prie sveikųjų skaičių.

Radiksu pagrįsti algoritmai

Rūšiuoti radiksą:Radix Sort yra ne palyginimu pagrįstas rūšiavimo algoritmas, kuris rūšiuoja elementus pagal jų skaičius arba simbolius. Jis skaičiuoja kiekvieną elementų skaičių arba ženklą nuo mažiausiai reikšmingo skaičiaus iki reikšmingiausio. Radikalioji rūšiavimo priemonė daro prielaidą, kad įvesties elementai yra sveikieji skaičiai arba eilutės.Rūšiuoti pagal kaušą:„Bucket Sort“ yra „Radix Sort“ variantas, skirstantis elementus į fiksuotas grupes pagal jų diapazoną arba pasiskirstymą. Kiekvienas segmentas rūšiuojamas atskirai, naudojant skirtingą rūšiavimo algoritmą arba rekursyvų rūšiavimą.MSD (labiausiai reikšmingas skaitmuo) radikso rūšiavimas:MSD Radix Sort yra radiksinio rūšiavimo variantas, kuris pradeda rūšiuoti elementus pagal jų reikšmingiausią. Jis rekursyviai padalija elementus į pogrupius pagal esamo skaičiaus reikšmę ir kiekvienam pogrupiui taiko MSD Radix Sort, kol bus suskaičiuoti visi skaičiai.LSD (mažiausiai reikšmingo skaitmens) raidžių rūšiavimas:LSD Radix Sort yra dar vienas variantas, kuris pradeda rūšiuoti elementus pagal jų mažiausiai reikšmingą. Jis rekursyviai rūšiuoja elementus pagal kiekvieną skaičių nuo tolimiausio dešiniojo iki kairiojo, o rezultatas yra surūšiuotas. Tiek skaičiavimu, tiek šaknine pagrįsti rūšiavimo algoritmai pasiekia tiesinį laiko sudėtingumą, išnaudodami konkrečias įvesties elementų savybes, tokias kaip jų diapazonas arba vaizdavimo struktūra (pvz., skaičiai ar simboliai). Tačiau jų pritaikymas gali skirtis priklausomai nuo įvesties duomenų savybių.

Linijinio laiko rūšiavimo privalumai

Linijinio laiko rūšiavimo algoritmai, pvz., skaitmeninis rūšiavimas, tam tikruose scenarijuose turi keletą pranašumų.

Veiksmingas dideliems įvesties dydžiams:Linijinio laiko rūšiavimo algoritmų sudėtingumas laike yra O(n), o tai reiškia, kad veikimo laikas tiesiškai didėja didėjant įvesties dydžiui. Dėl to jie yra labai veiksmingi dideliems duomenų rinkiniams, palyginti su palyginimu pagrįstais rūšiavimo algoritmais, tokiais kaip greitojo rūšiavimo arba sujungimo algoritmai, kurių laiko sudėtingumas paprastai yra O(n log n).Jokių palyginimo operacijų:Linijinio laiko rūšiavimo algoritmai, tokie kaip išvardijimo rūšiavimas, nepasikliauja elementariu palyginimu. Vietoj to jie naudoja konkrečius atributus arba informaciją apie įvesties elementus, pvz., jų apimtį ar pasiskirstymą. Dėl šios savybės jie yra naudingi, kai palyginimo kaina yra didelė, pvz., sudėtingiems objektams ar brangioms palyginimo operacijoms.Tinkamumas konkrečioms įvesties savybėms:Linijinio laiko rūšiavimo algoritmai dažnai turi specifinius reikalavimus arba prielaidas dėl įvesties elementų. Pavyzdžiui, norėdami apskaičiuoti rūšiavimo tvarką, turite iš anksto žinoti įvesties elementų diapazoną. Kai šios sąlygos yra įvykdytos, linijinio laiko rūšiavimo algoritmai gali pasiūlyti reikšmingų pranašumų, palyginti su bendraisiais rūšiavimo algoritmais.Stabilus rūšiavimas:Daugelis linijinio laiko rūšiavimo algoritmų, įskaitant skaitmeninį ir radiksinį rūšiavimą, iš esmės yra stabilūs. Nuoseklumas reiškia, kad elementai su pasikartojančiais raktais arba reikšmėmis išlaiko santykinę tvarką surūšiuotoje išvestyje. Tai gali būti labai svarbu rūšiuojant objektus ar įrašus su keliais atributais arba kai būtina išsaugoti pirminę vienodos vertės elementų tvarką.Naudojimo paprastumas:Linijinio laiko rūšiavimo algoritmus, tokius kaip išvardijimo rūšiavimas, dažnai yra gana lengva įdiegti, palyginti su sudėtingesniais palyginimu pagrįstais rūšiavimo algoritmais. Juos gali būti lengviau suprasti ir derinti, todėl jie tinka situacijose, kuriose norisi paprastumo ir aiškumo.

Linijinio laiko rūšiavimo trūkumai

Nors linijiniai planavimo algoritmai turi savo privalumų, jie taip pat turi tam tikrų apribojimų ir trūkumų:

Ribojantys įvesties reikalavimai:Linijinio laiko rūšiavimo algoritmai dažnai turi specifinius reikalavimus arba prielaidas dėl įvesties elementų. Pavyzdžiui, norėdami apskaičiuoti rūšiavimo tvarką, turite iš anksto žinoti įvesties elementų diapazoną. Šis apribojimas riboja jų taikymą situacijose, kai šios sąlygos yra įvykdytos. Atminties reikalavimai gali tapti nepraktiški arba viršyti turimus išteklius, jei diapazonas yra didelis arba nežinomas.Papildomi erdvės reikalavimai:Kai kuriems linijinio laiko rūšiavimo algoritmams, pvz., skaitmeniniam rūšiavimui, reikia papildomos vietos kitiems masyvams ar duomenų struktūroms saugoti. Reikalinga erdvė dažnai yra proporcinga įvesties elementų skaičiui. Tai gali būti trūkumas, kai atminties naudojimas yra problema, ypač kai susiduriama su dideliais duomenų rinkiniais arba ribotais atminties ištekliais.Trūksta universalumo:Linijinio laiko rūšiavimo algoritmai yra specializuoti algoritmai, sukurti konkretiems scenarijams ar apribojimams. Jie gali būti tinkamesni ir efektyvesni bendroms rūšiavimo užduotims arba skirtingiems įvesties paskirstymams. Palyginimu pagrįsti rūšiavimo algoritmai, tokie kaip greitas rūšiavimas arba sujungimas, yra universalesni ir gali apdoroti platesnį įvesties diapazoną.Neefektyvus mažiems diapazonams arba negausiems duomenims:Linijinio laiko rūšiavimo algoritmai, tokie kaip surašymas, yra efektyviausi, kai įvesties elementų diapazonas yra mažas ir tankiai paskirstytas. Jei diapazonas yra platus arba duomenų nedaug (t. y. tik kelios skirtingos reikšmės), algoritmas gali sutaupyti laiko ir pastangų apdorojant tuščias arba retai apgyvendintas įvesties diapazono dalis.Apribota tam tikrais duomenų tipais:Linijinio laiko rūšiavimo algoritmai, tokie kaip išvardijimo rūšiavimas, pirmiausia yra skirti rūšiuoti neneigiamus sveikuosius skaičius arba raktinių reikšmių objektus. Jie gali būti netinkami rūšiuoti kitų tipų duomenis, pvz., slankiojo kablelio skaičius, eilutes ar sudėtingas duomenų struktūras. Pritaikant linijinio laiko rūšiavimo algoritmus, kad būtų galima apdoroti skirtingus duomenų tipus arba pasirinktines palyginimo funkcijas, gali prireikti papildomo išankstinio apdorojimo arba modifikacijų.

Renkantis rūšiavimo algoritmą, būtina atidžiai apsvarstyti įvesties duomenų specifiką ir rūšiavimo problemos reikalavimus. Nors linijiniai planavimo algoritmai teikia pranašumų tam tikrais atvejais, jie tik kartais yra tinkamiausias arba efektyviausias pasirinkimas.

Linijinio laiko rūšiavimo algoritmų taikymai

Linijinio laiko rūšiavimo algoritmai yra veiksmingi ir turi daug pritaikymų įvairiose srityse. Štai keletas tipiškų linijinės laiko tvarkos taikymo būdų:

Mažo diapazono sveikųjų skaičių rūšiavimas:Linijinio laiko rūšiavimo algoritmai, tokie kaip skaičiavimo rūšiavimas ir rūšiavimas pagal radiksą, idealiai tinka rūšiuoti sveikųjų skaičių masyvus, kai reikšmių diapazonas yra Šie algoritmai pasiekia linijinį laiko sudėtingumą darydami prielaidas apie įvesties duomenis, leidžiančius apeiti palyginimu pagrįstą rūšiavimą.Eilučių rūšiavimas:Linijinio laiko rūšiavimo algoritmai taip pat gali būti taikomi norint efektyviai rūšiuoti eilutes. Atsižvelgdami į unikalias eilučių savybes, pvz., jų ilgį ar simbolius, tokie algoritmai kaip Radix Sort gali pasiekti linijinį laiko sudėtingumą rūšiuodami eilutes.Duomenų bazės funkcijos:Rūšiavimas yra esminė linijinio laiko rūšiavimo algoritmų funkcija, galinti efektyviai rūšiuoti didelius duomenų rinkinius pagal konkrečius stulpelius ar laukus. Tai leidžia greičiau apdoroti užklausas ir geriau atlikti duomenų bazės operacijas.Histogramų kūrimas:Histogramos yra būtinos įvairioms statistinėms ir duomenų analizės užduotims atlikti. Linijinio laiko rūšiavimo algoritmai, tokie kaip skaitmeninis rūšiavimas, gali generuoti histogramas efektyviai skaičiuodami elementų pasireiškimus duomenų rinkinyje.Išorinis rūšiavimas:Išorinis rūšiavimo metodas naudojamas tais atvejais, kai duomenys negali visiškai tilpti į atmintį. Linijinio laiko rūšiavimo algoritmai, tokie kaip išorinis radikso rūšiavimas arba išorinis skaičiavimo rūšiavimas, gali efektyviai rūšiuoti didelius duomenų rinkinius, saugomus diske ar kituose išoriniuose saugojimo įrenginiuose.Renginio tvarkaraštis:Linijinio laiko rūšiavimo algoritmai gali planuoti įvykius pagal jų pradžios arba pabaigos laiką. Rūšiuojant įvykius didėjimo tvarka, lengva nustatyti konfliktus, persidengiančius laikotarpius arba rasti kitą galimą laikotarpį.Žurnalo failų analizė:Žurnalo failų analizė yra įprasta sistemos administravimo ir derinimo užduotis. Linijinio laiko rūšiavimo algoritmus galima naudoti rūšiuojant žurnalus pagal laiko žymas, todėl lengviau nustatyti šablonus, anomalijas arba ieškoti konkrečių įvykių.Duomenų suspaudimas:Rūšiavimas atlieka esminį vaidmenį įvairiose duomenų glaudinimo technikose. Algoritmai, tokie kaip Burrows-Wheeler Transform (BWT) arba Move-To-Front Transform (MTF), remiasi linijine laiko tvarka, kad pertvarkytų duomenis ir pagerintų suspaudimo efektyvumą. Tai tik keli linijinio laiko rūšiavimo algoritmų taikymo pavyzdžiai.

Linijinio laiko rūšiavimo įgyvendinimas C++

Štai programos, įgyvendinančios skaičiavimo rūšiavimą, kuris yra linijinio laiko rūšiavimo algoritmas, pavyzdys:

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

Tai rodo, kad įvesties masyvas buvo surūšiuotas didėjančia tvarka, naudojant skaičiavimo rūšiavimo algoritmą, todėl surūšiuotas masyvas [1, 2, 2, 3, 3, 4, 8].

Šioje C++ programoje skaičiavimo rūšiavimo funkcija atsižvelgia į vektorių arr ir vykdo skaičiavimo rūšiavimo tvarką. Jis randa didžiausią lentelės reikšmę, kad nustatytų darbalapio dydį. Tada jis skaičiuoja kiekvieno elemento atsiradimą ir apskaičiuoja darbalapio priešdėlio sumą. Tada jis sukuria rezultato vektorių ir sutvarko elementus pagal darbalapį. Galiausiai jis nukopijuoja surūšiuotus elementus atgal į pradinį masyvą. Pirminėje funkcijoje pavyzdinis masyvas {4, 2, 2, 8, 3, 3, 1} surūšiuojamas pagal sąrašo rūšiavimo algoritmą ir atspausdinamas kaip surūšiuota matrica. Atminkite, kad programa naudoja bibliotekas, kad galėtų dirbti su vektoriais ir rasti maksimalų masyvo elementą, naudodama funkciją max_element.