Bevezetés

A rendezés az informatika alapvető művelete, amely magában foglalja az elemek meghatározott sorrendbe, például numerikus vagy ábécé sorrendbe rendezését. Különféle rendezési algoritmusokat fejlesztettek ki, mindegyik idő- és hatékonyságmutatókkal. A lineáris idejű rendezés a rendezési algoritmusok egy részhalmaza, amelynek jelentős előnye: egy adott elemhalmazt lineáris időben tudnak rendezni, a futásidő lineárisan növekszik a bemeneti mérettel.

A legismertebb lineáris idő szerinti rendezési algoritmus a csökkenő rendezés. A számítási rendezés különösen akkor hatékony, ha a bemeneti elemek köre ismert és viszonylag kicsi. Ezzel szükségtelenné válik az elemek összehasonlítása, ami sok más rendezési algoritmus fő időigényes művelete. A bemeneti tartomány ismereteit felhasználva a számítási rendezés lineáris időbonyolultságot ér el. A numerikus rendezés először átvizsgálja a bemeneti tömböt, hogy meghatározza az egyes elemek számát. Ezután ezekből a számokból számítja ki az elemek helyes pozícióját a rendezett eredménytáblázatban. Az algoritmus a következő lépésekből áll:

1. A tartomány meghatározásához határozza meg a bemeneti tömb minimális és maximális értékét.
2. Hozzon létre egy munkalapot a tartomány méretével és nullákkal inicializálva.
3. Iteráljon a bemeneti tömbön, és növelje az egyes talált elemeket.
4. Módosítsa a munkalapot az összesített összeg kiszámításával, hogy megkapja az egyes elemek helyes pozícióit.
5. Hozzon létre a bemeneti tömb méretű kimeneti tömbjét.
6. Mozgassa újra a bemeneti tömböt, és helyezze el az egyes elemeket a megfelelő pozícióba a kimeneti tömbben a munkalap alapján.
7. Az eredménytábla most rendezett elemeket tartalmaz.

A csökkenő rendezés fő előnye, hogy O(n) lineáris időbonyolultságot ér el, ami nagyon hatékonyvá teszi nagy bemeneti méretek esetén. Alkalmazhatósága azonban azokra a forgatókönyvekre korlátozódik, ahol a bemeneti elemek választéka előre ismert és viszonylag kicsi.

Fontos megjegyezni, hogy más rendezési algoritmusok, mint például a gyorsrendezés vagy egyesítés, jellemzően O(n log n) időbonyolítással rendelkeznek, ami sok gyakorlati alkalmazásban hatékonynak tekinthető. A lineáris idő szerinti rendezési algoritmusok, mint például a numerikus rendezés, alternatívát kínálnak, ha a bemenet bizonyos korlátai vagy tulajdonságai lehetővé teszik a lineáris időbonyolultság használatát.

Történelem

A lineáris idő szerinti rendezési algoritmusok gazdag számítástechnikai múlttal rendelkeznek. A lineáris időrend kialakulása a 20. század közepére tehető, és jelentős volt a tudósok és a matematikusok közreműködése. Az egyik legkorábbi lineáris idő szerinti rendezési algoritmus a vödör rendezés, amelyet Harold H. Seward javasolt 1954-ben. A vödör rendezés véges számú gyűjtőhelyre osztja a bemeneti elemeket, majd az egyes gyűjtőket külön-külön rendezi. Ez az algoritmus lineáris időben bonyolult, ha a bemeneti elemek eloszlása ​​viszonylag egyenletes.

1959-ben Kenneth E. Iverson bevezetett egy radix algoritmust, amely lineáris időbonyolultságot ér el. A Radix az elemeket számuk vagy előjeleik szerint rendezi a legkevésbé jelentőstől a legjelentősebbig. Robusztus rendezési algoritmusokat használ, például numerikus vagy vödör rendezést, hogy rendezze az elemeket az egyes számjegyek helyén. A Radix rendezés a lyukkártyák és a korai számítógépes rendszerek korában vált népszerűvé. A legismertebb lineáris idő szerinti rendezési algoritmus azonban egy felsorolás, amelyet Harold H. Seward és Peter Elias vezetett be 1954-ben, majd később önállóan Harold H. 'Bobby' Johnson fedezte fel újra 1961-ben. A numerikus rendezés jelentős figyelmet kapott.

Ez különösen akkor hatékony, ha a bemeneti elemek köre ismert és viszonylag kicsi. A lineáris idő szerinti rendezés története további speciális algoritmusok kifejlesztésével folytatódott. Például 1987-ben Hanan Samet javasolta a bináris eloszlásfa rendezést, egy lineáris idő szerinti rendezési algoritmust többdimenziós adatokhoz. Az évek során a kutatók folytatták a lineáris ütemezési algoritmusok tanulmányozását és fejlesztését, konkrét forgatókönyvekre és korlátokra összpontosítva. Bár az olyan algoritmusokat, mint a gyorsrendezés és az összevonás, szélesebb körben használják hatékonyságuk miatt több forgatókönyvben, a lineáris idejű rendezési algoritmusok értékes alternatívákat kínálnak, ha bizonyos körülmények lehetővé teszik a lineáris idejű összetettség kihasználását. Általánosságban elmondható, hogy a lineáris idő szerinti rendezés történetét olyan hatékony algoritmusok keresése jellemzi, amelyek képesek nagy adathalmazokat lineáris időben rendezni, leküzdve az összehasonlításon alapuló rendezési algoritmusok korlátait. Különböző kutatók hozzájárulása nyitotta meg az utat e speciális válogatási technikák fejlesztéséhez és megértéséhez.

A lineáris idő szerinti rendezés típusai

Számos különböző lineáris idő szerinti rendezési algoritmus létezik. A két fő típus a számlálás alapú algoritmusok és a radix alapú algoritmusok. Íme a leggyakoribb lineáris idő szerinti rendezési algoritmusok, amelyek a következő típusok alapján vannak osztályozva:

Számláláson alapuló algoritmusok

Számlálás alapú rendezés:A Counting-Based egy nem összehasonlító rendezési algoritmus. Számolja az egyes elemek előfordulását a bemeneti tömbben, és ezen információk alapján határozza meg az egyes elemek helyes pozícióját a rendezett kimeneti tömbben. A számláláson alapuló rendezés feltételezi, hogy a bemeneti elemek egész számok, vagy egész számokhoz hozzáadhatók.

Radix-alapú algoritmusok

Radix rendezése:A Radix Sort egy nem összehasonlításon alapuló rendezési algoritmus, amely az elemeket számok vagy karakterek alapján rendezi. A legkisebb jelentőségű számtól a legjelentősebbig számol minden egyes számot vagy előjelet az elemekben.Vödör rendezés:A Bucket Sort a Radix Sort egyik változata, amely az elemeket tartományuk vagy eloszlásuk alapján rögzített csoportokra osztja. Az egyes szegmensek külön-külön vannak rendezve, különböző rendezési algoritmussal vagy rekurzív bin-rendezéssel.MSD (legjelentősebb számjegy) radix rendezés:Az MSD Radix Sort a radix rendezés egyik változata, amely a legjelentősebbek alapján kezdi el rendezni az elemeket. Az elemeket rekurzívan alcsoportokra osztja az aktuális szám értéke alapján, és az MSD Radix Rendezést alkalmazza az egyes alcsoportokra, amíg az összes számot meg nem számlálja.LSD (legkisebb jelentőségű számjegy) radix rendezés:Az LSD Radix Sort egy másik változata, amely a legkisebb szignifikancia alapján kezdi el rendezni az elemeket. Rekurzív módon rendezi az elemeket az egyes számok alapján a jobb széltől a bal szélsőig, így rendezett eredményt ad. Mind a számlálási, mind a gyökéralapú rendezési algoritmusok lineáris időbonyolítást érnek el azáltal, hogy kihasználják a bemeneti elemek specifikus tulajdonságait, például tartományukat vagy reprezentációs struktúrájukat (pl. számok vagy karakterek). Alkalmazhatóságuk azonban a bemeneti adatok jellemzőitől függően változhat.

A lineáris idő szerinti rendezés előnyei

A lineáris idő szerinti rendezési algoritmusok, mint például a numerikus rendezés, számos előnyt kínálnak bizonyos forgatókönyvekben.

Hatékony nagy bemeneti méretekhez:A lineáris idő szerinti rendezési algoritmusok időbonyolultsága O(n), ami azt jelenti, hogy a futási idő lineárisan növekszik a bemeneti mérettel. Emiatt nagyon hatékonyak nagy adathalmazok esetén, összehasonlítva az összehasonlításon alapuló rendezési algoritmusokkal, például a gyorsszortírozási vagy egyesítő algoritmusokkal, amelyek időbeli összetettsége általában O(n log n).Nincsenek összehasonlítási műveletek:A lineáris idejű rendezési algoritmusok, mint például a felsorolás szerinti rendezés, nem támaszkodnak elemi összehasonlításra, hanem konkrét attribútumokat vagy információkat használnak a bemeneti elemekről, például azok kiterjedéséről vagy eloszlásáról. Ez a funkció akkor előnyös, ha az összehasonlítás költsége magas, például összetett objektumok vagy drága összehasonlítási műveletek esetén.Alkalmasság meghatározott bemeneti tulajdonságokhoz:A lineáris idejű rendezési algoritmusok gyakran speciális követelményeket vagy feltételezéseket tartalmaznak a bemeneti elemekkel kapcsolatban. Például egy rendezési sorrend kiszámításához előre ismerni kell a bemeneti elemek tartományát. Ha ezek a feltételek teljesülnek, a lineáris idő szerinti rendezési algoritmusok jelentős teljesítményelőnyt kínálnak az általános rendezési algoritmusokhoz képest.Stabil rendezés:Számos lineáris idejű rendezési algoritmus, beleértve a numerikus és a radix rendezést is, eredendően stabil. A konzisztencia azt jelenti, hogy az ismétlődő kulcsokkal vagy értékekkel rendelkező elemek relatív sorrendet tartanak fenn a rendezett kimenetben. Ez kritikus lehet több attribútummal rendelkező objektumok vagy rekordok rendezésekor, vagy ha elengedhetetlen az azonos értékű elemek eredeti sorrendjének megőrzése.Egyszerű használat:A lineáris idő szerinti rendezési algoritmusok, mint például a felsorolás szerinti rendezés, gyakran viszonylag könnyen megvalósíthatók a bonyolultabb összehasonlításon alapuló rendezési algoritmusokhoz képest. Könnyebben érthetők és hibakereshetők, így alkalmasak olyan helyzetekre, ahol az egyszerűség és az egyértelműség kívánatos.

A lineáris idő szerinti rendezés hátrányai

Bár a lineáris ütemező algoritmusoknak megvannak az előnyei, vannak bizonyos korlátaik és hátrányaik is:

Korlátozó beviteli követelmények:A lineáris idő szerinti rendezési algoritmusok gyakran speciális követelményeket vagy feltételezéseket tartalmaznak a bemeneti elemekkel kapcsolatban. Például egy rendezési sorrend kiszámításához előre ismerni kell a bemeneti elemek tartományát. Ez a korlátozás azokra a helyzetekre korlátozza az alkalmazásukat, ahol ezek a feltételek teljesülnek. A memóriaigények kivitelezhetetlenné válhatnak, vagy meghaladhatják a rendelkezésre álló erőforrásokat, ha a tartomány kiterjedt vagy ismeretlen.További helyigény:Egyes lineáris idő szerinti rendezési algoritmusok, például a numerikus rendezés, további helyet igényelnek más tömbök vagy adatstruktúrák tárolására. A szükséges hely gyakran arányos a bemeneti elemek számával. Ez hátrányt jelenthet, ha a memóriahasználat problémát jelent, különösen akkor, ha nagy adatkészletekkel vagy korlátozott memóriaerőforrásokkal foglalkozik.Sokoldalúság hiánya:A lineáris idő szerinti rendezési algoritmusok speciális algoritmusok, amelyeket meghatározott forgatókönyvekhez vagy megszorításokhoz terveztek. Előfordulhat, hogy megfelelőbbnek és hatékonyabbnak kell lenniük az általános rendezési feladatokhoz vagy a különböző bemeneti elosztásokhoz. Az összehasonlításon alapuló rendezési algoritmusok, mint például a gyorsrendezés vagy egyesítés, sokoldalúbbak, és a beviteli tartományok szélesebb tartományát képesek kezelni.Nem hatékony kis tartományok vagy ritka adatok esetén:A lineáris idejű rendezési algoritmusok, mint például a felsorolás, akkor a leghatékonyabbak, ha a bemeneti elemek tartománya kicsi és sűrűn elosztott. Ha a tartomány kiterjedt vagy az adatok ritkák (azaz csak néhány különálló érték), az algoritmus időt és erőfeszítést takaríthat meg a bemeneti tartomány üres vagy ritkán lakott részei feldolgozásakor.Konkrét adattípusokra korlátozva:A lineáris idejű rendezési algoritmusok, mint például a felsorolásrendezés, elsősorban nem negatív egész számok vagy kulcsérték objektumok rendezésére szolgálnak. Előfordulhat, hogy nem alkalmasak más adattípusok, például lebegőpontos számok, karakterláncok vagy összetett adatstruktúrák rendezésére. A lineáris idő szerinti rendezési algoritmusok adaptálása a különböző adattípusok vagy egyéni összehasonlítási funkciók kezelésére további előfeldolgozást vagy módosítást igényelhet.

A rendezési algoritmus kiválasztásakor elengedhetetlen a bemeneti adatok sajátosságainak és a rendezési probléma követelményeinek gondos mérlegelése. Míg a lineáris ütemező algoritmusok bizonyos forgatókönyvekben előnyöket kínálnak, csak néha a legmegfelelőbb vagy leghatékonyabb választás.

Lineáris idő szerinti rendezési algoritmusok alkalmazásai

A lineáris idő szerinti rendezési algoritmusok hatékonyak és számos alkalmazási területtel rendelkeznek a különböző területeken. Íme néhány tipikus lineáris időrend alkalmazása:

Kis tartományú egész számok rendezése:A lineáris idő szerinti rendezési algoritmusok, mint például a számláló rendezés és a radix rendezés ideálisak egész számok tömbeinek rendezésére, ha az értékek tartománya. Ezek az algoritmusok lineáris időbeli összetettséget érnek el azáltal, hogy feltételezéseket tesznek a bemeneti adatokról, lehetővé téve számukra az összehasonlításon alapuló rendezés megkerülését.Karakterlánc rendezés:A lineáris idő szerinti rendezési algoritmusok a karakterláncok hatékony rendezésére is alkalmazhatók. A karakterláncok egyedi tulajdonságainak, például hosszának vagy karaktereinek figyelembevételével az olyan algoritmusok, mint a Radix Sort, lineáris időbonyolítást érhetnek el a karakterláncok rendezésekor.Adatbázis funkciók:A rendezés a lineáris idő szerinti rendezés alapvető funkciója. Ez gyorsabb lekérdezésfeldolgozást és jobb teljesítményt tesz lehetővé az adatbázis-műveletek során.Hisztogramok létrehozása:A hisztogramok elengedhetetlenek különféle statisztikai és adatelemzési feladatokhoz. A lineáris idő szerinti rendezési algoritmusok, mint például a numerikus rendezés, képesek hisztogramokat generálni azáltal, hogy hatékonyan megszámolják az adathalmaz elemeinek előfordulását.Külső rendezés:A külső rendezési technikát olyan esetekben használják, amikor az adatok nem férnek el teljesen a memóriában. A lineáris idő szerinti rendezési algoritmusok, például az External Radix Sort vagy az External Counting Sort hatékonyan rendezhetik a lemezen vagy más külső tárolóeszközökön tárolt nagy adatkészleteket.Esemény ütemezése:A lineáris idő szerinti rendezési algoritmusok ütemezhetik az eseményeket a kezdési vagy befejezési időpontjuk alapján. Az események növekvő sorrendben történő rendezése megkönnyíti az ütközések, az átfedő időszakok azonosítását vagy a következő elérhető időszak megtalálását.Naplófájlok elemzése:A naplófájlok elemzése gyakori feladat a rendszeradminisztráció és a hibakeresés során. Lineáris idő szerinti rendezési algoritmusok használhatók a naplók időbélyegek alapján történő rendezésére, megkönnyítve a minták, anomáliák azonosítását vagy az adott események keresését.Adattömörítés:A rendezés alapvető szerepet játszik a különböző adattömörítési technikákban. Az olyan algoritmusok, mint a Burrows-Wheeler Transform (BWT) vagy a Move-To-Front Transform (MTF) lineáris időrendre támaszkodnak az adatok átrendezésére a tömörítési hatékonyság javítása érdekében. Ez csak néhány példa a lineáris idő szerinti rendezési algoritmusok alkalmazására.

Lineáris idő szerinti rendezés megvalósítása C++ nyelven

Íme egy példa egy programra, amely megvalósítja a Counting Sort funkciót, amely egy lineáris idő szerinti rendezési algoritmus:

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

Ez azt jelzi, hogy a bemeneti tömb a Counting Sort algoritmussal növekvő sorrendbe lett rendezve, ami a rendezett tömböt [1, 2, 2, 3, 3, 4, 8] eredményezi.

Ebben a C++ programban a számláló rendezési függvény hivatkozik az arr vektorra, és futtatja a számláló rendezési rutint. Megkeresi a táblázat maximális értékét a munkalap méretének meghatározásához. Ezután megszámolja az egyes elemek előfordulását, és kiszámítja a munkalap előtagjának összegét. Ezután létrehoz egy eredményvektort, és a munkalapnak megfelelően sorrendbe állítja az elemeket. Végül a rendezett elemeket visszamásolja az eredeti tömbbe. Az elsődleges függvényben a {4, 2, 2, 8, 3, 3, 1} példatömböt a felsorolás-rendezési algoritmus rendezi, és rendezett mátrixként nyomtatja ki. Vegye figyelembe, hogy a program könyvtárakat használ a vektorokkal való munkavégzéshez, és a max_element függvény segítségével a tömb maximális elemének megtalálásához.