Sorterar en länkad lista

Länkad listsortering . De allra flesta sorteringsalgoritmer kräver för sitt arbete förmågan att komma åt elementen i den sorterade listan efter deras serienummer (index). I länkade listor , där element lagras oordnat, är det en ganska resurskrävande operation att komma åt ett element efter dess nummer, vilket kräver jämförelser och minnesåtkomster i genomsnitt. Som ett resultat blir användningen av typiska sorteringsalgoritmer extremt ineffektiv. Länkade listor har dock fördelen av att kunna slå samman två sorterade listor till en åt gången utan att använda ytterligare minne.

Sammankoppling av två ordnade listor

Låt oss säga att vi har en enkellänkad lista vars element beskrivs av en struktur ( Pascal- exempel ):

typ PList_Item = ^ TList_Item ; TList_Item = rekord Nyckel : Heltal ; Nästa : PList_Item ; slut ; var Lista : PList_Item ; // Pekare till listan

Algoritmen är ganska enkel: vid ingången finns pekare till de första elementen i de kombinerade listorna. Elementet med den minsta nyckeln väljs som början av den resulterande listan. Sedan, som nästa element i den resulterande listan, väljs de efterföljande elementen från den första eller andra källlistan, med ett mindre nyckelvärde. När det sista elementet i en av inmatningslistorna nås, sätts pekaren för det sista elementet i den resulterande listan till resten av den andra inmatningslistan.

function IntersectSorted ( const pList1 , pList2 : PList_Item ) : PList_Item ; var pCurItem : PList_Item ; p1 , p2 : PList_Item ; börja p1 := pList1 ; p2 := pList2 ; om p1 ^. Nyckel <= p2 ^. Nyckel börjar sedan pCurItem := p1 ; p1 := p1 ^. nästa ; end else start pCurItem := p2 ; p2 := p2 ^. nästa ; slut ; Resultat := pCurItem ; medan ( p1 <> noll ) och ( p2 <> noll ) börjar om p1 ^ . Nyckel <= p2 ^. Nyckel börjar sedan pCurItem ^. Nästa := p1 ; pCurItem := p1 ; p1 := p1 ^. nästa ; slut annars börja pCurItem ^. Nästa := p2 ; pCurItem := p2 ; p2 := p2 ^. nästa ; slut ; slut ; om p1 <> noll så pCurItem ^. Nästa := p1 annat pCurItem ^. Nästa := p2 ; slut ;

Sortera en enkellänkad lista

Processen att sortera en lista är en sekventiell passage genom listan, sortering av första par av element, sedan varje par av elementpar, kombineras till listor med 4 element, sedan kombineras de resulterande listorna med 8, 16, etc. element.

Den föreslagna implementeringen använder en stapel med listor. Den nödvändiga stackstorleken är [log 2 n ] + 1, där n är antalet element i listan. Om antalet element inte är känt i förväg, kan ett tillräckligt stackdjup ställas in i förväg. Så, till exempel, en stack 32 element djup kan användas för att sortera listor upp till 4 294 967 295 element långa. Stacken lagrar pekare till de sorterade delarna av listan, och nivån är egentligen log 2 i + 1, där i är antalet element i den delen av listan.

Kärnan i algoritmen är som följer: listan genomkorsas sekventiellt, där varje element konverteras till en degenererad lista genom att radera pekaren till nästa element. En pekare till listan som skapats på detta sätt skjuts upp på stacken, med nivån inställd på 1, varefter en kontroll görs: om de två sista elementen i stacken har samma nivåvärde, så tas de från stacken. , listorna som pekas på av dessa element slås samman och den resulterande listan skjuts upp i stacken på en nivå som är en högre än den föregående. Denna förening upprepas tills nivåerna för de två sista elementen är lika, eller tills toppen av stapeln nås. Efter att den första listan har passerats fullständigt, kombineras listorna som listas i stacken, oavsett deras nivå. Listan som resulterar från facket är den önskade, med elementen sorterade

typ TSortStackItem = post Nivå : Heltal ; Objekt : PList_Item ; slut ; var Stack : Array [ 0..31 ] av TSortStackItem ; _ _ StackPos : Heltal ; p : PList_Item ; börja StackPos := 0 ; p := Lista ; medan p < > noll börjar Stack [ StackPos ] . Nivå := 1 ; Stack [ StackPos ] . Objekt := p ; p := p ^. nästa ; Stack [ StackPos ] . Objekt ^. Nästa := noll ; Inc ( StackPos ) ; medan ( StackPos > 1 ) och ( Stack [ StackPos - 1 ] . Level = Stack [ StackPos - 2 ] . Level ) börjar Stack [ StackPos - 2 ] . _ Objekt := IntersectSorted ( Stack [ StackPos - 2 ] . Objekt , Stack [ StackPos - 1 ] . Objekt ) ; Inc ( Stack [ StackPos - 2 ] . Nivå ) ; Dec ( StackPos ) ; slut ; slut ; medan StackPos > 1 börjar Stack [ StackPos - 2 ] . _ Objekt := IntersectSorted ( Stack [ StackPos - 2 ] . Objekt , Stack [ StackPos - 1 ] . Objekt ) ; Inc ( Stack [ StackPos - 2 ] . Nivå ) ; Dec ( StackPos ) ; slut ; om StackPos > 0 då List := Stack [ 0 ] . Objekt ; slut ;

Algoritmens komplexitet

Uppenbarligen är komplexiteten för algoritmen O( n log n ), medan minneskraven är minimala O(log n )

Sortera en dubbellänkad lista

Eftersom antalet operationer överstiger antalet element i listan, är den mest optimala lösningen vid sortering av en dubbellänkad lista att sortera listan som en enkellänkad lista, endast använda pekare till efterföljande element, och efter sortering återställa pekare till tidigare element. Komplexiteten i en sådan operation är alltid O(n).

typ PList_Item = ^ TList_Item ; TList_Item = rekord Nyckel : Heltal ; Föregående , Nästa : PList_Item ; slut ; var // Pekare till det första och sista elementet i listan First , Last : PList_Item ; p := Först ; // Kontrollera om listan inte är tom om p <> noll , börja sedan p ^. Föregående := noll ; medan p ^. Nästa <> noll börjar p ^ . Nästa ^. föregående := p ; p := p ^. nästa ; slut ; slut ; Sista := p ;

Se även

Litteratur