Sortarea unei liste legate

Sortarea listelor legate . Marea majoritate a algoritmilor de sortare necesită pentru munca lor capacitatea de a accesa elementele listei sortate după numerele lor de serie (indexuri). În listele legate , în care elementele sunt stocate neordonate, accesarea unui element după numărul său este o operațiune destul de intensivă în resurse, care necesită comparații și accesări la memorie în medie. Ca urmare, utilizarea algoritmilor tipici de sortare devine extrem de ineficientă. Cu toate acestea, listele legate au avantajul de a putea îmbina două liste sortate într-o singură dată, fără a utiliza memorie suplimentară.

Concatenarea a două liste ordonate

Să presupunem că avem o listă cu legături unice ale cărei elemente sunt descrise printr-o structură ( exemplu Pascal ):

tip PList_Item = ^ TList_Item ; TList_Item = înregistrare Cheie : Integer ; Următorul : PList_Item ; sfârşitul ; var Listă : PList_Item ; // Indicator către listă

Algoritmul este destul de simplu: la intrare există pointeri către primele elemente ale listelor combinate. Elementul cu cea mai mică cheie este selectat ca început al listei rezultate. Apoi, ca elemente următoare ale listei rezultate, sunt selectate elementele ulterioare din prima sau a doua listă sursă, cu o valoare de cheie mai mică. Când se ajunge la ultimul element al uneia dintre listele de intrare, indicatorul ultimului element al listei rezultate este setat la restul celeilalte liste de intrare.

funcția IntersectSorted ( const pList1 , pList2 : PList_Item ) : PList_Item ; var pCurItem : PList_Item ; p1 , p2 : PList_Item ; începe p1 := pList1 ; p2 := pList2 ; dacă p1 ^. Tasta <= p2 ^. Tasta apoi începe pCurItem := p1 ; p1 := p1 ^. următorul ; end else begin pCurItem := p2 ; p2 := p2 ^. următorul ; sfârşitul ; Rezultat := pCurItem ; în timp ce ( p1 <> nil ) și ( p2 <> nil ) încep dacă p1 ^ . Tasta <= p2 ^. Tasta apoi începe pCurItem ^. Următorul := p1 ; pCurItem := p1 ; p1 := p1 ^. următorul ; end else begin pCurItem ^. Următorul := p2 ; pCurItem := p2 ; p2 := p2 ^. următorul ; sfârşitul ; sfârşitul ; dacă p1 <> nil atunci pCurItem ^. Următorul := p1 else pCurItem ^. Următorul := p2 ; sfârşitul ;

Sortarea unei liste cu legături individuale

Procesul de sortare a unei liste este o trecere secvențială prin listă, sortând primele perechi de elemente, apoi fiecare pereche de perechi de elemente, combinându-se în liste de 4 elemente, apoi listele rezultate de 8, 16, etc. elemente sunt combinate.

Implementarea propusă utilizează un teanc de liste. Dimensiunea necesară a stivei este [log 2 n ] + 1, unde n este numărul de elemente din listă. Dacă numărul de elemente nu este cunoscut în prealabil, atunci o adâncime suficientă a stivei poate fi setată în avans. Deci, de exemplu, o stivă de 32 de elemente adâncime poate fi folosită pentru a sorta liste cu o lungime de până la 4.294.967.295 de elemente. Stiva stochează pointeri către părțile sortate ale listei, iar nivelul este de fapt log 2 i + 1, unde i este numărul de elemente din acea parte a listei.

Esența algoritmului este următoarea: lista este parcursă secvențial, fiecare element fiind convertit într-o listă degenerată prin ștergerea indicatorului către următorul element. Un pointer către lista creată în acest fel este împins pe stivă, cu nivelul setat la 1, după care se face o verificare: dacă ultimele două elemente ale stivei au aceeași valoare de nivel, atunci sunt scoase din stivă. , listele la care indică aceste elemente sunt îmbinate, iar lista rezultată este împinsă pe stivă la un nivel unul mai mare decât cel precedent. Această unire se repetă până când nivelurile ultimelor două elemente sunt egale sau până când se ajunge la vârful stivei. După ce lista inițială a fost complet parcursă, listele listate în stivă sunt combinate, indiferent de nivelul lor. Lista rezultată din unire este cea dorită, cu elementele sortate

tip TSortStackItem = record Level : Integer ; Item : PList_Item ; sfârşitul ; var Stack : Matrice [ 0 .. 31 ] din TSortStackItem ; StackPos : Integer ; p : PList_Item ; începe StackPos := 0 ; p := Lista ; în timp ce p < > nil începe Stack [ StackPos ] . Nivel := 1 ; Stack [ StackPos ] . Item := p ; p := p ^. următorul ; Stack [ StackPos ] . Articol ^. Următorul := nil ; Inc ( StackPos ) ; în timp ce ( StackPos > 1 ) și ( Stack [ StackPos - 1 ] . Level = Stack [ StackPos - 2 ] . Level ) încep Stack [ StackPos - 2 ] . Item := IntersectSorted ( Stiva [ Stiva Poz. - 2 ] . Articol , Stivă [ Poz.Stivă - 1 ] . Articol ) ; Inc ( Stivă [ StackPos - 2 ] . Nivel ) ; Dec ( StackPos ) ; sfârşitul ; sfârşitul ; în timp ce StackPos > 1 începe Stack [ StackPos - 2 ] . Item := IntersectSorted ( Stiva [ Stiva Poz. - 2 ] . Articol , Stivă [ Poz.Stivă - 1 ] . Articol ) ; Inc ( Stivă [ StackPos - 2 ] . Nivel ) ; Dec ( StackPos ) ; sfârşitul ; dacă StackPos > 0 atunci List := Stack [ 0 ] . articol ; sfârşitul ;

Complexitatea algoritmului

Evident, complexitatea algoritmului este O( n log n ), în timp ce cerințele de memorie sunt minime O(log n )

Sortarea unei liste dublu legate

Întrucât numărul de operații depășește numărul de elemente din listă, cea mai optimă soluție atunci când sortați o listă dublu legată este să sortați lista ca o listă unică legată, folosind doar pointeri către elementele ulterioare și, după sortare, restaurați pointerii la anterioare. elemente. Complexitatea unei astfel de operații este întotdeauna O(n).

tip PList_Item = ^ TList_Item ; TList_Item = înregistrare Cheie : Integer ; Anterior , Următorul : PList_Item ; sfârşitul ; var // Indicatori către primul și ultimul element al listei First , Last : PList_Item ; p := Prima ; // Verificați dacă lista nu este goală dacă p <> nil atunci începe p ^. Anterior := nil ; în timp ce p ^. Următorul <> nu începe p ^ . Următorul ^. prev := p ; p := p ^. următorul ; sfârşitul ; sfârşitul ; Ultimul := p ;

Vezi și

Literatură