Johdanto

Lajittelu on tietojenkäsittelytieteen olennainen toimenpide, joka sisältää elementtien järjestämisen tiettyyn järjestykseen, kuten numeeriseen tai aakkosjärjestykseen. On kehitetty erilaisia ​​lajittelualgoritmeja, joista jokaisessa on aika- ja tehokkuusindikaattorit. Lineaarinen aikalajittelu on lajittelualgoritmien osajoukko, jolla on merkittävä etu: ne voivat lajitella tietyn joukon elementtejä lineaarisessa ajassa, suoritusaika kasvaa lineaarisesti syötteen koon mukaan.

int merkkijonoon java

Tunnetuin lineaarinen aikalajittelualgoritmi on laskeva lajittelu. Laskennallinen lajittelu on erityisen tehokasta, kun syöteelementtien valikoima on tunnettu ja suhteellisen pieni. Tämä poistaa tarpeen vertailla elementtejä, mikä on tärkein aikaa vievä toimenpide monissa muissa lajittelualgoritmeissa. Syöttöaluetietoa käyttämällä laskennallinen lajittelu saavuttaa lineaarisen aikamonimutkaisuuden. Numeerinen lajittelu skannaa ensin syötetaulukon määrittääkseen kunkin elementin määrän. Sitten se laskee näiden numeroiden avulla elementtien oikeat sijainnit järjestetyssä tulostaulukossa. Algoritmi koostuu seuraavista vaiheista:

1. Voit määrittää alueen määrittämällä syöttötaulukon minimi- ja enimmäisarvot.
2. Luo laskentataulukko, joka on alustettu alueen koolla ja nollalla.
3. Iteroi syöttötaulukon yli ja lisää jokaista löydettyä elementtiä.
4. Muokkaa laskentataulukkoa laskemalla kumulatiivinen kokonaissumma saadaksesi kunkin elementin oikeat paikat.
5. Luo tulotaulukko, joka on samankokoinen kuin syöttötaulukko.
6. Siirrä syöttötaulukkoa uudelleen ja sijoita jokainen elementti oikeaan kohtaan tulostaulukossa laskentataulukon perusteella.
7. Tulostaulukko sisältää nyt lajiteltuja elementtejä.

Laskevan lajittelun tärkein etu on, että se saavuttaa O(n) lineaarisen aikakompleksisuuden, mikä tekee siitä erittäin tehokkaan suurille syötekokoille. Sen sovellettavuus rajoittuu kuitenkin skenaarioihin, joissa syöteelementtien valinta on tiedossa etukäteen ja suhteellisen pieni.

On tärkeää huomata, että muiden lajittelualgoritmien, kuten pikalajittelun tai yhdistämisen, aikamonimutkaisuus on tyypillisesti O(n log n), jota pidetään tehokkaana monissa käytännön sovelluksissa. Lineaariset aikalajittelualgoritmit, kuten numeerinen lajittelu, tarjoavat vaihtoehdon, kun tietyt syötteen rajoitukset tai ominaisuudet sallivat lineaarisen aikamonimutkaisuuden käytön.

Historia

Lineaarisilla aikalajittelualgoritmeilla on rikas historia tietojenkäsittelytieteessä. Lineaarisen aikajärjestyksen kehittyminen voidaan jäljittää 1900-luvun puoliväliin asti, ja tiedemiesten ja matemaatikoiden panos oli merkittävä. Yksi varhaisimmista lineaarisista aikalajittelualgoritmeista on Harold H. Sewardin vuonna 1954 ehdottama sämpärilajittelu. Sämpärilajittelu jakaa syöteelementit rajalliseen määrään sämpylöitä ja lajittelee sitten jokaisen sämpön erikseen. Tällä algoritmilla on lineaarinen aikamonimutkaisuus, jos syöteelementtien jakautuminen on suhteellisen tasaista.

Vuonna 1959 Kenneth E. Iverson esitteli kantaluku-algoritmin, joka saavuttaa lineaarisen aikamonimutkaisuuden. Radix lajittelee elementit niiden numeroiden tai etumerkkien mukaan vähiten merkitsevistä merkittävimpiin. Se käyttää vankkoja lajittelualgoritmeja, kuten numeerista tai kauhalajittelua, lajitellakseen elementit kussakin numeropaikassa. Radix-lajittelusta tuli suosittu reikäkorttien ja varhaisten tietokonejärjestelmien aikakaudella. Tunnetuin lineaarinen aikalajittelualgoritmi on kuitenkin luettelointi, jonka Harold H. Seward ja Peter Elias esittelivät vuonna 1954 ja jonka Harold H. 'Bobby' Johnson löysi myöhemmin itsenäisesti uudelleen vuonna 1961. Numeerinen lajittelu on saanut paljon huomiota.

Tämä on erityisen tehokasta, kun syöttöelementtien valikoima on tunnettu ja suhteellisen pieni. Lineaarisen aikalajittelun historia jatkui muiden erikoisalgoritmien kehittämisen myötä. Esimerkiksi vuonna 1987 Hanan Samet ehdotti binäärijakaumapuun lajittelua, lineaarista aikalajittelualgoritmia moniulotteiselle datalle. Vuosien mittaan tutkijat ovat jatkaneet lineaaristen aikataulutusalgoritmien tutkimista ja parantamista keskittyen tiettyihin skenaarioihin ja rajoituksiin. Vaikka algoritmeja, kuten pikalajittelu ja yhdistäminen, käytetään laajemmin niiden tehokkuuden vuoksi useammissa skenaarioissa, lineaariajan lajittelualgoritmit tarjoavat arvokkaita vaihtoehtoja, kun tietyt olosuhteet sallivat lineaarisen ajan monimutkaisuuden hyödyntämisen. Yleisesti ottaen lineaarisen aikalajittelun historialle on ominaista sellaisten tehokkaiden algoritmien etsiminen, jotka pystyvät lajittelemaan suuria tietojoukkoja lineaarisessa ajassa ylittäen vertailupohjaisten lajittelualgoritmien rajoitukset. Eri tutkijoiden panokset tasoittivat tietä näiden erikoistuneiden lajittelutekniikoiden kehittämiselle ja ymmärtämiselle.

Lineaarisen aikalajittelun tyypit

On olemassa useita erilaisia ​​lineaarisia aikalajittelualgoritmeja. Kaksi päätyyppiä ovat laskentaan perustuvat algoritmit ja kantalukupohjaiset algoritmit. Tässä ovat yleisimmät lineaariset aikalajittelualgoritmit, jotka on luokiteltu seuraavien tyyppien perusteella:

Laskentapohjaiset algoritmit

Laskentaperusteinen lajittelu:Counting-Based on ei-vertaileva lajittelualgoritmi. Se laskee jokaisen tietyn elementin esiintymisen syöttötaulukossa ja käyttää näitä tietoja määrittääkseen kunkin elementin oikean sijainnin lajitetussa tulostaulukossa. Laskentaperusteinen lajittelu olettaa, että syöteelementit ovat kokonaislukuja tai ne voidaan lisätä kokonaislukuihin.

Radix-pohjaiset algoritmit

Lajittele kanta:Radix Sort on ei-vertailupohjainen lajittelualgoritmi, joka lajittelee elementit numeroiden tai merkkien mukaan. Se laskee jokaisen luvun tai merkin elementeissä vähiten merkitsevästä numerosta merkittävimpään. Radikaalilajittelu olettaa, että syöteelementit ovat kokonaislukuja tai merkkijonoja.Kauhan lajittelu:Bucket Sort on muunnelma Radix Sortista, joka jakaa elementit kiinteisiin ryhmiin niiden alueen tai jakauman perusteella. Jokainen segmentti lajitellaan erikseen käyttämällä erilaista lajittelualgoritmia tai rekursiivisesti bin-lajittelua.MSD (Most Significant Digit) -radiksilajittelu:MSD Radix Sort on kantalukulajittelun muunnelma, joka aloittaa elementtien lajittelun niiden merkittävimmän perusteella. Se jakaa elementit rekursiivisesti alaryhmiin nykyisen luvun arvon perusteella ja soveltaa MSD Radix Sort -toimintoa jokaiseen alaryhmään, kunnes kaikki luvut on laskettu.LSD (Least Significant Digit) -radiksilajittelu:LSD Radix Sort on toinen variantti, joka alkaa lajitella elementtejä niiden vähiten merkitsevien perusteella. Se lajittelee elementit rekursiivisesti kunkin numeron perusteella oikealta äärimmäiseltä vasemmalle, jolloin saadaan lajiteltu tulos. Sekä laskentaperusteiset että juuripohjaiset lajittelualgoritmit saavuttavat lineaarisen aikamonimutkaisuuden hyödyntämällä syöteelementtien tiettyjä ominaisuuksia, kuten niiden aluetta tai esitysrakennetta (esim. numeroita tai merkkejä). Niiden sovellettavuus voi kuitenkin vaihdella syöttötietojen ominaisuuksien mukaan.

Lineaarisen aikalajittelun edut

Lineaariset aikalajittelualgoritmit, kuten numeerinen lajittelu, tarjoavat useita etuja tietyissä skenaarioissa.

Tehokas suurille tulokokoille:Lineaaristen aikalajittelualgoritmien aikamonimutkaisuus on O(n), mikä tarkoittaa, että ajoaika kasvaa lineaarisesti syötteen koon mukaan. Tämä tekee niistä erittäin tehokkaita suurille tietojoukoille verrattuna vertailupohjaisiin lajittelualgoritmeihin, kuten pikalajittelu- tai yhdistämisalgoritmeihin, joiden aikamonimutkaisuus on tyypillisesti O(n log n).Ei vertailutoimintoja:Lineaariaikaiset lajittelualgoritmit, kuten numeraatiolajittelu, eivät luota alkeelliseen vertailuun, vaan ne käyttävät tiettyjä attribuutteja tai tietoja syöteelementeistä, kuten niiden laajuudesta tai jakautumisesta. Tämä ominaisuus tekee niistä edullisia, kun vertailukustannukset ovat korkeat, kuten monimutkaisten kohteiden tai kalliiden vertailuoperaatioiden yhteydessä.Soveltuvuus tiettyihin syöttöominaisuuksiin:Lineaarisella aikalajittelualgoritmeilla on usein erityisiä vaatimuksia tai oletuksia syöteelementeistä. Esimerkiksi lajittelujärjestyksen laskemiseksi sinun on tiedettävä syöttöelementtien alue etukäteen. Kun nämä ehdot täyttyvät, lineaariset aikalajittelualgoritmit voivat tarjota merkittäviä suorituskykyetuja yleisiin lajittelualgoritmeihin verrattuna.Vakaa lajittelu:Monet lineaarisen ajan lajittelualgoritmit, mukaan lukien numeerinen ja kantalukulajittelu, ovat luonnostaan ​​vakaita. Johdonmukaisuus tarkoittaa, että elementit, joilla on päällekkäisiä avaimia tai arvoja, säilyttävät suhteellisen järjestyksen lajitetussa tulosteessa. Tämä voi olla ratkaisevaa lajitettaessa objekteja tai tietueita, joissa on useita attribuutteja, tai kun samanarvoisten elementtien alkuperäisen järjestyksen säilyttäminen on välttämätöntä.Helppokäyttöisyys:Lineaariset aikalajittelualgoritmit, kuten luettelointilajittelu, ovat usein suhteellisen helppoja toteuttaa verrattuna monimutkaisempiin vertailupohjaisiin lajittelualgoritmeihin. Niitä voi olla helpompi ymmärtää ja viankorjaus, mikä tekee niistä sopivia tilanteisiin, joissa halutaan yksinkertaisuutta ja selkeyttä.

Lineaarisen aikalajittelun haitat

Vaikka lineaarisilla ajoitusalgoritmeilla on etunsa, niillä on myös tiettyjä rajoituksia ja haittoja:

Rajoittavat syöttövaatimukset:Lineaarisilla aikalajittelualgoritmeilla on usein erityisiä vaatimuksia tai oletuksia syöteelementeistä. Esimerkiksi lajittelujärjestyksen laskemiseksi sinun on tiedettävä syöttöelementtien alue etukäteen. Tämä rajoitus rajoittaa niiden soveltamisen tilanteisiin, joissa nämä ehdot täyttyvät. Muistivaatimukset voivat tulla epäkäytännöllisiksi tai ylittää käytettävissä olevat resurssit, jos valikoima on laaja tai tuntematon.Lisätilavaatimukset:Jotkut lineaariset aikalajittelualgoritmit, kuten numeerinen lajittelu, vaativat lisätilaa muiden taulukoiden tai tietorakenteiden tallentamiseen. Tarvittava tila on usein verrannollinen syöteelementtien määrään. Tämä voi olla haitta, kun muistin käyttö on ongelma, varsinkin kun käsitellään suuria tietojoukkoja tai rajallisia muistiresursseja.Monipuolisuuden puute:Lineaariset aikalajittelualgoritmit ovat erikoisalgoritmeja, jotka on suunniteltu tiettyihin skenaarioihin tai rajoituksiin. Niiden on ehkä oltava sopivampia ja tehokkaampia yleisiin lajittelutehtäviin tai erilaisiin syöttöjakaumiin. Vertailupohjaiset lajittelualgoritmit, kuten pikalajittelu tai yhdistäminen, ovat monipuolisempia ja voivat käsitellä laajempaa syöttöaluetta.Tehoton pienille alueille tai harvalle datalle:Lineaariaikaiset lajittelualgoritmit, kuten luettelointi, ovat tehokkaimpia, kun syöteelementtien alue on pieni ja tiheästi jakautunut. Jos alue on laaja tai dataa on vähän (eli vain muutama eri arvo), algoritmi voi säästää aikaa ja vaivaa syötealueen tyhjien tai harvaan asuttujen osien käsittelyssä.Rajoitettu tiettyihin tietotyyppeihin:Lineaariaikaiset lajittelualgoritmit, kuten luettelointilajittelu, on ensisijaisesti suunniteltu lajittelemaan ei-negatiivisia kokonaislukuja tai avainarvoobjekteja. Ne eivät ehkä sovellu muiden tietotyyppien, kuten liukulukujen, merkkijonojen tai monimutkaisten tietorakenteiden lajitteluun. Lineaaristen aikalajittelualgoritmien mukauttaminen käsittelemään erilaisia ​​tietotyyppejä tai mukautettuja vertailutoimintoja saattaa vaatia lisäesikäsittelyä tai -muokkauksia.

Lajittelualgoritmia valittaessa on oleellista ottaa tarkasti huomioon syötetietojen erityispiirteet ja lajitteluongelman vaatimukset. Vaikka lineaariset ajoitusalgoritmit tarjoavat etuja tietyissä skenaarioissa, ne ovat vain toisinaan sopivin tai tehokkain valinta.

Lineaaristen aikalajittelualgoritmien sovellukset

Lineaariset aikalajittelualgoritmit ovat tehokkaita ja niillä on monia sovelluksia eri aloilla. Tässä on joitain tyypillisiä lineaarisen aikajärjestyksen sovelluksia:

Pienen alueen kokonaislukujen lajittelu:Lineaarisen aikalajittelualgoritmit, kuten count sort ja kantalukulajittelu, ovat ihanteellisia kokonaislukutaulukoiden lajitteluun, kun arvoalue on Nämä algoritmit saavuttavat lineaarisen aikamonimutkaisuuden tekemällä oletuksia syötetiedoista, jolloin ne voivat ohittaa vertailuun perustuvan lajittelun.Merkkijonojen lajittelu:Lineaarisia aikalajittelualgoritmeja voidaan soveltaa myös merkkijonojen tehokkaaseen lajitteluun. Ottamalla merkkijonojen ainutlaatuiset ominaisuudet, kuten niiden pituuden tai merkit, algoritmit, kuten Radix Sort, voivat saavuttaa lineaarisen aikamonimutkaisuuden merkkijonojen lajittelussa.Tietokantatoiminnot:Lajittelu on olennainen toiminto Lineaarisen aikalajittelun algoritmeilla, jotka voivat lajitella tehokkaasti suuria tietojoukkoja tiettyjen sarakkeiden tai kenttien perusteella. Tämä mahdollistaa nopeamman kyselyn käsittelyn ja paremman suorituskyvyn tietokantatoiminnoissa.Histogrammien luominen:Histogrammit ovat välttämättömiä erilaisissa tilasto- ja data-analyysitehtävissä. Lineaariset aikalajittelualgoritmit, kuten numeerinen lajittelu, voivat luoda histogrammeja laskemalla tehokkaasti elementtien esiintymiset tietojoukossa.Ulkoinen lajittelu:Ulkoista lajittelutekniikkaa käytetään skenaarioissa, joissa tiedot eivät mahdu kokonaan muistiin. Lineaariset aikalajittelualgoritmit, kuten External Radix Sort tai External Counting Sort, voivat lajitella tehokkaasti levylle tai muille ulkoisille tallennuslaitteille tallennettuja suuria tietojoukkoja.Tapahtuman aikataulu:Lineaariset aikalajittelualgoritmit voivat ajoittaa tapahtumia niiden alkamis- tai päättymisaikojen perusteella. Tapahtumien lajittelu nousevaan järjestykseen helpottaa ristiriitojen, päällekkäisten jaksojen tunnistamista tai seuraavan käytettävissä olevan jakson löytämistä.Lokitiedostojen analysointi:Lokitiedostojen analysointi on yleinen tehtävä järjestelmänhallinnassa ja virheenkorjauksessa. Lineaarisia aikalajittelualgoritmeja voidaan käyttää lokien lajitteluun aikaleimojen perusteella, mikä helpottaa kuvioiden, poikkeamien tunnistamista tai tiettyjen tapahtumien etsimistä.Tietojen pakkaus:Lajittelulla on olennainen rooli erilaisissa tiedonpakkaustekniikoissa. Algoritmit, kuten Burrows-Wheeler Transform (BWT) tai Move-To-Front Transform (MTF), luottavat lineaariseen aikajärjestykseen tietojen järjestämiseksi uudelleen pakkaustehokkuuden parantamiseksi. Nämä ovat vain muutamia esimerkkejä lineaarisen aikalajittelualgoritmien sovelluksista.

Lineaarisen aikalajittelun toteutus C++:ssa

Tässä on esimerkki ohjelmasta, joka toteuttaa Counting Sort -toiminnon, joka on lineaarinen aikalajittelualgoritmi:

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

Tämä osoittaa, että syötetaulukko on lajiteltu nousevaan järjestykseen käyttämällä Counting Sort -algoritmia, jolloin tuloksena on lajiteltu matriisi [1, 2, 2, 3, 3, 4, 8].

Tässä C++-ohjelmassa laskenta-lajittelutoiminto ottaa viittauksen vektoriin arr ja suorittaa laskevan lajittelurutiinin. Se löytää taulukon enimmäisarvon määrittääkseen laskentataulukon koon. Sitten se laskee kunkin elementin esiintymisen ja laskee laskentataulukon etuliitesumman. Sitten se luo tulosvektorin ja asettaa elementit laskentataulukon mukaiseen järjestykseen. Lopuksi se kopioi lajitellut elementit takaisin alkuperäiseen taulukkoon. Ensisijaisessa funktiossa esimerkkitaulukko {4, 2, 2, 8, 3, 3, 1} lajitellaan numeroinnin lajittelualgoritmin mukaan ja tulostetaan lajiteltuna matriisina. Huomaa, että ohjelma käyttää kirjastoja työskennelläkseen vektorien kanssa ja löytääkseen taulukon maksimielementin käyttämällä max_element-funktiota.