Introduksjon

Sortering er en essensiell operasjon i informatikk som involverer å ordne elementer i en bestemt rekkefølge, for eksempel numerisk eller alfabetisk rekkefølge. Det er utviklet ulike sorteringsalgoritmer, hver med tids- og effektivitetsindikatorer. Lineær tidssortering er en undergruppe av sorteringsalgoritmer med en betydelig fordel: de kan sortere et gitt sett med elementer i lineær tid, kjøretiden øker lineært med inngangsstørrelsen.

Den mest kjente lineære tidssorteringsalgoritmen er synkende sortering. Beregningsmessig sortering er spesielt effektiv når utvalget av inngangselementer er kjent og relativt lite. Dette eliminerer behovet for å sammenligne elementer, den viktigste tidkrevende operasjonen i mange andre sorteringsalgoritmer. Ved å bruke kunnskap om input-domene oppnår beregningsmessig sortering lineær tidskompleksitet. En numerisk sortering skanner først inngangsmatrisen for å bestemme antallet av hvert element. Den bruker deretter disse tallene til å beregne de riktige plasseringene til elementene i den ordnede resultattabellen. Algoritmen består av følgende trinn:

1. For å bestemme rekkevidden, identifiser minimums- og maksimumsverdiene til inngangsmatrisen.
2. Lag et regneark initialisert med områdestørrelsen og nuller.
3. Iterer over inndatamatrisen og øk hvert element som er funnet.
4. Endre regnearket ved å beregne den kumulative totalen for å få de riktige posisjonene for hvert element.
5. Opprett en utmatrise med samme størrelse som innmatningsmatrisen.
6. Flytt inndatamatrisen igjen, og plasser hvert element i riktig posisjon i utmatrisen basert på regnearket.
7. Resultattabellen inneholder nå sorterte elementer.

Hovedfordelen med synkende sortering er at den oppnår en lineær tidskompleksitet på O(n), noe som gjør den veldig effektiv for store inngangsstørrelser. Dens anvendelighet er imidlertid begrenset til scenarier der valget av input-elementer er kjent på forhånd og relativt lite.

Det er viktig å merke seg at andre sorteringsalgoritmer, for eksempel quicksort eller merge, typisk har en tidskompleksitet på O(n log n), som anses som effektiv for mange praktiske applikasjoner. Lineære tidssorteringsalgoritmer, for eksempel numerisk sortering, gir et alternativ når visse begrensninger eller egenskaper ved inngangen tillater bruk av lineær tidskompleksitet.

Historie

Lineære tidssorteringsalgoritmer har en rik historie innen informatikk. Utviklingen av lineær tidsorden kan spores tilbake til midten av det 20. århundre, og bidragene fra vitenskapsmenn og matematikere var betydelige. En av de tidligste lineære tidssorteringsalgoritmene er bøttesortering, foreslått av Harold H. Seward i 1954. En bøttesortering deler inngangselementene inn i et begrenset antall bøtter og sorterer deretter hver bøtte separat. Denne algoritmen har lineær tidskompleksitet hvis fordelingen av inngangselementer er relativt jevn.

I 1959 introduserte Kenneth E. Iverson en radix-algoritme som oppnår lineær tidskompleksitet. Radix sorterer elementer etter deres tall eller tegn fra minst signifikant til mest signifikant. Den bruker robuste sorteringsalgoritmer, for eksempel numerisk eller bøttesortering, for å sortere elementene på hvert siffersted. Radix-sortering ble populær i epoken med hullkort og tidlige datasystemer. Den mest kjente lineære tidssorteringsalgoritmen er imidlertid en oppregning, introdusert av Harold H. Seward og Peter Elias i 1954 og senere uavhengig gjenoppdaget av Harold H. 'Bobby' Johnson i 1961. Numerisk sortering har fått betydelig oppmerksomhet.

Dette er spesielt effektivt når utvalget av inngangselementer er kjent og relativt lite. Historien om lineær tidssortering fortsatte med utviklingen av andre spesialiserte algoritmer. For eksempel, 1987, foreslo Hanan Samet binær distribusjonstresortering, en lineær tidssorteringsalgoritme for flerdimensjonale data. Gjennom årene har forskere fortsatt å studere og forbedre lineære planleggingsalgoritmer, med fokus på spesifikke scenarier og begrensninger. Selv om algoritmer som quicksort og merge er mer utbredt for sin effektivitet i flere scenarier, gir lineær-tidssorteringsalgoritmer verdifulle alternativer når visse omstendigheter tillater at lineær-tidskompleksiteten kan utnyttes. Generelt er historien til lineær tidssortering preget av å søke etter effektive algoritmer som kan sortere store datasett i lineær tid, og overvinne begrensningene til sammenligningsbaserte sorteringsalgoritmer. Bidragene fra ulike forskere banet vei for å utvikle og forstå disse spesialiserte sorteringsteknikkene.

Typer lineær tidssortering

Det finnes flere forskjellige lineære tidssorteringsalgoritmer. De to hovedtypene er tellebaserte algoritmer og radiksbaserte algoritmer. Her er de vanligste lineære tidssorteringsalgoritmene, klassifisert basert på følgende typer:

Tellebaserte algoritmer

Tellebasert sortering:Tellebasert er en ikke-komparativ sorteringsalgoritme. Den teller forekomsten av hvert enkelt element i inngangsmatrisen og bruker denne informasjonen til å bestemme riktig posisjon for hvert element i den sorterte utmatrisen. Tellebasert sortering antar at inngangselementene er heltall eller kan legges til heltall.

Radix-baserte algoritmer

Sorter radix:Radix Sort er en ikke-sammenligningsbasert sorteringsalgoritme som sorterer elementer etter tall eller tegn. Den teller hvert tall eller tegn i elementene fra det minst signifikante tallet til det mest signifikante. Radikal sortering forutsetter at inngangselementene er heltall eller strenger.Bøttesortering:Bucket Sort er en variant av Radix Sort som deler elementer inn i faste grupper basert på deres rekkevidde eller distribusjon. Hvert segment sorteres separat ved å bruke en annen sorteringsalgoritme eller rekursivt bin-sort.MSD (Most Significant Digit) Radix-sortering:MSD Radix Sort er en variant av radix-sortering som begynner å sortere elementer basert på deres mest betydningsfulle. Den deler elementene rekursivt inn i undergrupper basert på verdien av gjeldende nummer og bruker MSD Radix Sort på hver undergruppe til alle tallene er talt.LSD (Least Significant Digit) Radix-sortering:LSD Radix Sort er en annen variant som begynner å sortere elementer basert på deres minst signifikante. Den sorterer elementene rekursivt basert på hvert tall fra lengst til høyre, og gir et sortert resultat. Både tellebaserte og rotbaserte sorteringsalgoritmer oppnår lineær tidskompleksitet ved å utnytte spesifikke egenskaper til inngangselementene, slik som deres rekkevidde eller representasjonsstruktur (f.eks. tall eller tegn). Imidlertid kan deres anvendelighet variere avhengig av egenskapene til inngangsdataene.

Fordeler med lineær tidssortering

Lineære tidssorteringsalgoritmer, for eksempel numerisk sortering, gir flere fordeler i spesifikke scenarier.

Effektiv for store inngangsstørrelser:Tidskompleksiteten til lineære tidssorteringsalgoritmer er O(n), som betyr at kjøretiden øker lineært med inngangsstørrelsen. Dette gjør dem svært effektive for store datasett sammenlignet med sammenligningsbaserte sorteringsalgoritmer som quicksort eller merge-algoritmer, som typisk har en tidskompleksitet på O(n log n).Ingen sammenligningsoperasjoner:Lineær-tidssorteringsalgoritmer, for eksempel oppregningssortering, er ikke avhengige av elementær sammenligning. I stedet bruker de spesifikke attributter eller informasjon om inngangselementene, for eksempel deres omfang eller distribusjon. Denne funksjonen gjør dem fordelaktige når sammenligningskostnadene er høye, for eksempel for komplekse objekter eller dyre sammenligningsoperasjoner.Egnethet til spesifikke inngangsegenskaper:Lineær-tidssorteringsalgoritmer har ofte spesifikke krav eller forutsetninger om inngangselementene. For eksempel, for å beregne en sorteringsrekkefølge, må du vite utvalget av inngangselementer på forhånd. Når disse betingelsene er oppfylt, kan lineære tidssorteringsalgoritmer tilby betydelige ytelsesfordeler fremfor generelle sorteringsalgoritmer.Stabil sortering:Mange lineær-tidssorteringsalgoritmer, inkludert numerisk og radiksortering, er iboende stabile. Konsistens betyr at elementer med dupliserte nøkler eller verdier opprettholder relativ rekkefølge i den sorterte utgangen. Dette kan være kritisk når du sorterer objekter eller poster med flere attributter eller når det er viktig å bevare den opprinnelige rekkefølgen av elementer med lik verdi.Brukervennlighet:Lineær-tidssorteringsalgoritmer som oppregningssortering er ofte relativt enkle å implementere sammenlignet med mer komplekse sammenligningsbaserte sorteringsalgoritmer. De kan være lettere å forstå og feilsøke, noe som gjør dem egnet for situasjoner der enkelhet og klarhet er ønsket.

Ulemper med lineær tidssortering

Selv om lineære planleggingsalgoritmer har sine fordeler, har de også visse begrensninger og ulemper:

Begrensende inputkrav:Lineære tidssorteringsalgoritmer har ofte spesifikke krav eller forutsetninger om inngangselementene. For eksempel, for å beregne en sorteringsrekkefølge, må du vite utvalget av inngangselementer på forhånd. Denne begrensningen begrenser deres anvendelighet til situasjoner der disse betingelsene er oppfylt. Minnekravene kan bli upraktiske eller overskride tilgjengelige ressurser hvis rekkevidden er omfattende eller ukjent.Ytterligere plassbehov:Noen lineære tidssorteringsalgoritmer, for eksempel numerisk sortering, krever ekstra plass for å lagre andre matriser eller datastrukturer. Plassen som kreves er ofte proporsjonal med antall inngangselementer. Dette kan være en ulempe når minnebruk er et problem, spesielt når man arbeider med store datasett eller begrensede minneressurser.Mangel på allsidighet:Lineære tidssorteringsalgoritmer er spesialiserte algoritmer designet for spesifikke scenarier eller begrensninger. De må kanskje være mer egnet og effektive for generelle sorteringsoppgaver eller ulike inputfordelinger. Sammenligningsbaserte sorteringsalgoritmer som quicksort eller merge er mer allsidige og kan håndtere et bredere spekter av inndataområde.Ineffektiv for små områder eller sparsomme data:Lineær-tidssorteringsalgoritmer som opptelling er mest effektive når rekkevidden av inngangselementer er liten og tett fordelt. Hvis rekkevidden er omfattende eller dataene er sparsomme (dvs. bare noen få distinkte verdier), kan algoritmen spare tid og krefter på å behandle tomme eller tynt befolkede deler av inndataområdet.Begrenset til spesifikke datatyper:Lineær-tidssorteringsalgoritmer, for eksempel oppregningssortering, er først og fremst designet for å sortere ikke-negative heltall eller nøkkelverdiobjekter. De er kanskje ikke egnet for sortering av andre datatyper, for eksempel flytende tall, strenger eller komplekse datastrukturer. Tilpasning av lineære tidssorteringsalgoritmer for å håndtere forskjellige datatyper eller tilpassede sammenligningsfunksjoner kan kreve ytterligere forhåndsbehandling eller modifikasjoner.

Når du velger en sorteringsalgoritme, er det viktig å nøye vurdere inndataens spesifikasjoner og sorteringsproblemets krav. Selv om lineære planleggingsalgoritmer gir fordeler i spesifikke scenarier, er de bare noen ganger det mest passende eller effektive valget.

Anvendelser av lineære tidssorteringsalgoritmer

Lineære tidssorteringsalgoritmer er effektive og har mange bruksområder på ulike felt. Her er noen typiske anvendelser av lineær tidsrekkefølge:

Sortering av heltall i liten rekkevidde:Lineære tidssorteringsalgoritmer som tellesortering og radiksortering er ideelle for sortering av arrays av heltall når verdiområdet er. Disse algoritmene oppnår lineær tidskompleksitet ved å gjøre antakelser om inngangsdataene, slik at de kan omgå sammenligningsbasert sortering.Stringssortering:Lineære tidssorteringsalgoritmer kan også brukes for å sortere strenger effektivt. Ved å ta unike egenskaper til strenger, for eksempel lengden eller tegnene, kan algoritmer som Radix Sort oppnå lineær tidskompleksitet ved sortering av strenger.Databasefunksjoner:Sortering er en viktig funksjon av lineære tidssorteringsalgoritmer kan effektivt sortere store datasett basert på spesifikke kolonner eller felt. Dette muliggjør raskere spørringsbehandling og bedre ytelse i databaseoperasjoner.Opprette histogrammer:Histogrammer er avgjørende for ulike statistiske oppgaver og dataanalyseoppgaver. Lineære tidssorteringsalgoritmer, for eksempel numerisk sortering, kan generere histogrammer ved effektivt å telle forekomsten av elementer i et datasett.Ekstern sortering:Den eksterne sorteringsteknikken brukes i scenarier der dataene ikke kan passe helt i minnet. Lineære tidssorteringsalgoritmer som External Radix Sort eller External Counting Sort kan effektivt sortere store datasett som er lagret på disk eller andre eksterne lagringsenheter.Arrangementsplanlegging:Lineære tidssorteringsalgoritmer kan planlegge hendelser basert på start- eller sluttid. Sortering av hendelser i stigende rekkefølge gjør det enkelt å identifisere konflikter, overlappende perioder eller finne neste tilgjengelige periode.Analyse av loggfiler:Å analysere loggfiler er en vanlig oppgave i systemadministrasjon og feilsøking. Lineære tidssorteringsalgoritmer kan brukes til å sortere logger basert på tidsstempler, noe som gjør det lettere å identifisere mønstre, anomalier eller søke etter spesifikke hendelser.Datakomprimering:Sortering spiller en viktig rolle i ulike datakomprimeringsteknikker. Algoritmer som Burrows-Wheeler Transform (BWT) eller Move-To-Front Transform (MTF) er avhengige av lineær tidsbestilling for å omorganisere data for å forbedre komprimeringseffektiviteten. Dette er bare noen få eksempler på anvendelser av lineære tidssorteringsalgoritmer.

Implementering av lineær tidssortering i C++

Her er et eksempel på et program som implementerer Counting Sort, som er en lineær tidssorteringsalgoritme:

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

Dette indikerer at inngangsmatrisen har blitt sortert i stigende rekkefølge ved å bruke tellesorteringsalgoritmen, noe som resulterer i den sorterte matrisen [1, 2, 2, 3, 3, 4, 8].

I dette C++-programmet tar tellesorteringsfunksjonen en referanse til vektoren arr og kjører tellesorteringsrutinen. Den finner tabellens maksimale verdi for å bestemme regnearkets størrelse. Den teller deretter hvert elements forekomst og beregner regnearkets prefikssum. Deretter lager den en resultatvektor og setter elementene i rekkefølge i henhold til regnearket. Til slutt kopierer den de sorterte elementene tilbake til den opprinnelige matrisen. I den primære funksjonen blir eksempelmatrisen {4, 2, 2, 8, 3, 3, 1} sortert etter oppregningssorteringsalgoritmen og skrevet ut som en sortert matrise. Merk at programmet bruker biblioteker til å jobbe med vektorer og finne det maksimale elementet i en matrise ved å bruke funksjonen max_element.