Introduktion

Sortering är en viktig operation inom datavetenskap som innebär att element ordnas i en specifik ordning, till exempel numerisk eller alfabetisk ordning. Olika sorteringsalgoritmer har utvecklats, var och en med tids- och effektivitetsindikatorer. Linjär tidssortering är en undergrupp av sorteringsalgoritmer med en betydande fördel: de kan sortera en given uppsättning element i linjär tid, körtiden ökar linjärt med indatastorleken.

Den mest kända linjära tidssorteringsalgoritmen är fallande sortering. Beräkningssortering är särskilt effektiv när utbudet av inmatningselement är känt och relativt litet. Detta eliminerar behovet av att jämföra element, den huvudsakliga tidskrävande operationen i många andra sorteringsalgoritmer. Med hjälp av kunskap om input-domän uppnår beräkningssortering linjär tidskomplexitet. En numerisk sortering skannar först inmatningsmatrisen för att bestämma antalet för varje element. Den använder sedan dessa siffror för att beräkna de korrekta positionerna för elementen i den ordnade resultattabellen. Algoritmen består av följande steg:

1. För att bestämma intervallet, identifiera minimi- och maximivärdena för inmatningsmatrisen.
2. Skapa ett kalkylblad initierat med intervallstorleken och nollor.
3. Iterera över inmatningsmatrisen och inkrementera varje hittat element.
4. Ändra kalkylbladet genom att beräkna den ackumulerade summan för att få rätt positioner för varje element.
5. Skapa en utmatris med samma storlek som inmatningsmatrisen.
6. Flytta inmatningsmatrisen igen, placera varje element i rätt position i utmatrisen baserat på kalkylbladet.
7. Resultattabellen innehåller nu sorterade element.

Den största fördelen med fallande sortering är att den uppnår en linjär tidskomplexitet på O(n), vilket gör den mycket effektiv för stora indatastorlekar. Dess tillämpbarhet är dock begränsad till scenarier där valet av insatselement är känt i förväg och relativt litet.

Det är viktigt att notera att andra sorteringsalgoritmer, såsom quicksort eller merge, vanligtvis har en tidskomplexitet på O(n log n), vilket anses vara effektivt för många praktiska tillämpningar. Linjära tidssorteringsalgoritmer, såsom numerisk sortering, tillhandahåller ett alternativ när vissa begränsningar eller egenskaper hos inmatningen tillåter linjär tidskomplexitet att användas.

Historia

Linjära tidssorteringsalgoritmer har en rik historia inom datavetenskap. Utvecklingen av linjär tidsordning kan spåras tillbaka till mitten av 1900-talet, och bidragen från vetenskapsmän och matematiker var betydande. En av de tidigaste linjära tidssorteringsalgoritmerna är hinksortering, föreslog av Harold H. Seward 1954. En hinksortering delar in inmatningselementen i ett ändligt antal hinkar och sorterar sedan varje hink separat. Denna algoritm har linjär tidskomplexitet om fördelningen av ingångselement är relativt enhetlig.

1959 introducerade Kenneth E. Iverson en radixalgoritm som uppnår linjär tidskomplexitet. Radix sorterar element efter deras antal eller tecken från minst signifikant till mest signifikant. Den använder robusta sorteringsalgoritmer, såsom numerisk eller hinksortering, för att sortera elementen på varje siffra. Radixsortering blev populärt under hålkortens och tidiga datorsystems era. Den mest kända linjära tidssorteringsalgoritmen är dock en uppräkning, introducerad av Harold H. Seward och Peter Elias 1954 och senare återupptäckt oberoende av Harold H. 'Bobby' Johnson 1961. Numerisk sortering har fått stor uppmärksamhet.

Detta är särskilt effektivt när omfånget av ingångselement är känt och relativt litet. Historien om linjär tidssortering fortsatte med utvecklingen av andra specialiserade algoritmer. Till exempel, 1987, föreslog Hanan Samet binär distributionsträdsortering, en linjär tidssorteringsalgoritm för flerdimensionell data. Under åren har forskare fortsatt att studera och förbättra linjära schemaläggningsalgoritmer, med fokus på specifika scenarier och begränsningar. Även om algoritmer som quicksort och merge används mer allmänt för sin effektivitet i fler scenarier, ger linjärtidssorteringsalgoritmer värdefulla alternativ när vissa omständigheter tillåter att linjärtidskomplexiteten kan utnyttjas. I allmänhet kännetecknas historien av linjär tidssortering av att söka efter effektiva algoritmer som kan sortera stora datamängder i linjär tid, och övervinna begränsningarna hos jämförelsebaserade sorteringsalgoritmer. Bidragen från olika forskare banade väg för att utveckla och förstå dessa specialiserade sorteringstekniker.

Typer av linjär tidssortering

Det finns flera olika linjära tidssorteringsalgoritmer. De två huvudtyperna är räkningsbaserade algoritmer och radixbaserade algoritmer. Här är de vanligaste linjära tidssorteringsalgoritmerna, klassificerade utifrån följande typer:

Räknebaserade algoritmer

Räknebaserad sortering:Counting-Based är en icke-jämförande sorteringsalgoritm. Den räknar förekomsten av varje särskilt element i inmatningsmatrisen och använder denna information för att bestämma den korrekta positionen för varje element i den sorterade utmatrisen. Räknebaserad sortering antar att indataelementen är heltal eller kan läggas till heltal.

Radix-baserade algoritmer

Sortera radix:Radix Sort är en icke-jämförelsebaserad sorteringsalgoritm som sorterar element efter deras nummer eller tecken. Den räknar varje nummer eller tecken i elementen från det minst signifikanta talet till det mest signifikanta. Radikal sortering förutsätter att inmatningselementen är heltal eller strängar.Hinksortering:Bucket Sort är en variant av Radix Sort som delar in element i fasta grupper baserat på deras intervall eller distribution. Varje segment sorteras separat med en annan sorteringsalgoritm eller rekursivt bin-sort.MSD (Most Significant Digit) Radix Sort:MSD Radix Sort är en variant av radixsortering som börjar sortera element baserat på deras mest signifikanta. Den delar rekursivt in elementen i undergrupper baserat på värdet på det aktuella numret och tillämpar MSD Radix Sort på varje undergrupp tills alla siffror har räknats.LSD (Least Significant Digit) Radix-sortering:LSD Radix Sort är en annan variant som börjar sortera element baserat på deras minst signifikanta. Den sorterar rekursivt elementen baserat på varje nummer från längst till höger till vänster, vilket ger ett sorterat resultat. Både räkningsbaserade och rotbaserade sorteringsalgoritmer uppnår linjär tidskomplexitet genom att utnyttja specifika egenskaper hos inmatningselementen, såsom deras intervall eller representationsstruktur (t.ex. siffror eller tecken). Deras tillämplighet kan dock variera beroende på egenskaperna hos indata.

Fördelar med linjär tidssortering

Linjära tidssorteringsalgoritmer, såsom numerisk sortering, erbjuder flera fördelar i specifika scenarier.

Effektiv för stora inmatningsstorlekar:Tidskomplexiteten för linjära tidssorteringsalgoritmer är O(n), vilket innebär att körtiden ökar linjärt med indatastorleken. Detta gör dem mycket effektiva för stora datamängder jämfört med jämförelsebaserade sorteringsalgoritmer som quicksort eller merge-algoritmer, som vanligtvis har en tidskomplexitet på O(n log n).Inga jämförelseoperationer:Linjär-tidssorteringsalgoritmer, såsom uppräkningssortering, förlitar sig inte på elementär jämförelse. Istället använder de specifika attribut eller information om indataelementen, såsom deras omfattning eller distribution. Denna funktion gör dem fördelaktiga när kostnaden för jämförelse är hög, till exempel för komplexa objekt eller dyra jämförelseoperationer.Lämplighet för specifika indataegenskaper:Linjär-tidssorteringsalgoritmer har ofta specifika krav eller antaganden om ingångselementen. Till exempel, för att beräkna en sorteringsordning, måste du veta omfånget av inmatningselement i förväg. När dessa villkor är uppfyllda kan linjära tidssorteringsalgoritmer erbjuda betydande prestandafördelar jämfört med allmänna sorteringsalgoritmer.Stabil sortering:Många linjär-tidssorteringsalgoritmer, inklusive numerisk sortering och radixsortering, är i sig stabila. Konsistens innebär att element med dubbletter av nycklar eller värden bibehåller relativ ordning i den sorterade utmatningen. Detta kan vara avgörande när man sorterar objekt eller poster med flera attribut eller när det är viktigt att bevara den ursprungliga ordningen av element av lika värde.Enkel användning:Linjär-tidssorteringsalgoritmer såsom uppräkningssortering är ofta relativt enkla att implementera jämfört med mer komplexa jämförelsebaserade sorteringsalgoritmer. De kan vara lättare att förstå och felsöka, vilket gör dem lämpliga för situationer där enkelhet och tydlighet önskas.

Nackdelar med linjär tidssortering

Även om linjära schemaläggningsalgoritmer har sina fördelar, har de också vissa begränsningar och nackdelar:

Begränsande indatakrav:Linjära tidssorteringsalgoritmer har ofta specifika krav eller antaganden om ingångselementen. Till exempel, för att beräkna en sorteringsordning, måste du veta omfånget av inmatningselement i förväg. Denna begränsning begränsar deras tillämplighet till situationer där dessa villkor är uppfyllda. Minneskraven kan bli opraktiska eller överskrida tillgängliga resurser om utbudet är omfattande eller okänt.Ytterligare utrymmeskrav:Vissa linjära tidssorteringsalgoritmer, såsom numerisk sortering, kräver ytterligare utrymme för att lagra andra arrayer eller datastrukturer. Det utrymme som krävs är ofta proportionellt mot antalet inmatningselement. Detta kan vara en nackdel när minnesanvändning är ett problem, särskilt när man hanterar stora datamängder eller begränsade minnesresurser.Brist på mångsidighet:Linjära tidssorteringsalgoritmer är specialiserade algoritmer utformade för specifika scenarier eller begränsningar. De kan behöva vara mer lämpade och effektiva för allmänna sorteringsuppgifter eller olika insatsfördelningar. Jämförelsebaserade sorteringsalgoritmer som quicksort eller merge är mer mångsidiga och kan hantera ett bredare indataområde.Ineffektivt för små intervall eller glesa data:Linjär-tidssorteringsalgoritmer såsom uppräkning är mest effektiva när omfånget av ingångselement är litet och tätt fördelat. Om intervallet är omfattande eller om data är gles (dvs. endast ett fåtal distinkta värden), kan algoritmen spara tid och ansträngning vid bearbetning av tomma eller glest befolkade delar av inmatningsintervallet.Begränsat till specifika datatyper:Linjär-tidssorteringsalgoritmer, såsom uppräkningssortering, är i första hand utformade för att sortera icke-negativa heltal eller nyckel-värdeobjekt. De kanske inte är lämpliga för att sortera andra datatyper, till exempel flyttal, strängar eller komplexa datastrukturer. Att anpassa linjära tidssorteringsalgoritmer för att hantera olika datatyper eller anpassade jämförelsefunktioner kan kräva ytterligare förbearbetning eller modifieringar.

När du väljer en sorteringsalgoritm är det viktigt att noggrant överväga indatas specifikationer och sorteringsproblemets krav. Även om linjära schemaläggningsalgoritmer erbjuder fördelar i specifika scenarier, är de bara ibland det mest lämpliga eller effektiva valet.

Tillämpningar av linjära tidssorteringsalgoritmer

Linjära tidssorteringsalgoritmer är effektiva och har många tillämpningar inom olika områden. Här är några typiska tillämpningar av linjär tidsordning:

Sortera heltal för små intervall:Linjära tidssorteringsalgoritmer som räknesortering och radixsortering är idealiska för att sortera arrayer av heltal när värdeintervallet är. Dessa algoritmer uppnår linjär tidskomplexitet genom att göra antaganden om indata, vilket gör att de kan kringgå jämförelsebaserad sortering.Strängsortering:Linjära tidssorteringsalgoritmer kan också användas för att sortera strängar effektivt. Genom att ta unika egenskaper hos strängar, såsom deras längd eller tecken, kan algoritmer som Radix Sort uppnå linjär tidskomplexitet vid sortering av strängar.Databasfunktioner:Sortering är en viktig funktion för linjära tidssorteringsalgoritmer som effektivt kan sortera stora datamängder baserat på specifika kolumner eller fält. Detta möjliggör snabbare frågebehandling och bättre prestanda i databasoperationer.Skapa histogram:Histogram är väsentliga för olika statistiska uppgifter och dataanalysuppgifter. Linjära tidssorteringsalgoritmer, såsom numerisk sortering, kan generera histogram genom att effektivt räkna förekomsten av element i en datauppsättning.Extern sortering:Den externa sorteringstekniken används i scenarier där data inte får plats helt i minnet. Linjära tidssorteringsalgoritmer som External Radix Sort eller External Counting Sort kan effektivt sortera stora datamängder lagrade på disk eller andra externa lagringsenheter.Händelseschemaläggning:Linjära tidssorteringsalgoritmer kan schemalägga händelser baserat på deras start- eller sluttider. Att sortera händelser i stigande ordning gör det enkelt att identifiera konflikter, överlappande perioder eller hitta nästa tillgängliga period.Analysera loggfiler:Att analysera loggfiler är en vanlig uppgift inom systemadministration och felsökning. Linjära tidssorteringsalgoritmer kan användas för att sortera loggar baserat på tidsstämplar, vilket gör det lättare att identifiera mönster, anomalier eller söka efter specifika händelser.Datakomprimering:Sortering spelar en viktig roll i olika datakomprimeringstekniker. Algoritmer som Burrows-Wheeler Transform (BWT) eller Move-To-Front Transform (MTF) förlitar sig på linjär tidsordning för att omordna data för att förbättra kompressionseffektiviteten. Detta är bara några exempel på tillämpningar av linjära tidssorteringsalgoritmer.

Implementering av linjär tidssortering i C++

Här är ett exempel på ett program som implementerar Counting Sort, som är en linjär tidssorteringsalgoritm:

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

Detta indikerar att inmatningsmatrisen har sorterats i stigande ordning med hjälp av Counting Sort-algoritmen, vilket resulterar i den sorterade matrisen [1, 2, 2, 3, 3, 4, 8].

I detta C++-program tar räknesorteringsfunktionen en referens till vektorn arr och kör räknesorteringsrutinen. Den hittar tabellens maximala värde för att bestämma kalkylbladets storlek. Den räknar sedan varje elements förekomst och beräknar kalkylbladets prefixsumma. Sedan skapar den en resultatvektor och placerar elementen i ordning enligt kalkylbladet. Slutligen kopierar den de sorterade elementen tillbaka till den ursprungliga arrayen. I den primära funktionen sorteras exempelmatrisen {4, 2, 2, 8, 3, 3, 1} av uppräkningssorteringsalgoritmen och skrivs ut som en sorterad matris. Observera att programmet använder bibliotek för att arbeta med vektorer och hitta det maximala elementet i en array med funktionen max_element.