Behov av att sortera data uppkommer i ett otal sammanhang. Sorteringsproblemet hör till datalogins allra viktigaste. Hyllmetrar har skrivits och publicerats om ämnet. Det finns inte någon seriös bok om algoritmer som inte innehåller ett eller flera kapitel om sortering. Däremot brukar det få styvmoderlig behandling i vanliga pascalläroböcker. Detta är ett skäl till att vi här ägnar det ett relativt stort utrymme. Ett annat är att sökandet efter olika sorteringsmetoder, och ansträngningarna att förbättra dem, rör centrala frågor om algoritmkonstruktion och programmering överhuvudtaget.
Vi ska också exemplifiera några mer avancerade programmeringsmetoder och språkelement. Detta gäller bl a dynamiska variabler (som i läroböcker ofta uteslutande berörs i samband med länkade strukturer, men som med fördel kan användas även i andra sammanhang), samt en del "lågnivåprogrammering" och Turbo-specialiteter. Vi kommer bl a att titta på hur man kan skapa helt datatypsoberoende (s k generiska) sorteringsrutiner.
Sortering kan antingen utföras i primärminnet eller på yttre enheter (filer). När datamängden ryms i datorns primärminne föredras nästan alltid minnessortering. Vid filsortering tillkommer nämligen ett mycket tidsödande element: läsning och skrivning på den yttre enheten. Man försöker därför undvika rena filsorteringsmetoder. Skulle datamängden vara för stor för att kunna hanteras i minnet kan ursprungsfilen "splittras upp" i delar som var för sig sorteras med minnessorteringsmetoder, varefter de sorterade delfilerna samsorteras på disk. Under senare år har dessutom s k virtuell minnesteknik blivit allt vanligare, varvid minnessortering kan utnyttjas även om inte hela datamängden får rum i arbetsminnet.
Mycket talar således för att det är rätt och rimligt att börja med de viktigaste och vanligaste grundläggande minnessorteringsalgoritmerna. För att inte kapitlet ska bli alltför långrandigt har genomgången gjorts ganska summarisk.
När grunderna avklarats tar vi oss an några mer speciella och intrikata sorteringsproblem (såsom generiska sorteringsrutiner). Därefter står filsorteringsproblematiken på dagordningen och kapitlet avrundas med några ord om metoder som kan komma till användning vid konstruktion av program av typen databaser (register).
I större delen av kapitlet kommer vi att utnyttja följande datatyper:
type
Index = 1..maxNum; (* maxNum = maxantalet element *))
KeyType = (* användardefinierat *)
DataType = (* --- " --- *)
ElementType = record
key : KeyType;
data: DataType;
end;
Vid minnessortering ligger elementen för det mesta i en länkad
lista eller en array. Vi inskränker oss här till det senare:
type ElementArray = array [Index] of ElementType;
Vi förutsätter att sorteringen ska göras m a p key-fältet
(se typdeklarationerna ovan). För enkelhets skull antar vi att key-fältet
har typen Integer, Real, string
eller array of Char. Denna inskränkning
är i och för sig inte nödvändig, men gör att vi
lättare kan koncentrera oss på sorteringsalgoritmerna som sådana,
dvs vi slipper ägna hanteringen av sorteringsnycklarna speciell uppmärksamhet.
De flesta sorteringsalgoritmerna kan hänföras till en av 3 huvudgrupper: sortering genom urval, genom insättning och genom utbyte. Inom var och en av dessa grupper finns metoder som inbördes är mycket olika i fråga om prestanda och komplexitet. Allmänt gäller att de mer effektiva algoritmerna också är mer komplicerade och därför svårare att programmera och förstå. Vi kommer att exemplifiera dessa "ytterligheter".
Ett mått på en sorteringsalgoritms effektivitet erhålls om man bestämmer hur många jämförelser och elementförflyttningar (byten) som måste göras för att sortera ett visst antal element. För att avgöra vilken metod som är "bäst" i ett visst sammanhang räcker dock inte en sådan analys. Det är också nödvändigt att ta hänsyn till vilken typ av data som ska sorteras. En metod som generellt sett är mindre effektiv än en annan kan mycket väl vara betydligt bättre för vissa typer av data. De allra effektivaste sorteringsmetoderna tar hänsyn till detta genom att kombinera olika sorteringsalgoritmer.
Ett sätt att sortera är att först leta upp det minsta elementet och låta detta byta plats med det första, varefter det näst minsta söks upp och byts med det andra elementet osv, ända tills dess hela datamängden är sorterad.
I engelskspråkig litteratur kallas detta för Selection Sort (urvalssortering). Algoritmen kan kodas så här (n = antalet arrayelement):
procedure SelectionSort(var a: ElementArray; n: Integer);
var
i, j, indx: Integer;
min: ElementType;
begin
for i:= 1 to num-1 do begin
indx:= i;
min:= a[indx];
for j:= i+1 to num do
if a[j].key < min.key then begin
min:= a[j];
indx:= j;
end (* if *);
a[indx]:= a[i];
a[i]:= min;
end (* for *);
end (* SelectionSort *);
Urvalssorteringsalgoritmen är enkel, men inte särskilt effektiv. Detta beror främst på det stora antalet jämförelser som måste göras (storleksordningen n2). Å andra sidan är antalet utbyten av storleksordningen n. Metoden fungerar därför jämförelsevis bra om elementen (posterna) innehåller mycket data (och alltså är kostsamma att förflytta), samtidigt som sorteringsnycklarna är korta (dvs enkla att jämföra).
En annan metod som bygger på urval är Heapsortering. Denna utnyttjar dock en betydligt effektivare datastruktur än urvalssorteringen, nämligen ett binärt träd, där varje "förälder" är större än eller lika med sina "barn" (dvs största elementet finns i trädets rot). En sådan datastruktur kallas för en heap (hög).
Binära träd kan representeras sekventiellt i en array genom
att placera roten i position 1, dess barn i positionerna 2 och 3, noderna
i nästa nivå i positionerna 4, 5, 6 och 7 osv. Detta gör
det enkelt att gå från en viss nod till dess "förälder"
eller "barn": "föräldern" till noden i position j finns i position
j div 2 och de 2 "barnen" i positionerna 2j resp 2j + 1.
Heapsorteringen sker i två steg. Först placeras data i en heap och sedan hämtas data från heapen i sorterad ordning.
Antalet jämförelser och förflyttningar är med denna algoritm av storleksordningen n * 2log(n), vilket är mycket bra. I själva verket kan det, med den typ av sorteringsalgoritmer som behandlas här, inte bli bättre. Metoden innehåller dock en ganska komplex "inre loop", vilket gör att den inte tillhör de allra snabbaste. Å andra sidan spelar det relativt liten roll hur ursprungsdata är ordnade. Flera andra sorteringsmetoder kan i extremfall ge mångdubblade sorteringstider mot normalt.
procedure HeapSort(var a: ElementArray; num: Integer);
var
temp: ElementType;
i: Integer;
procedure Adjust(i, n: Integer);
var
temp: ElementType;
j: Integer;
finished: Boolean;
begin
finished:= false;
temp:= a[i];
j:= 2*i;
while (j <= n) and not finished do begin
if j < n then (* Finn max av vä o hö barn *)
if a[j].key < a[j+1].key then
Inc(j);
if temp.key >= a[j].key then
finished:= true (* Klart om temp > max *)
else begin
a[j div 2]:= a[j]; (* Flytta upp posten j *)
j:= 2*j
end (* if *);
end (* while *);
a[j div 2]:= temp;
end (* Adjust *);
begin (* HeapSort *)
for i:= num div 2 downto 1 do
Adjust(i, num); (* Konstruera heapen *)
for i:= (num-1) downto 1 do begin
temp:= a[1]; a[1]:= a[i+1]; a[i+1]:= temp;
Adjust(1, i); (* Återskapa heapen *)
end (* for *);
end (* HeapSort *);
Insticksalgoritmen bygger på att en "lista" kan ses som två dellistor, där den ena är sorterad och den andra inte. Sorteringen sker genom att plocka ut ett element i taget ur den osorterade dellistan och infoga det på rätt plats i den sorterade dellistan, som därmed utvidgas med ett element i taget. Metoden påminner om det sätt på vilket kortspelare ofta ordnar sina spelkort.
procedure InsertSort(var a: ElementArray; n: Integer);
var
i, j: Integer;
temp: ElementType;
begin
for i:= 2 to n do begin
temp:= a[i];
j:= i;
while (j >= 2) and (temp.key < a[j-1].key) do begin
a[j]:= a[j-1]; (* Bered plats för temp *)
Dec(j);
end (* while *);
a[j]:= temp (* Insätt på rätt plats *)
end (* for *);
end (* InsertSort *);
I rutinen ovan föreligger emellertid ett problem, beroende på
det sätt på vilket Pascal vanligen utvärderar villkorssatser.
Antag att det element som ska insorteras är mindre än a[1]. Då
får j värdet 1 och loopen avbryts p g a första villkoret
i while-satsen - eller hur? Nja, men även det andra villkoret kommer
att testas, dvs temp.key < a[0] - och något element med index
0 existerar inte! Det finns flera möjligheter att komma runt problemet.
Man kan t ex ge arrayen ett extra element med index 0, som då inte
används för att lagra något element. I Turbo kan man också
helt enkelt strunta i problemet, ty rutinen fungerar om man utnyttjar s
k kortslutning (kompileringsdirektivet B-).
Ett annat sätt är att införa en vaktpost. Med en sådan
kan också det första villkoret i inre loopen avvaras: Vaktposten
kan väljas så att den garanterat är mindre (eller lika
med) det minsta elementen i listan och placeras i a[0]. Denna lösning
kräver dock att arrayen förses med ett extra element. Om vi i
stället börjar med att söka reda på det minsta elementet
och placerar detta först (i a[1]), behövs varken ett extra element
eller en extra position. Denna modifiering har genomförts på programdisketten.
En stor "flaskhals" är de omfattande datatransporter som det
kan bli fråga om i den inre loopen. Om dessa effektiviseras kan mycket
tid sparas. En sådan möjlighet föreligger i Turbo Pascal:
Med Move-proceduren sker kopiering från en variabel till en annan
mycket snabbt. Om vi utnyttjar både vaktpost och Move kan while-loopen
skrivas:
while temp.key < a[j-1].key do Dec(j);
Dataförflyttningarna görs "i klump" efter while-loopen:
if j < i then Move(a[j], a[j+1], SizeOf(ElementType)*(i-j));
Med Move sänks sorteringstiden för 1000 element med över
40% för heltal och ännu mer då det är fråga
om flyttal eller andra större datatyper.
När är insticksmetoden lämplig att använda?
Den yttre loopen genomlöps alltid n-1 gånger, men utförandet
av den inre beror både på j-värdet och på hur rådata
är "sorterade". I bästa fall (sorterade data) utförs den
inte alls och i värsta fall av storleksordningen n¨ gånger.
Metoden är således inte särskilt effektiv i det allmänna
fallet. Bäst fungerar den för "nästan sorterade data".
En trevlig egenskap hos insticksmetoden är att den lämnar den inbördes ordningen mellan lika sorteringsnycklar oförändrad, vilket betyder att en array som sorteras 2 ggr efter olika sorteringsnycklar blir sorterad efter båda.
En effektivare sorteringsalgoritm, tillhörande familjen insättningsmetoder, är Shellsortering. I denna jämförs och byts först data som ligger långt från varandra. När inga fler utbyten kan göras halveras steglängden, och jämförelserna/utbytena återupptas. På detta sätt minskas steglängden successivt tills dess denna är 1 (data som ligger intill varandra jämförs).
Metodens effektivitet beror en hel del på valet av startsteglängden. Vanligt är att börja med en steglängd som är ungefär lika med halva antalet element:
procedure ShellSort(var a: ElementArray; n: Integer);
var
i, k, step: Integer;
temp: ElementType;
swapped: Boolean;
begin
step:= n;
while step > 1 do begin
step:= step div 2; (* halvera steglängden *)
repeat
swapped:= false;
for i:= 1 to n - step do begin
k:= i+step; (* stega *)
if a[i].key > a[k].key then begin (* byt *)
temp:= a[i]; a[i]:= a[k]; a[k]:= temp;
swapped:= true;
end (* if *);
end (* for *);
until not swapped
end (* while *);
end (* ShellSort *);
Med bättre startsteglängd förbättras metodens prestanda. En bra sådan erhålls om man väljer ett tal av typen 2p - 1, där exponenten p ska uppfylla villkoret att 2p är den största 2-potens som är mindre än antalet element (dvs 2p < n < 2(p+1)). Denna förbättring, och ett par andra, är införd i diskettversionen.
Shellsortering intar en mellanställning mellan de enklare och de mest komplicerade (och effektivaste) sorteringsalgoritmerna. Metoden är inte heller speciellt svår att förstå eller implementera, varför den passar bra för att sortera "medelstora" datamängder. Dessa trevliga egenskaper förklarar dess stora popularitet.
Betrakta en lista med osorterade data (t ex tal) som ska ordnas i storleksordning (de minsta först). Vi börjar med att jämföra de 2 första elementen och om element 1 är större än element 2 får de byta plats. Sedan jämförs element 2 och 3 och vi byter om 2:an är större än 3:an. Vi fortsätter på detta sätt till dess de 2 sista talen jämförts och eventuellt fått byta plats. Sedan startar vi med element 1 igen och upprepar hela proceduren. Detta fortgår tills dess hela listan genomlöpts utan att något utbyte gjorts. Då är det färdigsorterat. Denna sorteringsmetod, som kallas för bubbelsortering, brukar behandlas i de flesta grundläggande läroböcker i programmering.
procedure BubbleSort(var a: ElementArray; num: Integer);
var
i: Integer;
temp: ElementType;
sorted: Boolean;
begin
sorted:= false;
while not sorted do begin
sorted:= true; (* Antar att det är sorterat *)
for i:= 1 to num - 1 do
if a[i].key > a[i+1].key then begin (* Byt *)
temp:= a[i]; a[i]:= a[i+1]; a[i+1]:= temp;
sorted:= false (* Det var ej sorterat *)
end (* if *);
end (* for *);
end (* BubbleSort *);
Algoritmen kan göras effektivare. Det är t ex inte nödvändigt att gå igenom hela listan varje gång (inre loopen), ty efter första genomlöpningen måste ju det sista elementet vara på rätt plats, efter andra omgången de 2 sista osv. Det finns även några andra "trick" som kan tillgripas för att förbättra prestanda.
Hur vi än bär oss åt kvarstår dock faktum: Bubbelsortering är den ineffektivaste av de metoder vi behandlat hittills: " i själva verket finns knappast något som talar till bubbelsorteringens fördel, utom dess klatschiga namn" (N. Wirth 1976).
Det finns alltså ingen anledning att använda bubbelsortering. P g a dess enkelhet kan den vara lämplig att ta upp i nybörjarböcker vid introduktion av sorteringsbegreppet, men låt den förbli där.
Den grundläggande tanken bakom Quicksorteringsalgoritmen är följande: Ett element ("pivot"-elementet) väljs ut, varefter listan omstruktureras så att det urplockade elementet hamnar på rätt plats och övriga "på rätt sida" om detsamma. Därmed blir listan indelad i 2 dellistor, som var för sig kan sorteras på samma sätt, osv ... Detta leder naturligt till en rekursiv algoritm.
Delningen kan utföras så här:
En Pascal-implementering av metoden:
procedure QuickSort(var a: ElementArray; l, r: Integer);
var
i, (* index för att söka från vänster *)
j: Integer; (* index för att söka från höger *)
pivotKey: KeyType;
temp: ElementType; (* för temporär lagring vid byte *)
begin (* QuickSort *)
(* Init index för sökning från vänster resp höger *)
i:= l; j:= r;
pivotKey:= a[(l+r) div 2].key;
repeat (* Så länge som sökningarna ej "mötts" *)
while a[i].key < pivotKey do (* Sök från vänster *)
Inc(i);
while pivotKey < a[j].key do (* Sök från höger *)
Dec(j);
if i <= j then begin (* Byt *)
temp:= a[i]; a[i]:= a[j]; a[j]:= temp;
Inc(i); Dec(j);
end (* if *)
until i > j;
if l < j then
QuickSort(a, l, j); (* Sortera vänster dellista *)
if i < r then
QuickSort(a, i, r); (* Sortera höger dellista *)
end (* QuickSort *);
Liksom för Heapsortering är antalet jämförelser och byten (normalt) av storleksordningen n * 2log(n). Om vi bortser från extremt ogynnsamma utgångsdata, då Quick-metoden kan degenerera till en "n2-algoritm", är den effektivare än Heap-metoden. Quicksortering är, generellt sett, den snabbaste av alla kända minnessorteringsalgoritmer. Det betyder inte att metoden alltid är effektivast. För korta listor kan instickssortering eller urvalssortering vara att föredra, ty deras "overhead" är betydligt mindre.
Den ursprungliga algoritmen kan förbättras på tre punkter:
På programdisketten finns en variant (Quicker), där samtliga dessa punkter implementerats.
Vi ska nu titta på en sorteringsmetod som inte kan räknas till någon av de 3 huvudgrupperna. Den är intressant av flera anledningar. Dels är den en av de snabbare, dels kan den grundläggande algoritmen även utnyttjas vid sortering av sekventiella filer.
Vi börjar med ett enklare problem: samsortering av två (sorterade) arrayer (a och b) till en enda (c). Detta kan utföras med följande algoritm:
Det är således ganska enkelt att samsortera 2 arrayer (algoritmen kan ytterligare förenklas med införandet av en "vaktpost"). Men hur göra om vi har bara en (1) osorterad array att utgå ifrån?
Det finns flera möjligheter. Ett sätt är att från början betrakta varje enskild post som en sorterad dellista med längden 1. Dessa dellistor samsorteras parvis till dellistor av längden 2, dessa i sin tur till dellistor av längden 4 osv tills dess en enda sorterad lista erhållits. Denna algoritm kallas för Mergesortering:
procedure MergeSort(var a: ElementArray; n: Integer);
var
subLen: Integer; (* Dellistornas längd *)
tempList: ElementArray; (* Temporär array under sorteringen *)
(*--------------------------------------------------------------*)
procedure Merge(subLen, n: Integer; var a, tempList: ElementArray);
(* Sorterade dellistor med längden subLen samsorteras till del- *)
(* listor av längd 2*subLen. Resultatet lagras i tempList. *)
(*--------------------------------------------------------------*)
var
tIndx, (* Index för tempList *)
k1, k2, (* Index för dellista 1 resp 2 *)
end1, end2: Integer; (* Slutindex för dellista 1 resp 2 *)
begin
k1:= 1; k2:= subLen+1; tIndx:= 1;
repeat
end1:= k1+subLen; (* Slutindex för dellista 1 *)
if end1 > n then (* Enbart en lista finns *)
end1:= n+1 (* Fungerar som "vaktpost" *)
else begin
end2:= k2+subLen; (* Andra lista finns *)
if end2 > n then end2:= n+1;
repeat (* Dellistorna samsorteras tills en slut *)
if a[k1].key <= a[k2].key then begin
tempList[tIndx]:= a[k1];
Inc(tIndx);
Inc(k1);
end
else begin
tempList[tIndx]:= a[k2];
Inc(tIndx);
Inc(k2);
end (* if *);
until (k1 = end1) or (k2 = end2);
end (* if *);
if k1 < end1 then
repeat (* kopiera posterna i icke-tomma dellistan *)
tempList[tIndx]:= a[k1];
Inc(tIndx);
Inc(k1)
until k1 = end1
else
repeat
tempList[tIndx]:= a[k2];
Inc(tIndx);
Inc(k2)
until k2 = end2;
k1:= k2; k2:= k2+subLen;
until k1 > n;
end (* Merge *);
begin (* MergeSort *)
subLen:= 1; (* Dellistornas längd vid start *)
if n > 3 then
repeat
Merge(subLen, n, a, tempList);
subLen:= 2*subLen; (* Fördubbla dellistornas längd *)
Merge(subLen, n, tempList, a);
subLen:= 2*subLen;
until subLen > n div 2;
if subLen < n then begin
Merge(subLen, n, a, tempList);
a:= tempList; (* Kopiera hela tempList till a *)
end (* if *);
end (* MergeSort *);
Metoden är förvånansvärt (?) snabb. Dessutom är den i det närmaste okänslig för hur ursprungsdata är ordnade. Mergesortering har dock en avgörande nackdel: Den kräver ungefär dubbelt så mycket minne som övriga algoritmer (en hel extra upplaga av den ursprungliga arrayen).
Vi har nu studerat ett representativt urval av sorteringsmetoder. Det finns givetvis fler, av vilka Radixsortering och sortering med utnyttjande av ett ordnat binärt träd är de intressantaste. Dessa två hör dock intimt samman med länkade strukturer, varför de bäst avhandlas i samband med sådana (den senare metoden tas upp i kapitlet om datastrukturer).
Av de algoritmer som behandlats här är i allmänhet Quicksortering effektivast. För små datamängder kan dock instickssortering (om posterna är små) eller urvalssortering (om posterna är stora) vara att föredra. I många fall är Shellsortering en bra "kompromiss". Övriga sorteringsmetoder är mer av allmänt intresse.
ProgramdiskettenSORTDEMO.PAS ger tillfälle att studera samtliga sorteringsmetoder som behandlats ovan. Sorteringsprocedurerna ligger i separata include-filer, som hanteras med Overlay-teknik. I programmet är |
Om sorteringsposterna är stora krävs mycket datatransporter vid de erforderliga bytena. Ett sätt att undvika detta är att bilda en ny array (vektor) innehållande posternas index. Denna array kan vi kalla för accessvektor eller indexarray. Vid sorteringen behöver sedan enbart elementen i indexarrayen (dvs heltal) byta plats. Med tillägg för den tid som åtgår för initieringen av indexarrayen, samt för att komma åt sorteringsfälten och göra jämförelserna mellan aktuella sorteringsnycklar, bör sorteringen med detta "trick" ske lika snabbt som om enbart heltal sorterats.
Metodens baksidor är att det behövs en extra array (indexarrayen) och att den ursprungliga arrayen ju egentligen förblir osorterad, vilket kan vara en nackdel om vidare bearbetning ska göras. Å andra sidan kan metoden lätt utvidgas så att data hålls sorterade efter flera olika nycklar samtidigt (en extra indexarray/sorteringsnyckel).
Indexarray kan i princip användas tillsammans med vilken sorteringsalgoritm som helst, men det är främst i kombination med de mer avancerade metoderna (Shell- och Quicksortering) som det brukar bli aktuellt.
Här ska vi kombinera indexarray med Shellsortering.
En extra typdeklaration behövs:
type IndexArray = array [Index] of Index;
Dessutom måste indexarrayen initieras. Detta görs nedan i sorteringsproceduren, men det kan lika gärna ordnas i det anropande programmet.
procedure ShellIxSort(var a: ElementArray;
var ix: IndexArray; n: Integer);
var
i, k, step, temp: Integer;
swapped: Boolean;
begin
for i:= 0 to n do ix[i]:= i; (* Initierar indexarrayen *)
step:= n;
while step > 1 do begin
step:= step div 2;
repeat
swapped:= false;
for i:= 1 to n - step do begin
k:= i+step;
if a[ix[i]].key > a[ix[k]].key then begin (* Byt *)
temp:= ix[i]; ix[i]:= ix[k]; ix[k]:= temp;
swapped:= true;
end (* if *);
end (* for *);
until not swapped
end (* while *);
end (* ShellIxSort *);
Jämför med den ursprungliga Shellsorteringsrutinen. Som synes är ändringarna små.
Eftersom den ursprungliga arrayen egentligen förblir "osorterad", måste indexarrayen utnyttjas för åtkomst av elementen i sorterad ordning, t ex för utskrift:
for i:= 1 to n do WriteLn(a[ix[i]]);
Om elementarrayen behöver omstruktureras efter sorteringen,
kan det lätt åstadkommas med utnyttjande av en extra ElementArray,
säg tempX, som först tilldelas den ursprungliga arrayen (a).
Sedan används indexarrayen för att plocka elementen från
tempX, och placeras i originalarrayen i sorterad ordning.
En nackdel med denna enkla metod är att det krävs en extra upplaga av originalarrayen. Det är dock möjligt att ordna omstruktureringen "på stället", dvs utan en extraarray:
procedure Rearrange(var a: ElementArray;
var ix: IndexArray; n: Integer);
var
i, j, k: Integer;
temp: ElementType;
begin
for i:= 1 to n-1 do
if ix[i] <> i then begin
temp:= a[i];
j:= i;
repeat
k:= ix[j]; a[j]:= a[k]; ix[j]:= j; (* Byt *)
j:= k;
until ix[j] = i;
a[j]:= temp;
ix[j]:= j;
end (* if *);
end (* Rearrange *);
Ytterligare ett sätt att göra omstruktureringen är att först skriva ut elementen på en fil i sorterad ordning och sedan inläsa dem på nytt i ursprungsarrayen. Denna metod är särskilt attraktiv om RAM-disk är tillgänglig, eftersom prestanda därmed blir jämförelsevis goda.
Omstrukturering, särskilt upprepad sådan, bör undvikas, ty om posterna är stora tar den ofta betydligt längre tid än själva sorteringen, särskilt om den görs "på stället". Många detaljer kan avklaras via indexarrayen, t ex skriva ut elementen i sorteringsordning på skärm, skrivare eller en fil. Även binärsökning kan göras med utnyttjande av indexarrayen.
Vid all sortering jämförs sorteringsnycklar. Vi har hittills
haft att göra med mycket enkla sorteringsvillkor, med enbart en sorteringsnyckel,
där sorteringsordningen bestämts med en if-sats av typen:
if a[i].key > a[j].key then <byt>
I det verkliga livet kan man råka ut för sorteringsvillkor som är betydligt mer komplicerade. Nycklarna kan omfatta flera fält, innehållande olika datatyper. Villkoren kan vara av de mest skiftande slag. Redan en sådan enkel sak som att i svensk bokstavsordning (vilket ej är detsamma som ASCII-ordning) sortera en namnlista efter efternamn (i första hand) och förnamn (i andra hand) krånglar till det hela betydligt.
Det finns massor med "tricks" för att hantera sådana problem: poster med variantdel, uppbygge av speciella sorteringsnycklar m m. Många av dessa är speciellt avpassade till speciella typer av poster osv. Att ge en någorlunda fullständig täckning av denna rika flora skulle kräva en hel bok och något sådant ska vi inte ge oss in på. Några synpunkter och exempel borde dock inte skada.
Låt oss titta på ett ganska enkelt problem: Sortering
efter efternamn och förnamn i ASCII-ordning (komplikationen med bokstavsordning
tas upp senare). KeyType blir då en postvariabel, t ex:
type
KeyType = record
enamn: string[20];
fnamn: string[15]
end;
Det första som man förmodligen kommer att tänka på
är att justera if-satsen inne i sorteringsrutinen:
if a[i].key.enamn > a[j].key.enamn then
<byt>
else if (a[i].key.enamn = a[j].key.enamn) and
(a[i].key.fnamn > a[j].key.fnamn) then
<byt>
Detta är betydligt komplexare än den enkla sats vi hade
att göra med tidigare. Vid ännu fler sorteringsfält och
krångligare villkor kan det hela bli ganska så invecklat. Det
värsta är dock att man genom att införa villkoren direkt
i sorteringsrutinen tvingas skriva om denna för varje speciellt sorteringsproblem.
Mycket skulle vara vunnet om detta kunde undvikas, dvs om jämförelserna
kunde göras skild från sorteringsrutinen. Detta kan avklaras
med en boolsk funktion. Om vi kallar den för GreaterThan kan vi i
sorteringsrutinen skriva
if GreaterThan(a[i], a[j]) then <byt>
Det enda som då behöver ändras mellan olika sorteringsproblem
är funktionen GreaterThan, som i vårt exempel kan formuleras
så här:
function GreaterThan(var a, b: ElementType): Boolean;
begin
if a.key.enamn > b.key.enamn then
GreaterThan:= true
else if (a.key.enamn = b.key.enamn) and
(a.key.fnamn > b.key.fnamn) then
GreaterThan:= true
else
GreaterThan:= false
end (* GreaterThan *);
eller, något effektivare:
function GreaterThan(var a, b: ElementType): Boolean;
begin
if a.key.enamn > b.key.enamn then
GreaterThan:= true
else if a.key.enamn < b.key.enamn then
GreaterThan:= false
else
GreaterThan:= a.key.fnamn > b.key.fnamn
end (* GreaterThan *);
Med införandet av en boolsk funktion har vi tagit ett stort steg mot att göra sorteringsrutinerna generella, dvs så att de (utan ändringar) fungerar för godtyckliga datatyper. Det återstår dock en del innan vi kan påstå att vi har skapat "en generisk sorteringsrutin". Fortfarande erfordras en upplaga av sorteringsrutinen för varje slag av sortering, även om det bara är samma array som ska sorteras på olika sätt. Däremot slipper vi göra ändringar i själva sorteringsrutinen (om de olika upplagorna innesluts i olika "skal", dvs läggs inne i omslutande procedurer, så att "namnkollisioner" undviks). Men, som vi ska se senare, sorteringsrutinerna kan göras betydligt generellare.
Anmmärkning Villkoren kan sammanföras till ett enda:
function GreaterThan(var a, b: ElementType): Boolean;
begin
GreaterThan:= (a.key.enamn + #0 + a.key.fnamn) >
(b.key.enamn + #0 + b.key.fnamn)
end (* GreaterThan *);
Denna variant är tyvärr ineffektivare än de tidigare, men knepet att bygga upp en ny sträng är användbart i vissa sammanhang.
Med de nya "verktygen" kan vi faktiskt ganska enkelt lösa en del kluriga sorteringsproblem. Antag t ex att en svensk-tysk ordlista ska sorteras efter de tyska orden och i tysk bokstavsordning.
För enkelhets skull förutsätter vi att alla bokstäver är stora och att effektiviteten är av underordnad betydelse: Det viktigaste är att "få jobbet gjort".
Vad utmärker då det tyska alfabetet? Jo, där likställs bokstäverna Ü, Ä och Ö med respektive U, A och O. Vid sorteringen måste alltså Ü behandlas som ett U osv. Detta kan göras genom att vid jämförelserna byta ut Ü mot U osv. Utbytet kan utföras med en funktion:
function German(s: Strng): Strng;
var
i: Integer;
begin
for i:= 1 to Length(s) do begin
case s[i] of
'Ü': s[i]:= 'U';
'Ä': s[i]:= 'A';
'Ö': s[i]:= 'O';
end (* case *);
end (* for *);
German:= s;
end (* German *);
Anmärkning: I ovanstående och följande exempel är Strng
en strängtyp som ska defineras tidigare i programmet, eller så kan det (med
nyare versioner av Turbo Pascal) sättas till string,
vilket är samma som string[255] |
Men, sakta i backarna nu, vi får ju inte ändra orden som
sådana. Inget problem! Vi skriver funktionen GreaterThan på
följande sätt:
function GreaterThan(var a,b: Strng): Boolean;
begin
GreaterThan:= German(a) > German(b)
end (* GreaterThan *);
Här jämförs funktionsresultaten, inte de verkliga
orden. Olägenheten är att en hel del extratid går åt
för anrop till funktionen German (det kan mycket väl hända
att samma ord behöver "översättas" ett stort antal gånger
innan sorteringen är färdig). Men det fungerar.
Tekniken i föregående exempel fungerar lika bra för
sortering i svensk bokstavsordning. Om man dessutom låter funktionen
(säg: Swedish) omvandla alla små bokstäver till stora,
erhålls korrekt alfabetisk ordning oberoende av om orden är
skrivna med små eller stora bokstäver. I många sammanhang
skulle dock denna metod bli alltför "trög".
Om det inte är nödvändigt att likställa gemener (små bokstäver) med versaler (stora bokstäver) kan sorteringsproblemet hanteras med ett lite annorlunda, effektivare tillvägagångssätt:
Chr(91), Chr(92) och Chr(93),
samt motsvarande för å, ä och ö):
procedure ShiftSwedChar(var s: Strng);
var
i:Integer;
begin
for i:= 1 to Length(s) do begin
case s[i] of
'å': s[i]:= #123;
'ä': s[i]:= #124;
'ö': s[i]:= #125;
'Å': s[i]:= #91;
'Ä': s[i]:= #92;
'Ö': s[i]:= #93;
end;(* case *)
end; (* for *)
end (* ShiftSwedChar *);
procedure RestoreSwedChar(var s: Strng);
var
i:Integer;
begin
for i:= 1 to Length(s) do begin
case s[i] of
#123: s[i]:= 'å';
#124: s[i]:= 'ä';
#125: s[i]:= 'ö';
#91 : s[i]:= 'Å';
#92 : s[i]:= 'Ä';
#93 : s[i]:= 'Ö';
end;(* case *)
end; (* for *)
end (* RestoreSwedChar *);
Anm: Procedurerna fungerar med både vanlig ASCII och IBM-ASCII - i det senare fallet dock med förbehållet att det inte ingår hak- eller krullparenteser samt tecknen \ och | i de strängar som ska sorteras.
Om ordlistan finns på en fil kan man göra så här:
Orden inläses ett och ett, konverteras (med en funktion eller procedur) på önskat sätt och placeras i en array. Sedan utförs sorteringen med utnyttjande av indexarray. Efter sorteringen inläses orden från filen på nytt, nu utan att konverteras. Eftersom de då läses in i samma ordning som förra gången, kan indexarrayen användas för att skriva ut den korrekt sorterade ordlistan på en ny fil.
Med denna metod kan vilka förändringar som helst av de
först inlästa orden göras, ty de konverterade orden utnyttjas
enbart för sortering av indexarrayen. För svensk bokstavsordning
kan ordkonverteringen göras med proceduren Swedish:
procedure Swedish(var s: Strng);
var
i: Integer;
begin
for i:= 1 to Length(s) do begin
case s[i] of
'a'..'z': s[i]:= UpCase(s[i]);
'Å', 'å': s[i]:= #91;
'Ä', 'ä': s[i]:= #92;
'Ö', 'ö': s[i]:= #93;
end; (* case *)
end; (* for *)
end (* Swedish *);
Även problemet i exempel 2 (tysksorteringen) kan lösas enligt denna modell. Glosorna inläses och sorteringsnycklar bildas med ÜÄÖ ersatta av UAO, varefter sorteringen görs enligt ovan.
Med en generisk sorteringsrutin menas här en rutin som förmår sortera många olika datatyper. Man kan skilja på 2 slag av sådana rutiner: De som är "kompileringsgeneriska", dvs binds till en bestämd datatyp vid kompileringen, och de som även efter kompileringen klarar av olika datatyper. Ett exempel på den första kategorin är den Quicksorteringsrutin som följer med den svenska Turbo-disketten. Här ska vi gå ett steg längre och skapa sorteringsrutiner av den andra typen. För att klara av detta tvingas vi tillgripa en del "lågnivåprogrammering". Vi ska också utnyttja några andra finesser som ökar flexibiliteten, bl a dynamiska variabler.
Betrakta den tidigare redovisade varianten av Shellsortering med
indexarray. Vid lite närmare eftertanke inses, att om jämförelserna
görs med en funktion, till vilken elementens index skickas i stället
för elementen, då kan datatypen ElementArray strykas från
sorteringsrutinens parameterlista. Därmed kan rutinen sortera vilken
array som helst: Vi har fått en "kompileringsgenerisk" sorteringsrutin.
Nackdelen är att jämförelsefunktionen måste utnyttja
den globala arrayen för att komma åt de element som ska jämföras.
Men hur komma härifrån till en rutin som (i samma program) kan sortera olika arrayer efter olika sorteringsnycklar?
Om jämförelsefunktionerna kunde överföras som parametrar till sorteringsrutinen, då skulle saken vara biff. Är detta möjligt? Ja, i Standardpascal kan underprogram anges som parametrar till andra procedurer/funktioner. För en generisk sorteringsprocedur skulle procedurhuvudet kunna skrivas så här:
procedure GenericShellIxSort(var ix: IndexArray; n: Integer); function ToSwap(i,j: Integer): Boolean;
I parameterlistan specificerar function ToSwap(i,j: Integer): Boolean
att ToSwap är en boolsk funktion, vars formella parametrar är
av datatypen Integer (index i vårt fall). För att sortera en
array med en jämförelsefunktion som heter NameGreaterThan, anropas
sorteringsrutinen med
GenericShellIxSort(ix, n, NameGreaterThan);
Tyvärr tillåter inte Turbo-Pascal underprogram som parametrar - en av de få punkter på vilka Turbo på ett icke fördelaktigt sätt avviker från Standardpascal. Lyckligtvis finns ett sätt att klara av biffen ändå:
procedure GenericShellIxSort(var ix: IndexArray;
n: Integer; ofsToSwap: Integer);
Parametern ofsToSwap motsvarar function ToSwap ... i "standardhuvudet"
och utgörs av offset för den aktuella jämförelsefunktionen.
| Anmärkning: Efter detta skrevs införde Borland s k procedurtyper, som kan betraktas som en variant av Standardpascalens "procedurparametrar". Detta kommer dock inte att tas upp i fortsättningenx - se manualer eller någon Pascal-lärobok för mer information. |
Sorteringsrutinen skulle nu kunna skrivas direkt, men låt oss
införa en finess till: I parameterlistan utelämnar vi datatypen
för indexarrayen (och döper om den till ixArr), och inne i sorteringsproceduren
inför vi en absolutdeklarerad Integer-array, kallad ix. Vitsen med
detta är att rutinen då i oförändrat skick klarar
av såväl en statisk (dvs "vanlig") indexarray som en dynamisk
dito. I det senare fallet skickar vi bara "den indexarray som pekaren pekar
på" som parameter. Sorteringsrutinen ser ut så här:
procedure GenericShellIxSort(var ixArr; (* Obs typlös *)
n: Integer; ofsToSwap: Integer);
var
i, j, k, step, temp: Integer;
ix: array [1..1] of Integer absolute ixArr;
(* OBS att fältindexkontrollen måste vara passiv, dvs
kompileringsdirektivet R+ får ej användas *)
function ToSwap(index1, index2: Index): Boolean;
begin Sub end;
begin
AssignSub(Ofs(ToSwap), ofsToSwap); (* Se kommentarer nedan *)
if n > maxInt div 2 then (* Bestäm lämpligt stegvärde *)
step:= maxInt div 2
else begin
step:= 1;
while step < n do step:= step+step;
step:= step div 2;
end (* if *);
if step > 1 then Dec(step);
while step > 0 do begin (* Här börjar själva sorteringen *)
for j:= 1 to n-step do begin
i:= j;
repeat
k:= i+step;
if ToSwap(ix[i], ix[k]) then begin
temp:= ix[i];
ix[i]:= ix[k];
ix[k]:= temp;
i:= i-step;
end
else
i:= 0
until (i < 1)
end (* for *);
step:= step div 2;
end (* while *);
end (* GenericShellIxSort *);
Sorteringsordningen bestäms med en boolsk funktion som anger
när två element ska byta plats. För att t ex sortera (den
statiska) arrayen eArr i stigande (vanlig) ordning kan funktionen skrivas:
function GreaterThan(var index1, index2:Integer): Boolean;
begin
GreaterThan:= eArr[index1] > eArr[index2]
end (* GreaterThan *);
Om vi i stället ska sortera en dynamiskt allokerad array, skriver
vi eArr^[index1] ...
Jämförelsefunktionens offset/adress skickas som parameter
till sorteringsrutinen. Satsen AssignSub(Ofs(ToSwap), ofsToSwap) sköter
om sammankopplingen mellan den formella funktionen ToSwap och den aktuella.
Exempel på anrop (vi arbetar med en statisk indexarray):
GenericShellIxSort(ix, n, Ofs(GreaterThan));
ProgramdiskettenDemo-programmet GSHELLIX.PAS sorterar 3 olika datatyper (reella tal, strängar och poster). Både indexarrayen och elementarrayerna är dynamiskt allokerade. Detta är en stor fördel i sådana här sammanhang, eftersom minnet då kan återvinnas när det inte längre behövs. För MS/PC-DOS-datorer innebär det också att arrayer upp till 64K kan sorteras, ty dynamiska variabler läggs på "högen", dvs behöver inte knapra på datasegmentet för statiska variabler (som är begränsat till totalt 64K). Med dynamiska variabler kan flera stora arrayer hållas i minnet samtidigt (försök dock inte att utnyttja hela det fria minnet - systemet behöver också svängrum). |
Index-metoden har nackdelar:
Det skulle inte vara så dumt med en generisk metod som sorterar "på vanligt sätt", dvs som inte går "omvägen" via en indexarray, eller hur? Det är möjligt att åstadkomma, även om det är litet knivigare. Vi ska demonstrera detta med en generisk variant av (rekursiv) Quicksortering.
En förutsättning för att sortering överhuvudtaget ska vara möjlig är att sorteringsrutinen, direkt eller indirekt, kan komma åt och "förflytta sig" mellan olika element. I förra avsnittet avklarades denna viktiga detalj med indexarrayen. Nu måste problemet bemästras inne i sorteringsrutinen, trots att den verkliga datastrukturen måste förbli odefinierad, dvs okänd. Problemet kan avklaras med att ge sorteringsrutinen information om storleken (i bytes) av ett arrayelement och den minnesadress på vilken arrayen startar. Sedan kan förflyttning till ett godtyckligt element ske genom att antalet bytes som föregår det aktuella elementet beräknas och adderas till startadressen.
Elementstorleken kan bestämmas med standardfunktionen SizeOf
och skickas som parameter till sorteringsrutinen. Minnesadresseringen är
ett större krux. Det problemet löser vi med införandet av
en pekarvariabel, en "sorteringspekare", deklarerad som en variant posttyp
(utan märkelement):
SortPointer = record
case Integer of
0: (p: ^Byte);
1: (o, s: Integer); (* offset, segment *)
end;
Varför denna underliga konstruktion? Jo, även om en pekarvariabel
helt enkelt innehåller minnesadressen till det "den pekar på",
så behandlar pascalsystemet adresser och pekare som olika datatyper
och därför kan t ex inte en pekare direkt tilldelas en minnesadress
(i Turbo finns en speciell funktion - Ptr - för just denna konvertering).
Vitsen med "variantdeklarationen" är att vi därmed kan komma
åt "sorteringspekaren" på 2 olika sätt: Pekarvarianten
kan utnyttjas för att "peka ut" array-element och med adressvarianten
kan adressen, dvs pekarens innehåll, direktmanipuleras.
För att "ställa in" sorteringspekaren på arrayens 1:a element, dvs omvandla adressen till ett pekarvärde, skriver vi:
adr.p:= Ptr(Seg(sortArray), Ofs(sortArray))
Genom att addera lämpligt antal sizeOfItem till Ofs() resp Ord()
innan konverteringen med Ptr skulle vi faktiskt klara oss med enbart denna
variant. Problemet är att då måste tidsödande multiplikationer
utföras varje gång pekaren ska ändras (hur detta går
till se proceduren GetAddr i sorteringsrutinen nedan). Eftersom förflyttningen
för det mesta sker fram eller tillbaka ett element i taget (1 sizeOfItem)
är detta mycket ineffektivt. Det är här den andra varianten
kommer in. Med denna kan vi direkt lägga till eller dra bort just
1 sizeOfItem från offseten/adressen.
Därmed är det svåraste problemet löst: Vi har tillgång till en "sorteringspekare" med vilken de element som ska jämföras/bytas kan "utpekas".
En detalj återstår dock: Det behövs också
en temporär variabel (temp) vid byten av värden mellan 2 variabler.
Till detta utnyttjar vi en annan "lågnivå-finess": Variabeln
temp definieras som en pekare och sedan utnyttjas proceduren GetMem för
att reservera precis det antal bytes som behövs. Själva bytet
utförs med Move-proceduren.
Den färdiga rutinen redovisas nedan (jämför gärna
med "vanlig" Quicksortering). Lägg märke till att variabelparametern
sortArray är typlös:
procedure GenericQuickSort(var sortArray; (*Arr som ska sorteras*)
sizeOfItem, (*Storlek på 1 element*)
n, (*Antal element*)
ofsInOrder: Integer);
type
Index = 1..maxInt;
SortPointer = record
case Integer of
0: (p: ^Byte);
1: (o, s: Integer); (* offset, segment *)
end;
var
temp: ^Byte;
mAddr, iAddr, jAddr: SortPointer;
function InOrder(var item1, item2): Boolean;
begin Sub end;
procedure GetAddr( i: Integer;
var adr: SortPointer);
begin
adr.p:= Ptr(Seg(sortArray), Ofs(sortArray) + Pred(i)*sizeOfItem)
end (* GetAddr *);
procedure Sort(l, r: Index);
var
i, j, mid: Index;
begin
i:= l; j:= r;
mid:= (l+r) div 2;
GetAddr(mid, mAddr);
GetAddr(i, iAddr);
GetAddr(j, jAddr);
repeat
while InOrder(iAddr.p^, mAddr.p^) do begin
Inc(i);
iAddr.o:= iAddr.o + sizeOfItem
end (* while *);
while InOrder(mAddr.p^, jAddr.p^) do begin
Dec(j);
jAddr.o:= jAddr.o - sizeOfItem
end (* while *);
if i <= j then begin (* Byt *)
Move(iAddr.p^, temp^, sizeOfItem);
Move(jAddr.p^, iAddr.p^, sizeOfItem);
Move(temp^, jAddr.p^, sizeOfItem);
(* Om mid = i el j har vi flyttat på mid varför vi
måste korrigera för detta för att jämförelserna ska bli OK: *)
if mid = i then begin
mid:= j;
mAddr:= jAddr;
end
else if mid = j then begin
mid:= i;
mAddr:= iAddr;
end (* if *);
Inc(i); iAddr.o:= iAddr.o + sizeOfItem;
Dec(j); jAddr.o:= jAddr.o - sizeOfItem;
end (* if *);
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r)
end (* Sort *);
begin (* GenericQuickSort *)
AssignSub(Ofs(InOrder), ofsInOrder);
GetMem(temp, sizeOfItem); (* Reservera minne för item vid byte *)
Sort(1, n); (* Sortera *)
FreeMem(temp, sizeOfItem); (* Frigör minne *)
end (* GenericQuickSort *);
Kommentarer: Sorteringsordningen bestäms (som vanligt) med en boolsk funktion. För att sortera i stigande ordning ska funktionen definiera "mindre än", t ex:
function LesserThan(var a1, a2: Real): Boolean;
begin
LesserThan:= a1 < a2
end (* LesserThan *);
En array innehållande 1000 reella tal (realArr) kan sorteras med
GenericQuickSort(realArr, SizeOf(Real), 1000, Ofs(LesserThan));
Om arrayen är dynamiskt allokerad (med pekarvariabeln realArr)
är det bara att skicka "den utpekade arrayen", dvs i proceduranropet
skriva realArr^ i stället för realArr.
ProgramdiskettenGENQDEMO.PAS sorterar reella tal, strängar och poster. Arrayerna är dynamiskt allokerade. Läs programkommentarerna innan du kör igång. |
Vi har nu redovisat 2 "generiska rutiner" för minnessortering. Fördelarna med sådana torde vara uppenbara, men det finns också olägenheter:
I det verkliga livet har man ofta att göra med så stora datamängder att rena minnessorteringsmetoder inte räcker till.
Som påpekades i början av kapitlet, blir s k virtuell minneshantering allt vanligare i sådana sammanhang. Större fleranvändarsystem (tidsdelarsystem) har ofta operativsystem som automatiskt sköter om den detaljen, men tekniken kan också användas på persondatorer, varvid det aktuella programmet får sköta om det hela. Det sorteringsprogram som ingår i Turbo Database Toolbox är ett exempel på detta. Den intresserade kan där studera hur man kan gå till väga.
Här ska inte ordas mer om "virtuellt minne", hur lockande ämnet än må vara. Däremot ska vi ta upp ett par varianter av samsortering, som ofta utnyttjas vid filsortering. Vi ska också visa ett sätt att med Turbo Pascal utföra Quicksortering helt på diskett. Men allra först ska vi titta på en lite mer udda metod, som utgör ett slags mellanting mellan fil- och minnessortering. Även om den inte tillhör de mer "grundläggande", är den intressant ur flera aspekter.
Antag att vi har lagt upp ett personregister. Det kan röra sig om ett medlemsregister för en idrottsklubb eller något dylikt. Registerposterna innehåller så mycket information att hela registret inte ryms i primärminnet.
Följande typdeklarationer gäller för filposterna:
type
Str15 = string[15];
NameType = record
lastName,
firstName: Str15;
end;
InfoType = record
<användardefinierat>
<t ex adress, telefon m m>
end;
RecType = record
name: NameType;
info: InfoType;
end;
Filen ska sorteras i namnordning (efternamn + förnamn). Vi förutsätter att medlemsantalet är så litet att alla sorteringsnycklarna gott och väl ryms i primärminnet (vi behöver extra svängrum). Då kan sorteringen hanteras i primärminnet med uppbygget av en speciell sorteringsarray, innehållande sorteringsnycklarna (efter- och förnamn), samt ett tal som entydigt bestämmer postens nummer på filen. Sedan arrayen sorterats uppsöks filposterna i tur och ordning, inläses och skrivs ut i sorterad ordning på en ny fil.
För att utföra denna operation behövs några extra deklarationer:
const
maxNum = <maximala antalet poster>
type
Index = 1..maxNum;
Str31 = string[31];
KeyType = Str31;
DataType = Integer;
ElementType = record (* Sorteringspost *)
key : KeyType; (* Sorteringsnyckeln *)
data: DataType; (* Nummer för identifiera filpost *)
end;
ElementArray = array [Index] of ElementType;
var
n: Integer;
recFile: file of RecType;
sortList: ElementArray; (* sorteringsarrayen *)
Vid uppbygget av sorteringsposterna sammanför vi sorteringsfälten (efternamn och förnamn) till ett enda, vilket förenklar sorteringsvillkoret:
sortRec:= sortRec + #0 + firstName;
ASCII-tecknet null (#0) har till uppgift att åtskilja efter- och förnamn.
Uppbygget av sorteringsarrayen överlåts åt en procedur:
procedure MakeSortArray(var sortList: ElementArray; var n: Integer);
var
rec: RecType;
sortRec: KeyType;
begin
Assign(recFile, <filnamn>);
Reset(recFile);
n:= 0;
while not EoF(recFile) do begin
Read(recFile, rec);
Inc(n);
with rec, name do begin
sortRec:= lastName + #0 + firstName;
sortList[n].key:= sortRec;
sortList[n].data:= n;
end (* with *);
end (* while *);
Close(recFile);
end (* MakeSortArray *);
Varje post erhåller ett nummer (sortList[n].data:= n) som identifierar
filposten. Detta nummer spelar en central roll för metoden (jfr index
i en indexarray).
Den färdiga sorteringsarrayen kan sorteras med valfri metod
(t ex QuickSort). Numret i sorteringspostens datafält kan sedan utnyttjas
för att söka upp filposterna i sorteringsordning och skriva ut
dem på den nya filen:
procedure WriteSortedFile(var sortList: ElementArray; n: Integer);
var
i: Integer;
rec: RecType;
outFile: file of RecType;
begin
Assign(outFile, <nytt filnamn>);
Rewrite(outFile);
Assign(recFile, <gamla filnamnet>);
Reset(recFile);
for i:= 1 to n do begin
Seek(recFile, sortList[i].data-1);
Read(recFile, rec);
Write(outFile, rec)
end (* for *);
Close(outFile); Close(recFile);
end (* WriteSortedFile *);
Binära datafiler (ej textfiler) kan hanteras både sekventiellt
och som direktfiler. Vid direktfilsbearbetning kan postnumren utnyttjas
för att komma åt enskilda filposter på ett sätt som
liknar användning av index i arrayer. För att sortera en binärfil
i stället för en array behövs bara smärre ändringar
i sorteringsalgoritmen (vi anlitar en funktion, InOrder, för att bestämma
sorteringsordningen):
procedure FileQuickSort(var sortFile: ElementFile);
var
numRecs: Integer;
procedure GetItem (var a: ElementType; i: Integer);
begin
Seek(sortFile, i); Read(sortFile, a);
end (* GetItem *);
procedure QuickSort(low, high: Integer);
var
j, k, mid: Integer;
a, b, c: ElementType;
begin (* QuickSort *)
j:= low; k:= high;
mid:= (j+k) div 2;
GetItem(a, mid);
repeat
GetItem(b, j);
while InOrder(b, a) do begin
Inc(j);
GetItem(b, j)
end (* while *);
GetItem(b, k);
while InOrder(a, b) do begin
Dec(k);
GetItem(b, k);
end (* while *);
if j <= k then begin (* byt *)
GetItem(b, j);
GetItem(c, k);
Seek(sortFile, k); Write(sortFile, b);
Seek(sortFile, j); Write(sortFile, c);
Inc(j); Dec(k);
end (* if *)
until j > k;
if low < k then
QuickSort(low, k); (* Sortera vänster dellista *)
if j < high then
QuickSort(j, high); (* Sortera höger dellista *)
end (* QuickSort *);
begin (* FileQuickSort *)
numRecs:= FileSize(sortFile); (* Får vara högst maxInt *)
QuickSort(0, numRecs-1); (* Filposter numreras från 0 *)
Close(sortFile);
end (* FileQuickSort *);
En fördel med denna metod, jämfört med andra filsorteringsmetoder,
är att den inte kräver extra diskutrymme för tillfälliga
hjälpfiler. Den bör dock inte användas för sortering
på diskett - för detta finns effektivare metoder. På RAM-disk
kan den däremot vara ett bra alternativ, just därför att
den inte utnyttjar hjälpfiler. Det som då sätter gränsen
för hur stora filer som kan sorteras är bara postantalet (får
vara högst maxInt) och RAM-diskens kapacitet.
Samsortering av 2 sorterade filer är en enkel operation. De två ursprungsfilerna öppnas för läsning och resultatfilen för skrivning, varefter samsorteringen sker i princip på samma sätt som vid samsortering av arrayer (en algoritm för detta redovisades i avsnittet om Mergesortering ovan).
Med samsorteringsalgoritmen som utgångspunkt kan även generella filsorteringsmetoder skapas. En sådan metod är den s k naturliga Mergesorteringen. För att förstå hur den fungerar tittar vi på ett exempel. Vi utgår från filen F1, som har följande innehåll (heltal):
F1 : 73 55 80 10 40 70 14 31 22
Vi observerar att flera delar av filen innehåller element som redan är i rätt ordning:
F1 : | 73 | 55 80 | 10 40 70 | 14 31 | 22
I engelsk litteratur brukar delarna, som åtskilts med |, kallas för subfiles eller runs. Här kommer benämningen delfiler att användas. Delfilerna utgör en "naturlig" uppdelning av filen F1.
Sorteringen inleds med att delfilerna läses och växelvis skrivs ut på 2 andra filer, F2 och F3:
F2 : | 73 | 10 40 70 | 22 |
F3 : | 55 80 | 14 31 |
Sedan samsorteras delfilerna i F2 och F3 och placeras i F1. Detta fortgår tills dess slutet på en av filerna F2 och F3 nåtts, varvid eventuellt återstående element kopieras över till F1. Vi erhåller:
F1 : | 55 73 80 | 10 14 31 40 70 | 22 |
Delningen och samsorteringen upprepas tills filen är sorterad.
Delning:
F2 : | 55 73 80 | 22 |
F3 : | 10 14 31 40 70 |
Samsortering:
F1 : | 10 14 31 40 55 70 73 80 | 22
Delning:
F2 : | 10 14 31 40 55 70 73 80 |
F3 : | 22 |
Samsortering:
F1 : | 10 14 22 31 40 55 70 73 80 |
Sorteringen sker alltså i 2 faser:
Det hela upprepas tills dess båda filerna består av en enda sorterad "delfil". När dessa samsorterats är sorteringen klar.
Denna "naturliga" samsorteringsmetod kan förbättras på några punkter. Men allra störst effekt erhålls om sorteringen inleds med att filen inläses i delar som sorteras i primärminnet. Därmed ökas längden på de sorterade delfilerna, samtidigt som deras antal sänks.
Proceduren SortFile nedan är en implementering av metoden. Eftersom
rutinen är ganska lång är nog en översiktlig beskrivning
på sin plats.
SortFile är indelat i två större "block": Det första
(PreSort) utför försorteringen i minnet, det andra
(MergeSort)
själva disksorteringen.
Minnessorteringen sker med maxIndex element i taget. I den nedan
redovisade versionen förutsätts att maxIndex är en global
konstant, men maxIndex kan även bestämmas under programkörningen
med utgångspunkt från ledigt minne och posternas storlek (mer
om detta nedan).
För minnessorteringen används Shellsortering och indexarray.
Elementarrayen (elementBuf) allokeras dynamiskt. Detta betyder att det
reserverade minnet återfås efter avslutad minnessortering,
men också att upp till 64K kan sorteras åt gången (om
datorn har tillräckligt stort primärminne).
Filen ska vara av typen ElementFile, posterna av typen ElementType.
Denna är godtycklig, men måste fastställas före kompileringen
(rutinen är "kompileringsgenerisk"). Sorteringsordningen bestäms
med en boolesk funktion (kallad InOrder), som placeras före sorteringsrutinen.
Normalordningen (växande ordning) formuleras med "mindre än".
De sorterade delfilerna skrivs tillbaka på utgångsfilen
(med utnyttjande av Seek-proceduren).
När försorteringen är klar överlåts jobbet
åt proceduren MergeSort (om inte hela filen redan är färdigsorterad).
Procedurerna SplitFile och Merge anropas omväxlande tills hela filen
sorterats.
SplitFile har till uppgift att jämnt fördela delfilerna
från f1 till f2 och f3. Till sin hjälp har SplitFile proceduren
CopySubFile som administrerar kopieringen av en delfil. Kopieringen av
ett element från en fil till en annan handhas av CopyOneItem.
Merge tar vid när en delning är slutförd. MergeSubfile
genomför samsortering tills en av filerna är slut. Eventuella
återstående delfiler kopieras då över till f1. Sorteringen
är fullbordad då antalet delfiler (numSubFiles) är 1, varvid
hjälpfilerna (f2 och f3) raderas.
procedure SortFile(var f1: ElementFile);
var
f2, f3: ElementFile;
done: Boolean;
procedure PreSort(var done: Boolean);
type
Buffer = array [1..maxIndex] of ElementType;
BufPointer = ^Buffer;
IndexArray = array [1..maxIndex] of Integer;
var
elementBuf: BufPointer;
index1,
index2,
len, i: Integer;
indx: IndexArray;
procedure ReadFile(var lower, upper: Integer);
var
i: Integer;
begin
i:= 0;
while (i < maxIndex) and not EoF(f1) do begin
Inc(i);
Read(f1, elementBuf^[i]);
end (* while *);
upper:= lower+i;
end (* ReadFile *);
procedure ShellSort(var a: BufPointer; var indx: IndexArray; n: Integer);
var
i, j,
k, step,
temp: Integer;
begin (* ShellSort *)
if n > maxInt div 2 then (*fixa bra start-step = 2p - 1, där*)
step:= maxInt div 2 (*2p är den största 2-potensen < n*)
else begin
step:= 1;
while step < n do step:= step+step;
step:= step div 2;
end (* if *);
if step > 1 then Dec(step);
while step > 0 do begin
for j:= 1 to n-step do begin
i:= j;
repeat
k:= i+step;
if InOrder(a^[indx[k]], a^[indx[i]]) then begin
temp:= indx[i];
indx[i]:= indx[k];
indx[k]:= temp;
i:= i-step;
end
else i:= 0
until i < 1;
end (* for *);
step:= step div 2;
end (* while *);
end (* ShellSort *);
procedure WriteFile(lower, upper: Integer);
var
i, n: Integer;
begin
n:= upper-lower;
Seek(f1, lower-1);
for i:= 1 to n do Write(f1, elementBuf^[indx[i]]);
end (* WriteFile *);
begin (* --- PreSort --- *)
Reset(f1);
index1:= 1; index2:= 1;
New(elementBuf);
repeat
ReadFile(index1, index2);
len:= index2-index1;
for i:= 1 to len do indx[i]:= i;
ShellSort(elementBuf, indx, len);
WriteFile(index1, index2);
index1:= index2;
until EoF(f1);
Dispose(elementBuf);
done:= FileSize(f1) <= maxIndex;
Close(f1);
end (* PreSort *);
(* --------------------- Försortering klar --------------------------*)
procedure MergeSort;
var
subFile: Boolean;
numSubFiles,
index1,
index2: Integer;
procedure CopyOneItem(var x, y: ElementFile;
var index: Integer;
var subFile: Boolean);
var
temp1, temp2: ElementType;
begin
Read(x, temp1);
Inc(index);
Write(y, temp1);
if EoF(x) then
subFile:= false
else begin
Read(x, temp2);
Seek(x, index);
if InOrder(temp2, temp1) then
subFile:= false
end (* if *);
end (* CopyOneItem *);
procedure CopySubFile(var f1, f2: ElementFile;
var index: Integer;
var subFile: Boolean);
begin
subFile:= true;
while subFile do
CopyOneItem(f1, f2, index, subFile);
end (* CopySubFile *);
procedure SplitFile;
begin
index1:= 0; index2:= 0;
repeat
CopySubFile(f1, f2, index1, subFile);
if not EoF(f1) then
CopySubFile(f1, f3, index1, subFile);
until EoF(f1);
end (* SplitFile *);
procedure MergeSubFile;
var
temp3, temp4: ElementType;
begin
subFile:= true;
repeat
Read(f2, temp3);
Seek(f2, index1);
Read(f3, temp4);
Seek(f3, index2);
if InOrder(temp3, temp4) then begin
CopyOneItem(f2, f1, index1, subFile);
if not subFile then
CopySubFile(f3, f1, index2, subFile)
end
else begin
CopyOneItem(f3, f1, index2, subFile);
if not subFile then
CopySubFile(f2, f1, index1, subFile);
end (* if *);
until not subFile
end (* MergeSubFile *);
procedure Merge(var numSubFiles: Integer);
begin
index1:= 0; index2:= 0;
numSubFiles:= 0;
repeat
MergeSubFile;
Inc(numSubFiles);
until EoF(f2) or EoF(f3);
while not EoF(f2) do begin
CopySubFile(f2, f1, index1, subFile);
Inc(numSubFiles);
end (* while *);
while not EoF(f3) do begin
CopySubFile(f3, f1, index2, subFile);
Inc(numSubFiles);
end (* while *);
end (* Merge *);
begin (* MergeSort *)
repeat
Rewrite(f2); Rewrite(f3); Reset(f1);
SplitFile;
Close(f1); Close(f2); Close(f3);
Reset(f2); Reset(f3); Rewrite(f1);
Merge(numSubFiles);
until numSubFiles = 1;
Close(f1); Close(f2); Close(f3);
Erase(f2); Erase(f3);
end (* MergeSort *);
begin (* SortFile *)
Assign(f2, 'F2.TMP'); Assign(f3, 'F3.TMP');
PreSort(done);
if not done then MergeSort;
end (* SortFile *);
Eftersom det är önskvärt att minnessortera så
stora block som möjligt är det en nackdel att antalet element
som inläses under försorteringsfasen bestäms av en konstant
(maxIndex). Detta spelar ingen roll om rutinen ska användas för
bara en datatyp åt gången och på en enda dator med känt
minne. Då kan man från fall till fall välja ett lämpligt
värde. Men bättre vore givetvis om programmet självt under
programkörningen ombesörjde framräkningen av ett "optimalt" maxIndex.
För att åstadkomma detta gör vi om maxIndex till
en lokal variabel. Dessutom måste typerna för elementbufferten
och indexarrayen ändras.
Värdet på variabeln maxIndex kan beräknas utifrån
kännedom om tillgängligt minne och elementtypens storlek (i bytes).
Även indexarrayen måste tas med i denna kalkyl (dess element
är heltal, dvs 2 bytes). Om tillräckligt minne finns tilldelas
elementbufferten 64K, i annat fall får elementbufferten och indexarrayen
dela på det som kan avvaras. Minne allokeras dynamiskt till både
elementbufferten och indexarrayen (med GetMem). Därefter kan minnessorteringen
börja. När den är klar frigörs det reserverade minnet
(med FreeMem). På demo-disketten är denna variant implementerad.
Antag att 6 sorterade filer ska samsorteras till en enda. Ett sätt att göra detta är att först samsortera filerna parvis till 3 hjälpfiler. Därpå ihopsorteras 2 av dessa och det hela fullbordas med samsortering av de 2 återstående filerna.
Samsorteringsalgoritmen kan skrivas:
Med enbart 2 ursprungsfiler fungerar metoden utmärkt, men det blir betydligt besvärligare om de är fler, eftersom ett flertal hjälpfiler då måste öppnas, stängas och raderas innan det hela är klart.
Om allihop kunde samsorteras på en gång borde det bli betydligt lättare att hantera och dessutom effektivare, ty då behövs inga hjälpfiler alls. Detta går att ordna om bara antalet filer inte är alltför stort (det exakta antalet är beroende av tillgängligt primärminne och operativsystemet).
Samsorteringen kan göras på följande sätt:
Algoritmen är i princip enkel, men det krävs en del tankemöda
för att omvandla den till en fungerande Pascal-rutin. För att
administrera det hela inför vi en array av filer (ja just det!), samt
en motsvarande array av poster, där vi dels registrerar om motsvarande
fil är slut eller inte och dels lagrar den sist inlästa filposten.
Med denna konstruktion erhåller vi följande pascalprocedur:
procedure MergeSort(var files; n: Integer; ofsInOrder: Integer);
function InOrder(var item1, item2): Boolean;
begin Sub end;
const
maxFiles = 15;
var
f: array [1..maxFiles] of file of ElementType absolute files;
type
FState = record
empty: Boolean;
lastItem: ElementType;
end;
var
fStatus: array [1..maxFiles] of FState;
i, minF: 1..maxFiles;
minKey : ElementType;
allFilesSorted: Boolean; (* false tills alla filer sorterats *)
procedure InitFStatus;
var
i: 1..maxFiles;
begin
for i:= 1 to n do begin
Reset(f[i]);
with fStatus[i] do begin
if EoF(f[i]) then begin
empty:= true;
Close(f[i])
end
else begin
empty:= false;
Read(f[i], lastItem)
end (* if *);
end (* with *);
end (* for *);
end (* InitFStatus *);
begin (* MergeSort *)
AssignSub(Ofs(InOrder), ofsInOrder);
allFilesSorted:= false;
InitFStatus; (* Läs första item från alla filer *)
while not allFilesSorted do begin
i:= 1;
while fStatus[i].empty and (i <= n) do Inc(i);
if i > n then
allFilesSorted:= true
else begin
minKey:= fStatus[i].lastItem;
minF:= i;
Inc(i);
while i <= n do begin (* Sök minsta nyckel av öppna filer *)
if not fStatus[i].empty and
InOrder(fStatus[i].lastItem, minKey) then begin
minKey:= fStatus[i].lastItem;
minF:= i
end (* if *);
Inc(i);
end (* while *);
(* Minsta nyckel funnen. Skriv till ny fil: *)
WriteOnMergedFile(fStatus[minF].lastItem);
if EoF(f[minF]) then begin
fStatus[minF].empty:= true;
Close(f[minF])
end
else
Read(f[minF], fStatus[minF].lastItem);
end (* if *);
end (* while *);
end (* MergeSort *);
Kommentarer:
file of ElementType, där ElementType är godtycklig, dvs rutinen är "kompileringsgenerisk".function InOrder(var a,b: ElementType): Boolean;vars adress skickas som parameter (
ofsInOrder) till MergeSort .
WriteOnMergedFile,
med parameter av typ ElementType. Resultatfilen behöver inte ha samma
typ som ursprungsfilerna - utskriften kan t ex ske till en textfil.Med denna nya samsorteringsmetod i bakfickan kan vi med nya friska tag angripa det allmänna filsorteringsproblemet:
Filsortering enligt denna modell står sig utmärkt i jämförelse med de metoder vi tittat på tidigare. Vad själva samsorteringsrutinen beträffar finns f ö utrymme för ytterligare effektiviseringsåtgärder. Man kan t ex i primärminnet bygga upp speciella input-buffertar för var och en av de filer som ska samsorteras, liksom en output-buffert och därmed reducera antalet diskaccesser. Med s k urvalsträd m m är det dessutom möjligt att reducera den tid som åtgår för att ta reda på vilken post som står i tur att överföras till resultatfilen (eller dess buffert). Vi ska här inte gå in närmare på dessa metoder (se speciallitteraturen).
ProgramdiskettenDe metoder som beskrivits i detta avsnitt finns samtliga på programdisketten (programmen FILESRT1.PAS-FILESRT4.PAS). Programmen byggs i stor utsträckning upp med hjälp av include-filer. De delar som är gemensamma för de olika programmen är samlade i include-filerna FILETYPE.DEF (typdeklarationer) och FILESORT.INC (gemensamma underprogram). Den grundläggande posttypen ser ut så här
PersRecType = record
key : PersIDType;
data: AddressType;
end;
där I FILESORT.INC ingår bl a rutiner som - för att göra det hela mer "realistiskt" - slumpmässigt genererar "riktiga" personposter. Till detta utnyttjas 7 textfiler med rådata som inläses i minnet och lagras i dynamiskt allokerade arrayer (dessa deallokeras när persondatafilen skapats). FILESRT1.PAS sorterar m a p efternamn/förnamn enligt den först behandlade metoden och med användning av en funktion, Swedish, för att ge korrekt svensk bokstavsordning. Minnessorteringen görs med rekursiv Quicksortering. FILESRT2.PAS utför Quicksortering direkt på disk. Sorteringen sker m a p efternamn/förnamn i ASCII-ordning. Sorteringsrutinen ligger i en särskild include-fil. Pröva gärna programmet med RAM-disk om så är möjligt. FILESRT3.PAS demonstrerar minnessortering kombinerad med "naturlig Mergesortering". För minnessorteringen utnyttjas den mer avancerade variant som beskrivs i texten (se include-filen FILMERG.SRT). FILESRT4.PAS demonstrerar den slagkraftiga kombinationen generisk
minnessortering (include-filen GENQUICK.SRT) + samsortering av flera filer
samtidigt på disk (include-filen FILNMERG.SRT). Programmet ger möjlighet
att välja mellan 3 olika sorteringsordningar (personnummer, namn resp
postnummer). Att lägga märke till är att proceduren OBS: Innan körning av programmen, se till att det finns gott om ledigt diskutrymme! |
Vi har nu tittat på såväl minnessortering som filsortering. Genomgången skulle emellertid förbli ofullständig om vi inte också sade några ord om det praktiska problemet att hantera stora datamängder, typ register, där det gäller att hålla data "sorterade" hela tiden, kanske efter flera sorteringsnycklar samtidigt.
Att ständigt sortera om en stor datafil eller ännu värre - om den måste hållas sorterad efter flera nycklar - göra det med flera upplagor av filen är i praktiken uteslutet.
Det finns två sätt att komma runt problemet.
En metod kallas "hashing" och går ut på att sorteringsnyckeln transformeras till ett tal (hashtalet) med en därför utformad funktion (hash-funktionen). Hashtalet får bestämma vart posten ska skrivas/sökas i filen (som måste ha bestämd längd). Hashing har dock vissa nackdelar:
En annan metod är att utnyttja s k indexfiler. Posterna i en indexfil innehåller 2 fält, det ena med den aktuella sorteringsnyckeln, det andra med adressen (postnumret) till motsvarande post i huvudfilen. För att komma åt en post i huvudfilen enligt en viss sorteringsordning räcker det med att ha en indexfil sorterad i denna ordning - huvudfilen behöver aldrig sorteras. Fördelarna med indexfiler är flera:
När indexfilen (-filerna) ryms helt i primärminnet fungerar metoden ypperligt. Enskilda poster hittas mycket snabbt - t ex med binärsökning (om indexfilens element ligger i en array), samt en enda diskaccess för att läsa in huvudfilsposten. Likaså kan index uppdateras mycket effektivt och när sessionen är avslutad skrivs indexfilen ut på sekundärminnet i ett enda svep.
Problem uppstår då indexfilen/filerna inte ryms i primärminnet. Man kan då stycka upp indexfilen och skapa en extra "indextabell" till indexfilens olika delar. Därmed erhålls index på olika nivåer. Självklart blir detta besvärligare att hantera. Sökningen måste, åtminstone delvis, ske på disk och det blir betydligt krångligare att uppdatera index när nya poster infogas, gamla poster raderas osv.
Med en smartare indexfilstruktur kan nackdelarna reduceras avsevärt. En effektiv sådan metod är ISAM (Index Sequential Access Method). I denna utnyttjas en speciell trädstruktur kallad B-träd (ej att förväxla med binära träd).
För lite större registersystem är ISAM nästan ett måste. Det fina i kråksången är att det inte är nödvändigt att gräva ner sig i alla detaljer om hur metoden fungerar och sätta sig ner och själv skriva ett sådant system: Turbo Database Toolbox innehåller alla rutiner som behövs för att skapa och upprätthålla indexfiler organiserade som B-träd. Eftersom hela systemet levereras i källkod kan den intresserade i lugn och ro studera hur systemet är uppbyggt.
I stället för att dyka ner i ISAM-problematiken ska vi här avrunda med ett betydligt mindre storslaget projekt, nämligen ett personregister, med enbart en sorteringsordning och med en indexfil som helt ryms i primärminnet. Som en första introduktion i ämnet "indexfiler" och registerprogram får det duga.
Det färdiga programmet, som finns på demodisketten (DATABAS.PAS), är över tusen rader långt och ska här inte behandlas i detalj. Vi inskränker oss till att diskutera några av de problem som rör indexhanteringen.
Posterna i personregistret har följande uppbyggnad:
PersRecType = record
lastName: string[25];
firstName: string[20];
street: string[25];
zipCode: string[6];
city: string[20];
phone: string[15];
end;
Indexfilen hålls sorterad i svensk bokstavsordning enligt efternamn
(lastName) i 1:a hand och förnamn (firstName) i 2:a hand. För
att göra det hela lite intressantare (och spara minne) används
bara delar av namnen för att bygga upp nyckelfältet i indexposterna:
de 10 första tecknen i efternamnet + de 3 första i förnamnet.
Detta ger givetvis fler "kollisioner" (dvs nycklar som blir identiska)
än om hela namnfälten användes (t ex kommer Gunnar Andersson
och Gun Andersson att ge samma nycklar). Om det är lätt att förflytta
sig fram och tillbaka i registret gör detta inte så mycket.
Indexposterna innehåller sorteringsnyckeln (string[13] enligt
ovan) och ett heltal som anger postens adress i huvudfilen. Detta heltal
utgörs av postnumret i huvudfilen (numrerade 1, 2, 3 osv):
IndexType = record
key = string[13];
data= Integer;
end;
Indexposter byggs upp med följande två underprogram (den första är till för att ge svensk bokstavsordning):
function Swedish(s: Str80): Str80;
var
i: Integer;
begin
for i:= 1 to Length(s) do begin
case s[i] of
'a'..'z': s[i]:= UpCase(s[i]);
'Å', 'å': s[i]:= #91;
'Ä', 'ä': s[i]:= #92;
'Ö', 'ö': s[i]:= #93;
end (* case *);
end (* for *);
Swedish:= s;
end (* Swedish *);
procedure MakeIndex(pers: PersRecType; num: Integer;
var index: IndexType);
const
blank = ' ';
begin
index.key:= Copy(Swedish(pers.lastName)+ blank , 1, 10)+
Copy(Swedish(pers.firstName)+blank, 1, 3);
index.data:= num
end (* MakeIndex *);
I primärminnet hanteras index med en sorterad lista. All sökning, insortering etc sköts via "vanliga" listoperationer. Fördelen med detta är att vi kan utnyttja färdiga biblioteksrutiner och slipper bekymra oss om hur listan är implementerad. I programmet används en array-implementering av listan, vilket medger mycket snabb sökning (hanteras med binärsökning i list-modulen), men inget hindrar att - om så skulle önskas - i stället t ex en cirkulär dubbellänkad lista utnyttjas. Under förutsättning att list-implementeringen innehåller "samma operationer" behöver bara list-include-filen bytas ut och det hela kommer att fungera.
Nackdelen med en "vanlig" sorterad lista är att vissa operationer blir något omständigare än om en specialimplementering för just registerprogrammet gjorts, men detta uppvägs av att det är enklare och säkrare att utnyttja en känd och beprövad datastruktur än att skapa en ny (dessutom får vi ett tillfälle att illustrera hur en färdig modul av denna typ kan utnyttjas).
Filhanteringen är enkel. Vid start av registerprogrammet inläses
indexfilen och antalet ingående poster i huvudfilen bestäms
med FileSize-funktionen. När nya poster skall tillföras huvudfilen
uppräknas först postantalet (och lagras i motsvarande indexpost).
Sedan skrivs posten sist i huvudfilen. Radering avklaras med att indexposten
avlägsnas ur listan (dvs inget görs åt huvudfilen).
I programmet uppdateras både index- och huvudfilen varje gång
som användaren lämnar registret, vilket förhindrar att huvudfilen
blir större än nödvändigt. Man kan tänka sig flera
andra sätt att sköta uppdateringen av huvudfilen. Exempelvis
skulle den kunna utföras enbart om antalet "raderade poster" överstiger
ett visst tal. Detta är lätt att åstadkomma, ty man bara
behöver jämföra antalet filposter med antalet listelement.
Det är i princip också möjligt att uppdatera huvudfilen
efter hand, t ex genom att vid radering av en post kopiera sista posten
i huvudfilen till den raderades plats. Då måste dock postnumret
för den flyttade posten ändras i listan (dvs ges den gamlas postnummer).
Dessutom bör huvudfilen då "trunkeras", dvs den sista filposten
avlägsnas. Under MS/PC-DOS är detta enkelt (görs med standardproceduren
Truncate).
Registerprogrammet (huvudfil: DATABAS.PAS) innehåller en hel del "finesser", bl a redigeringsmöjligheter a la WordStar. Vid redigering ser bildskärmen t ex ut så här (OBS att på IBM-PC och kompatibler fungerar även piltangenterna):
--------------------------------------------------------------------------------
PERSONREGISTER UPPDATERA/SÖKA
Post nummer: 1 Registret innehåller 239 poster
--------------------------------------------------------------------------------
<< EDITERINGSHJÄLP >>
Markörstyrning: | Radera: | Övrigt:
^S tkn vänster ^D tkn höger | ^G tkn under markör | ^V infoga av/på
^A radbörjan ^F radslut | DEL, BS tkn vänster | ESC avbryt
^E föreg fält ^X nästa fält | ^Y radera rad
------------------------------------------------------------------------------
Efternamn : Anka_____________________ Förnamn : Kalle_______________
Gatuadress: Näbbgatan 1______________
Postnummer: 124 45 Postadress: Ankeborg____________
Telefon : 02-47 11_______
------------------------------------------------------------------------------
S)ök, F)ram, T)illbaka, E)ditera, R)adera, H)uvudmenyn: E
Avbryt med tryck på ESC
|
De flesta kan förmodligen hitta användbart stoff i DATABAS.PAS och tillhörande filer. Det skulle dock vara förmätet att påstå att programmet håller "professionell standard" - det kan förbättras på många punkter. Och sist men inte minst: Den som vill skriva flexibla och effektiva registerprogram bör absolut införliva Turbo Database Toolbox i sitt programbibliotek.
Texten ovan skrevs mitten av 80-talet för Turbo Pascal version 2 och 3 och de exempel som använder mer lågnivåmässiga grepp (särskilt de "generiska" rutinerna) fungerar inte i befintligt skick med senare Turbo/Borland Pascal-versioner. Samtliga exempel i texten och diskettprogrammen (beskrivs i speciella rutor ovan) finns dock konverterade så att de fungerar med de nyare Pascal-versionerina.
Om tillräckligt stort intresse föreligger kan jag göra dessa filer tillgängliga. Skriv i så fall en rad ...
Copyright © 1999 Martin Fahlgren
martin@1-1-7-46a.ghn.gbg.bostream.se [Till början av dokumentet] [Till artikelförteckningen]