Hivatkozott lista rendezése

Linkelt lista rendezése . A rendezési algoritmusok túlnyomó többsége megköveteli a munkához, hogy a sorszám (index) alapján hozzáférjen a rendezett lista elemeihez. A linkelt listákban , ahol az elemeket rendezetlenül tárolják, egy elemhez a szám alapján hozzáférni meglehetősen erőforrás-igényes művelet, átlagosan összehasonlításokat és memóriaeléréseket igényel. Ennek eredményeként a tipikus rendezési algoritmusok használata rendkívül hatástalanná válik. A csatolt listáknak azonban megvan az az előnye, hogy két rendezett listát egyenként egyesíthetnek további memória használata nélkül.

Két rendezett lista összefűzése

Tegyük fel, hogy van egy egyedi hivatkozású listánk, amelynek elemeit egy struktúra írja le ( Pascal példa ):

írja be: PList_Item = ^ TList_Item ; TList_Item = rekord Kulcs : Integer ; Következő : PList_Item ; vége ; var Lista : PList_Item ; // Mutató a listára

Az algoritmus meglehetősen egyszerű: a bemeneten mutatók vannak a kombinált listák első elemeire. A legkisebb kulcsú elem kerül kiválasztásra a kapott lista elején. Ezután a kapott lista következő elemeiként az első vagy a második forráslista következő elemei kerülnek kiválasztásra, kisebb kulcsértékkel. Amikor az egyik beviteli lista utolsó elemét elérjük, az eredményül kapott lista utolsó elemének mutatója a másik beviteli lista többi részéhez áll.

függvény IntersectSorted ( const pList1 , pList2 : PList_Item ) : PList_Item ; var pCurItem : PList_Item ; p1 , p2 : PList_Item ; kezdődik p1 := pList1 ; p2 := pList2 ; ha p1 ^. Kulcs <= p2 ^. Billentyű , majd kezdődik a pCurItem := p1 ; p1 := p1 ^. következő ; end else begin pCurItem := p2 ; p2 := p2 ^. következő ; vége ; Eredmény := pCurItem ; míg a ( p1 <> nil ) és a ( p2 <> nil ) akkor kezdődik , ha p1 ^. Kulcs <= p2 ^. Billentyű , majd indítsa el a pCurItem ^ parancsot. Következő := p1 ; pCurItem := p1 ; p1 := p1 ^. következő ; vége else kezdődik pCurItem ^. Következő := p2 ; pCurItem := p2 ; p2 := p2 ^. következő ; vége ; vége ; ha p1 <> nulla , akkor pCurItem ^. Következő := p1 else pCurItem ^. Következő := p2 ; vége ;

Egyedül hivatkozott lista rendezése

A lista rendezésének folyamata a listán való szekvenciális áthaladás, az első elempárok, majd az egyes elempárok rendezése, 4 elemből álló listákba való összevonás, majd a kapott 8, 16 stb. elemből álló listák összevonása.

A javasolt megvalósítás egy halom listát használ. A szükséges veremméret [log 2 n ] + 1, ahol n a lista elemeinek száma. Ha az elemek száma nem ismert előre, akkor megfelelő veremmélység előre beállítható. Így például egy 32 elem mélységű verem akár 4 294 967 295 elem hosszúságú listák rendezésére is használható. A verem a lista rendezett részeire mutató mutatókat tárol, és a szint valójában log 2 i + 1, ahol i a lista adott részének elemeinek száma.

Az algoritmus lényege a következő: a listát szekvenciálisan bejárjuk, minden elemet degenerált listává alakítunk a következő elemre mutató mutató törlésével. Az így elkészített listára mutató mutató kerül a verembe, 1-es szinttel, majd ellenőrzés történik: ha a verem utolsó két eleme azonos szintértékű, akkor kikerül a veremből. , az ezen elemek által mutatott listák összevonásra kerülnek, és az eredményül kapott lista a verembe kerül az előzőnél eggyel magasabb szinten. Ez az unió addig ismétlődik, amíg az utolsó két elem szintje egyenlő nem lesz, vagy amíg el nem éri a verem tetejét. A kezdeti lista teljes bejárása után a veremben felsorolt ​​listák szintjüktől függetlenül kombinálódnak. Az unió eredményeként kapott lista a kívánt, az elemek rendezve

típus TSortStackItem = rekord Szint : Egész ; Elem : PList_Item ; vége ; var Stack : TSortStackItem [ 0..31 ] tömbje ; _ _ _ StackPos : Integer ; p : PList_Item ; start StackPos : = 0 ; p := Lista ; míg p <> nil do begin Verem [ StackPos ] . Szint := 1 ; Stack [ StackPos ] . Tétel := p ; p := p ^. következő ; Stack [ StackPos ] . ^ elem . Következő := null ; Inc ( StackPos ) ; míg ( StackPos > 1 ) és ( Stack [ StackPos - 1 ] . Level = Stack [ StackPos - 2 ] . Level ) elkezdi a Stack [ StackPos - 2 ] -t . Item := IntersectSorted ( Verem [ StackPos - 2 ] . Item , Stack [ StackPos - 1 ] . Item ) ; Inc ( Stack [ StackPos - 2 ] . Level ) ; dec ( StackPos ) ; vége ; vége ; míg a StackPos > 1 elkezdi a Stacket [ StackPos - 2 ] . Item := IntersectSorted ( Verem [ StackPos - 2 ] . Item , Stack [ StackPos - 1 ] . Item ) ; Inc ( Stack [ StackPos - 2 ] . Level ) ; dec ( StackPos ) ; vége ; ha StackPos > 0 , akkor List := Stack [ 0 ] . tétel ; vége ;

Az algoritmus összetettsége

Nyilvánvaló, hogy az algoritmus bonyolultsága O( n log n ), míg a memóriaigény minimális O(log n )

Duplán linkelt lista rendezése

Mivel a műveletek száma meghaladja a lista elemeinek számát, a legoptimálisabb megoldás a duplán linkelt lista rendezésekor, ha a listát egyedileg csatolt listaként rendezzük, csak a következő elemekre mutató mutatókat használva, majd a rendezés után visszaállítjuk a mutatókat az előzőre. elemeket. Egy ilyen művelet bonyolultsága mindig O(n).

írja be: PList_Item = ^ TList_Item ; TList_Item = rekord Kulcs : Integer ; Előző , Következő : PList_Item ; vége ; var // Mutatók a lista első és utolsó elemére First , Last : PList_Item ; p := Első ; // Ellenőrizze, hogy a lista nem üres- e, ha p <> nil , then begin p ^. Előző := null ; míg p ^. Következő <> null do kezdődik p ^. Következő ^. előz := p ; p := p ^. következő ; vége ; vége ; Utolsó := p ;

Lásd még

Irodalom