Introduktion

Sortering er en væsentlig operation inden for datalogi, der involverer at arrangere elementer i en bestemt rækkefølge, såsom numerisk eller alfabetisk rækkefølge. Der er udviklet forskellige sorteringsalgoritmer, hver med tids- og effektivitetsindikatorer. Lineær tidssortering er en delmængde af sorteringsalgoritmer med en væsentlig fordel: de kan sortere et givet sæt af elementer i lineær tid, køretiden øges lineært med inputstørrelsen.

Den bedst kendte lineære tidssorteringsalgoritme er faldende sortering. Beregningsmæssig sortering er særlig effektiv, når rækken af ​​input-elementer er kendt og relativt lille. Dette eliminerer behovet for at sammenligne elementer, den vigtigste tidskrævende operation i mange andre sorteringsalgoritmer. Ved hjælp af input-domæne viden opnår beregningsmæssig sortering lineær tidskompleksitet. En numerisk sortering scanner først input-arrayet for at bestemme antallet af hvert element. Den bruger derefter disse tal til at beregne de korrekte placeringer af elementerne i den ordnede resultattabel. Algoritmen består af følgende trin:

1. For at bestemme området skal du identificere minimum- og maksimumværdierne for input-arrayet.
2. Opret et regneark initialiseret med områdestørrelsen og nuller.
3. Gentag over input-arrayet og øg hvert element fundet.
4. Rediger regnearket ved at beregne den kumulative total for at opnå de korrekte positioner for hvert element.
5. Opret et output-array af samme størrelse som input-arrayet.
6. Flyt input-arrayet igen, og placer hvert element i den korrekte position i output-arrayet baseret på regnearket.
7. Resultattabellen indeholder nu sorterede elementer.

Den største fordel ved faldende sortering er, at den opnår en lineær tidskompleksitet på O(n), hvilket gør den meget effektiv til store inputstørrelser. Dens anvendelighed er dog begrænset til scenarier, hvor valget af inputelementer er kendt på forhånd og relativt lille.

Det er vigtigt at bemærke, at andre sorteringsalgoritmer, såsom quicksort eller merge, typisk har en tidskompleksitet på O(n log n), hvilket anses for at være effektivt til mange praktiske anvendelser. Lineære tidssorteringsalgoritmer, såsom numerisk sortering, giver et alternativ, når visse begrænsninger eller egenskaber af inputtet tillader lineær tidskompleksitet at blive brugt.

Historie

Lineære tidssorteringsalgoritmer har en rig historie inden for datalogi. Udviklingen af ​​lineær tidsorden kan spores tilbage til midten af ​​det 20. århundrede, og bidragene fra videnskabsmænd og matematikere var betydelige. En af de tidligste lineære tidssorteringsalgoritmer er spandsortering, foreslået af Harold H. Seward i 1954. En spandsortering opdeler inputelementerne i et begrænset antal spande og sorterer derefter hver spand separat. Denne algoritme har lineær tidskompleksitet, hvis fordelingen af ​​inputelementer er relativt ensartet.

I 1959 introducerede Kenneth E. Iverson en radix-algoritme, der opnår lineær tidskompleksitet. Radix sorterer elementer efter deres tal eller tegn fra mindst signifikant til mest signifikant. Den bruger robuste sorteringsalgoritmer, såsom numerisk eller bucket-sortering, til at sortere elementerne på hver cifferplacering. Radix-sortering blev populær i æraen med hulkort og tidlige computersystemer. Den mest kendte lineære tidssorteringsalgoritme er dog en opregning, introduceret af Harold H. Seward og Peter Elias i 1954 og senere uafhængigt genopdaget af Harold H. 'Bobby' Johnson i 1961. Numerisk sortering har fået stor opmærksomhed.

Dette er særligt effektivt, når rækken af ​​input-elementer er kendt og relativt lille. Historien om lineær tidssortering fortsatte med udviklingen af ​​andre specialiserede algoritmer. For eksempel foreslog Hanan Samet i 1987 binær distributionstræsortering, en lineær tidssorteringsalgoritme for multidimensionelle data. I årenes løb har forskere fortsat med at studere og forbedre lineære planlægningsalgoritmer med fokus på specifikke scenarier og begrænsninger. Selvom algoritmer som quicksort og merge er mere udbredt på grund af deres effektivitet i flere scenarier, giver lineær-tidssorteringsalgoritmer værdifulde alternativer, når visse omstændigheder tillader lineær-tidskompleksiteten at blive udnyttet. Generelt er historien om lineær tidssortering karakteriseret ved at søge efter effektive algoritmer, der kan sortere store datasæt i lineær tid, og overvinde begrænsningerne ved sammenligningsbaserede sorteringsalgoritmer. Bidragene fra forskellige forskere banede vejen for udvikling og forståelse af disse specialiserede sorteringsteknikker.

Typer af lineær tidssortering

Der er flere forskellige lineære tidssorteringsalgoritmer. De to hovedtyper er tællebaserede algoritmer og radix-baserede algoritmer. Her er de mest almindelige lineære tidssorteringsalgoritmer, klassificeret baseret på følgende typer:

Optællingsbaserede algoritmer

Optællingsbaseret sortering:Optællingsbaseret er en ikke-komparativ sorteringsalgoritme. Den tæller forekomsten af ​​hvert enkelt element i input-arrayet og bruger denne information til at bestemme den korrekte position af hvert element i det sorterede output-array. Optællingsbaseret sortering antager, at inputelementerne er heltal eller kan føjes til heltal.

Radix-baserede algoritmer

Sort radix:Radix Sort er en ikke-sammenligningsbaseret sorteringsalgoritme, der sorterer elementer efter deres tal eller tegn. Den tæller hvert tal eller tegn i elementerne fra det mindst signifikante tal til det mest signifikante. Radikal sortering antager, at inputelementerne er heltal eller strenge.Sortér spand:Bucket Sort er en variant af Radix Sort, der opdeler elementer i faste grupper baseret på deres rækkevidde eller fordeling. Hvert segment sorteres separat ved hjælp af en anden sorteringsalgoritme eller rekursivt bin-sort.MSD (Most Significant Digit) Radix Sort:MSD Radix Sort er en variant af radix sort, der begynder at sortere elementer baseret på deres mest betydningsfulde. Den opdeler rekursivt elementerne i undergrupper baseret på værdien af ​​det aktuelle tal og anvender MSD Radix Sort på hver undergruppe, indtil alle tallene er blevet talt.LSD (Least Significant Digit) Radix-sortering:LSD Radix Sort er en anden variant, der begynder at sortere elementer baseret på deres mindst signifikante. Den sorterer rekursivt elementerne baseret på hvert tal fra længst til højre til venstre, hvilket giver et sorteret resultat. Både tællebaserede og rodbaserede sorteringsalgoritmer opnår lineær tidskompleksitet ved at udnytte specifikke egenskaber for inputelementerne, såsom deres rækkevidde eller repræsentationsstruktur (f.eks. tal eller tegn). Deres anvendelighed kan dog variere afhængigt af inputdataens karakteristika.

Fordele ved lineær tidssortering

Lineære tidssorteringsalgoritmer, såsom numerisk sortering, giver flere fordele i specifikke scenarier.

Effektiv til store inputstørrelser:Tidskompleksiteten af ​​lineære tidssorteringsalgoritmer er O(n), hvilket betyder, at køretiden stiger lineært med inputstørrelsen. Dette gør dem meget effektive til store datasæt sammenlignet med sammenligningsbaserede sorteringsalgoritmer såsom quicksort eller merge-algoritmer, som typisk har en tidskompleksitet på O(n log n).Ingen sammenligningsoperationer:Lineær-tidssorteringsalgoritmer, såsom optællingssortering, er ikke afhængige af elementær sammenligning I stedet bruger de specifikke attributter eller information om inputelementerne, såsom deres omfang eller fordeling. Denne funktion gør dem fordelagtige, når sammenligningsomkostningerne er høje, såsom for komplekse objekter eller dyre sammenligningsoperationer.Egnethed til specifikke inputegenskaber:Lineær-tidssorteringsalgoritmer har ofte specifikke krav eller antagelser om input-elementerne. For at beregne en sorteringsrækkefølge skal du for eksempel kende rækken af ​​inputelementer på forhånd. Når disse betingelser er opfyldt, kan lineære tidssorteringsalgoritmer tilbyde betydelige ydeevnefordele i forhold til generelle sorteringsalgoritmer.Stabil sortering:Mange lineær-tidssorteringsalgoritmer, herunder numerisk og radix-sortering, er i sagens natur stabile. Konsistens betyder, at elementer med dublerede nøgler eller værdier opretholder relativ rækkefølge i det sorterede output. Dette kan være kritisk, når du sorterer objekter eller poster med flere attributter, eller når det er vigtigt at bevare den oprindelige rækkefølge af elementer af samme værdi.Brugervenlighed:Lineære tidssorteringsalgoritmer såsom optællingssortering er ofte relativt nemme at implementere sammenlignet med mere komplekse sammenligningsbaserede sorteringsalgoritmer. De kan være nemmere at forstå og fejlfinde, hvilket gør dem velegnede til situationer, hvor enkelhed og klarhed ønskes.

Ulemper ved lineær tidssortering

Selvom lineære planlægningsalgoritmer har deres fordele, har de også visse begrænsninger og ulemper:

Begrænsende inputkrav:Lineære tidssorteringsalgoritmer har ofte specifikke krav eller antagelser om inputelementerne. For at beregne en sorteringsrækkefølge skal du for eksempel kende rækken af ​​inputelementer på forhånd. Denne begrænsning begrænser deres anvendelighed til situationer, hvor disse betingelser er opfyldt. Hukommelseskravene kan blive upraktiske eller overstige tilgængelige ressourcer, hvis rækkevidden er omfattende eller ukendt.Yderligere pladskrav:Nogle lineære tidssorteringsalgoritmer, såsom numerisk sortering, kræver ekstra plads til at gemme andre arrays eller datastrukturer. Den nødvendige plads er ofte proportional med antallet af input-elementer. Dette kan være en ulempe, når hukommelsesbrug er et problem, især når man har at gøre med store datasæt eller begrænsede hukommelsesressourcer.Mangel på alsidighed:Lineære tidssorteringsalgoritmer er specialiserede algoritmer designet til specifikke scenarier eller begrænsninger. De skal muligvis være mere egnede og effektive til generelle sorteringsopgaver eller forskellige inputfordelinger. Sammenligningsbaserede sorteringsalgoritmer såsom quicksort eller merge er mere alsidige og kan håndtere en bredere vifte af inputområde.Ineffektiv til små områder eller sparsomme data:Lineære tidssorteringsalgoritmer såsom optælling er mest effektive, når rækken af ​​inputelementer er lille og tæt fordelt. Hvis rækkevidden er omfattende, eller dataene er sparsomme (dvs. kun nogle få forskellige værdier), kan algoritmen spare tid og kræfter på at behandle tomme eller tyndt befolkede dele af inputområdet.Begrænset til specifikke datatyper:Lineær-tidssorteringsalgoritmer, såsom optællingssortering, er primært designet til at sortere ikke-negative heltal eller nøgleværdiobjekter. De er muligvis ikke egnede til at sortere andre datatyper, såsom flydende kommatal, strenge eller komplekse datastrukturer. Tilpasning af lineære tidssorteringsalgoritmer til at håndtere forskellige datatyper eller brugerdefinerede sammenligningsfunktioner kan kræve yderligere forbehandling eller ændringer.

Når du vælger en sorteringsalgoritme, er det vigtigt nøje at overveje inputdataens specifikationer og sorteringsproblemets krav. Selvom lineære planlægningsalgoritmer tilbyder fordele i specifikke scenarier, er de kun nogle gange det mest passende eller effektive valg.

Anvendelser af lineære tidssorteringsalgoritmer

Lineære tidssorteringsalgoritmer er effektive og har mange anvendelsesmuligheder inden for forskellige områder. Her er nogle typiske anvendelser af lineær tidsrækkefølge:

Sortering af heltal i lille område:Lineære tidssorteringsalgoritmer såsom tællesortering og radixsortering er ideelle til at sortere arrays af heltal, når værdiintervallet er. Disse algoritmer opnår lineær tidskompleksitet ved at lave antagelser om inputdataene, hvilket giver dem mulighed for at omgå sammenligningsbaseret sortering.Strengesortering:Lineære tidssorteringsalgoritmer kan også anvendes til at sortere strenge effektivt. Ved at tage strenge unikke egenskaber, såsom deres længde eller tegn, kan algoritmer som Radix Sort opnå lineær tidskompleksitet ved sortering af strenge.Database funktioner:Sortering er en væsentlig funktion af lineære tidssorteringsalgoritmer kan effektivt sortere store datasæt baseret på specifikke kolonner eller felter. Dette muliggør hurtigere forespørgselsbehandling og bedre ydeevne i databaseoperationer.Oprettelse af histogrammer:Histogrammer er afgørende for forskellige statistiske og dataanalyseopgaver. Lineære tidssorteringsalgoritmer, såsom numerisk sortering, kan generere histogrammer ved effektivt at tælle forekomsten af ​​elementer i et datasæt.Ekstern sortering:Den eksterne sorteringsteknik bruges i scenarier, hvor dataene ikke kan passe helt i hukommelsen. Lineære tidssorteringsalgoritmer såsom External Radix Sort eller External Counting Sort kan effektivt sortere store datasæt gemt på disk eller andre eksterne lagerenheder.Begivenhedsplanlægning:Lineære tidssorteringsalgoritmer kan planlægge begivenheder baseret på deres start- eller sluttidspunkter. Sortering af begivenheder i stigende rækkefølge gør det nemt at identificere konflikter, overlappende perioder eller finde den næste tilgængelige periode.Analyse af logfiler:Analyse af logfiler er en almindelig opgave i systemadministration og fejlfinding. Lineære tidssorteringsalgoritmer kan bruges til at sortere logfiler baseret på tidsstempler, hvilket gør det nemmere at identificere mønstre, anomalier eller søge efter specifikke hændelser.Datakomprimering:Sortering spiller en væsentlig rolle i forskellige datakomprimeringsteknikker. Algoritmer såsom Burrows-Wheeler Transform (BWT) eller Move-To-Front Transform (MTF) er afhængige af lineær tidsbestilling til at omarrangere data for at forbedre kompressionseffektiviteten. Dette er blot nogle få eksempler på anvendelser af lineære tidssorteringsalgoritmer.

Implementering af lineær tidssortering i C++

Her er et eksempel på et program, der 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 input-arrayet er blevet sorteret i stigende rækkefølge ved hjælp af Counting Sort-algoritmen, hvilket resulterer i det sorterede array [1, 2, 2, 3, 3, 4, 8].

I dette C++-program tager tællesorteringsfunktionen en reference til vektoren arr og kører tællesorteringsrutinen. Den finder tabellens maksimale værdi for at bestemme regnearkets størrelse. Den tæller derefter hvert elements forekomst og beregner regnearkets præfikssum. Derefter opretter den en resultatvektor og sætter elementerne i rækkefølge i henhold til regnearket. Til sidst kopierer den de sorterede elementer tilbage i det originale array. I den primære funktion sorteres eksempelarrayet {4, 2, 2, 8, 3, 3, 1} efter opregningssorteringsalgoritmen og udskrives som en sorteret matrix. Bemærk, at programmet bruger biblioteker til at arbejde med vektorer og finde det maksimale element i et array ved hjælp af funktionen max_element.