|
2. Teil
Bis auf eines wurden in Heft 1 alle wichtigen Sortieralgorithmen mit Programmierbeispielen vorgestellt.
Hier folgt nun noch Quicksort, was normalerweise das schnellste Sortierverfahren darstellt.
Dann wenden wir uns Suchverfahren zu, wofür zur Vereinheitlichung und zur besseren Vergleichsmöglichkeit einheitliche Abbruchbedingungen definiert werden.
|
Quicksort
Diese schnellste aller Sortiermethoden wurde von C. A. Hoare entwickelt.
Der Vorteil von Quicksort offenbart sich aber erst bei größeren Datenmengen.
Bei diesem Algorithmus wird der Austausch von falsch postierten Elementen über größere Distanzen durchgeführt.
Das Verfahren arbeitet folgendermaßen:
- Wähle ein beliebiges Element des Feldes, zum Beispiel das mittlere
(H := D [1+N DIV 2]).
- Durchsuche das Feld von links und rechts nach der Mitte zu, bis von links kommend ein Element D[I]>H und von rechts kommend ein Element D[J]<H gefunden ist.
Vertausche die Elemente und fahre fort, bis sich die Indizes I und J irgendwo treffen.
Jetzt besteht das Feld aus zwei Teilen, deren linker Teil Elemente kleiner als H und deren rechter Teil Elemente größer als H besitzt (es sind natürlich immer die Schlüssel gemeint).
- Sortiere den linken und den rechten Teil getrennt nach der oben angegebenen Vorgehensweise.
Fahre fort, bis die Teile nur noch aus einem Element bestehen.
Der Zerlegungsalgorithmus läßt sich am besten durch eine rekursive Prozedur darstellen (Tabelle 5).
| Tabelle 5: Rekursive Zerlegung bei Pascal-Quicksort |
|
PROCEDURE PARTITION (L,R : INTEGER);
(* L UND R SIND DIE UNTER- UND OBERGRENZE DES ZU ZERLEGENDEN TEILS DES
DATENFELDES *)
VAR I,J : INTEGER;
H : ITEM;
BEGIN
I := L; J := R; (* GRENZEN UEBERTRAGEN *)
H := D [(L+R) DIV 2]; (* MITTLERES ELEMENT *)
REPEAT
(* SCHLEIFE BIS SICH I UND J TREFFEN *)
WHILE (D[I].KEY<H.KEY) AND (I<R) DO
(* SUCHE VON LINKS *) I := I + 1;
WHILE (D[I].KEY>H.KEY) AND (J>L) DO
(* SUCHE VON RECHTS *) J := J - 1;
IF I<=J THEN
BEGIN SWAP (D[I], D[J]); I := I + 1; J := J - 1 END;
UNTIL I>J;
(*JETZT KÖNNEN DIE BEIDEN TEILE GETRENNT BEARBEITET WERDEN, ALSO
RECURSIV AUFGERUFEN WERDEN: *)
IF L<J THEN PARTITION (L,J);
IF I<R THEN PARTITION (I,R);
END; (* PARTITION *)
Die Prozedur Quicksort hat sich dann reduziert zu
PROCEDURE QUICKSORT (VAR D: DATA);
PROCEDURE SWAP (VAR X,Y : ITEM);
.....
PROCEDURE PARTITION (R,L : INTEGER);
.....
BEGIN
PARTITION (1,N);
END;
|
|
Der Algorithmus hat noch einen kleinen, nicht sofort sichtbaren Nachteil.
Durch die Rekursion im Aufruf von PARTITION kann sich der Bedarf an Speicherplätzen stark aufblähen, wenn die Anordnung der Daten ungünstig ist und die beiden entstehenden Teile sehr unterschiedliche Größen besitzen.
Denn die lokalen Variablen I, J, H und die Rücksprunginformation der Prozedur benötigen Speicherplatz.
Also muß das Programm so geändert werden, daß sich die Verschachtelungstiefe der Prozeduraufrufe in Grenzen hält.
Mit der folgenden Änderung ist die maximale Verschachtelungstiefe nur noch log2N.
Für eine Million Elemente bleibt die Verschachtelungstiefe also unter 30 (Tabelle 6).
| Tabelle 6: Verbesserter Rekursionsalgorithmus |
|
PROCEDURE PARTITION (L,R : INTEGER);
VAR I,J : INTEGER;
H : ITEM;
BEGIN
REPEAT (* SCHLEIFE ÜBER DIE AUFRUFE *)
I := L; J := R; H := D [(L+R) DIV 2];
REPEAT
WHILE (D[I].KEY<H.KEY) AND (I<R) DO I := I + 1;
WHILE (D[J).KEY>H.KEY) AND (J>L) DO J := J - 1;
IF I<=J THEN
BEGIN SWAP (D[I], D[J]); I := I + 1; J := J - 1 END;
UNTIL I>J;
(* NEUER TEIL: RECURSIONSTIEFE BEGRENZEN *)
IF (J - L)<(R - I) THEN
(* ERST DEN KLEINEREN TEIL BEARBEITEN *)
BEGIN
IF L<J THEN PARTITION (L,J);
L:=I
END
ELSE
BEGIN
IF I<R THEN PARTITION (I,R);
R:=I
END;
UNTIL R<=L;
END;
|
|
Um das Programm für Basic verarbeitbar zu machen, müssen aber jetzt noch die rekursiven Aufrufe in der Prozedur PARTITION entfernt werden.
Da die Aufrufstruktur recht einfach ist und als einzige Information die Parameter R und L aufzubewahren sind, bietet sich eine „Entrekursivierung" durch einen Kellerspeicher (Stack) an.
Der Stack wird hier durch ein lineares Feld STACK und eine Variable SP als Stackpointer repräsentiert:
VAR STACK : ARRAY [1..SL] OF
RECORD
R,L : integer
END;
SP : 0..SL;
SL ist die maximale Stacktiefe, man kommt hier mit 30 in jedem Fall aus (SL = LOG2N).
Da nun keine Aufrufe von PARTITION (bis auf den einen PARTITION(1,N)) mehr vorkommen und die Prozedur Quicksort auch recht kurz ist, wurde PARTITION in QUICKSORT einkopiert.
Übrigens ist die Stackversion auch in Pascal durchaus zu empfehlen, sie ist in bezug auf Speicherplatz und auch auf Rechenzeit die effizienteste.
Die Programmlistings sind in Bild 14 und Bild 15 abgedruckt.
PROCEDURE QUICKSORT (VAR D : DATA);
(* SORTIEREN DES FELDES D NACH DEN SCHLUESSELN D[..].KEY
IN AUFSTEIGENDER FOLGE.
GLOBALE KONSTANTE : N FELDLAENGE
GLOBALE TYPEN: ITEM = RECORD KEY : ...; INFO : ... END;
DATA = ARRAY [1..N] OF ITEM;
*)
(* ENTRECURSIVIERT, STACKLAENGE BEGRENZT *)
CONST SL = 30;
VAR I,J,L,R : 0..N;
SP : 0..SL;
H : ITEM;
STACK : ARRAY [1..SL] OF RECORD L,R : INTEGER END;
PROCEDURE SWAP (VAR X,Y : ITEM);
VAR Z : ITEM;
BEGIN Z := X; X := Y; Y := Z END;
BEGIN
(* STACK INITIALISIEREN *)
SP := 1; STACK[1].L := 1; STACK[1].R := N;
REPEAT
(* DIESE SCHLEIFE ERSETZT ZUSAMMEN MIT DEM STACK
DIE RECURSION *)
(* OBERSTES STACKELEMENT HOLEN *)
L := STACK[SP].L; R := STACK[SP].R; SP := SP - 1;
REPEAT
(* PARTITION *)
I := L; J := R; H := D[ (L+R) DIV 2];
REPEAT
WHILE (D[I].KEY<H.KEY) AND (I<R) DO I := I + 1;
WHILE (D[J].KEY>H.KEY) AND (J>L) DO J := J - 1;
IF I <= J THEN
BEGIN SWAP(D[I],D[J]); I := I + 1; J := J -1 END;
UNTIL I>J;
IF (R - I) > (J - L) THEN
BEGIN
IF L < J THEN
BEGIN (* PARTITION (L,J) *)
SP := SP + 1; STACK[SP].L := L; STACK[SP].R := J
END;
L :=I;
END
ELSE
BEGIN
IF I < R THEN
BEGIN (* PARTITION(I,R) *)
SP := SP + 1; STACK[SP].L := I; STACK[SP].R := R
END;
R := J;
END;
UNTIL R <= L; (* ENDE PARTITION *)
UNTIL SP = 0;
END (* QUICKSORT *);
|
Bild 14. Quicksort ist normalerweise das schnellste Sortierverfahren
60000 REM * * * * * * * * * * QUICKSORT * * * * * * * * * *
60001 REM * SORTIEREN DES FELDES I$ NACH DEN SCHLUESSELN
60002 REM * IN DEM FELD K.
60003 REM * DIE ELEMENTE K(J) UND I$(J) BILDEN EIN PAAR
60004 REM * SCHLUESSEL - INFORMATION.
60005 REM * DIE UNTERE FELDGRENZE IST 1, DIE OBERE FELD-
60006 REM * GRENZE STEHT IN DER VARIABLEN N.
60010 DIM S(30,2)
60020 REM S IST STACK, WOBEI S(..,1)<=>STACK[..].L UND
60030 REM S(..,2)<=>STACK[..].R ENTSPRICHT. S1 IST STACKPOINTER
60040 S1 = 1
60050 S(1,1) = 1
60060 S(1,2) = N
60070 REM STACK IST INITIALISIERT. "RECURSIONSSCHLEIFE"
60080 L = S(S1,1)
60090 R = S(S1,2)
60100 S1 = S1 - 1
60110 REM PARTITION
60120 I = L
60130 J = R
60140 H = K( INT(L+R)/2 )
60150 H$ = I$( INT(L+R)/2 )
60160 IF (K(I)>=H) OR (I>=R) THEN 60190
60170 I = I + 1
60180 GOTO 60160
60190 IF(K(J)<=H) OR (J<=L) THEN 60220
60200 J = J - 1
60210 GOTO 60190
60220 IF I> J THEN 60320
60230 REM SWAP (DATA[I],DATA[J])
60240 Z = K(I)
60250 Z$ = I$(I)
60260 K(I) = K(J)
60270 I$(I) = I$(J)
60280 K(J) = Z
60290 I$(J) = Z$
60300 I = I + 1
60310 J = J - 1
60320 IF I<=J THEN 60160
60330 IF (R - I)<=(J - L) THEN 60400
60340 IF L>=J THEN 60380
60350 S1 = S1 + 1
60360 S(S1,1) = L
60370 S(S1,2) = J
60380 L = I
60390 GOTO 60450
60400 IF I>=R THEN 60440
60410 S1 = S1 + 1
60420 S(S1,1) = I
60430 S(S1,2) = R
60440 R = J
60450 REM ENDE PARTITION
60460 IF R>L THEN 60110
60470 REM ENDE "RECURSIONSSCHLEIFE"
60480 IF S1<>0 THEN 60070
60490 RETURN
60500 REM * * * * * * * * * * * * * * * *
|
Bild 15. Quicksort als Basic-Unterprogramm
Ergebnisse des Effizienzvergleichs
Die beschriebenen Sortierverfahren wurden, wie bereits einleitend bemerkt, einem Vergleich ihrer Arbeitsgeschwindigkeit unterzogen.
Jedes Sortierprogramm wurde dazu zum Sortieren von drei Arten von Datensätzen herangezogen:
- aufsteigend sortierte Schlüssel
- zufällig angeordnete Schlüssel
- absteigend, d. h. umgekehrt sortierte Schlüssel
Jeder Testlauf wurde einmal mit 100 Feldelementen als Beispiel für eine kleine Datenmenge und mit 1000 Feldelementen als Beispiel für eine mittlere Datenmenge durchgeführt.
Die Zeitmessungen wurden nur für die Pascal-Proceduren durchgeführt;
die hier ermittelten Zeitverhältnisse lassen sich aber in ihrer Größenordnung auf die BASIC-Programme übertragen.
Für die Erzeugung von annähernd gleich verteilten Zufallszahlen im Bereich von 0 bis 9999 wurde der folgende einfache Algorithmus verwendet:
SEED := (131071 (* 217-1 *) * SEED) MOD 2147483647 (* 221-1 *);
RANDOMNUMBER := SEED DIV 214748;
Die Variable SEED wird mit der Primzahl 797 initiiert.
Die Ergebnisse finden Sie in Bild 16.
FELDLAENGE : 100 ELEMENTE.
=============================
SORTIERPROZEDUR SORTIERT ZUFAELLIG UMGEKEHRT
-----------------------------------------------------
LINEARES EINFUEGEN 0.001 0.022 0.048 SEKUNDEN.
BINAERES EINFUEGEN 0.004 0.018 0.035 SEKUNDEN.
BUBBLESORT 0.032 0.078 0.136 SEKUNDEN.
SHAKERSORT 0.001 0.071 0.143 SEKUNDEN.
HEAPSORT 0.014 0.013 0.012 SEKUNDEN.
QUICKSORT 0.004 0.010 0.006 SEKUNDEN.
FELDLAENGE : 1000 ELEMENTE.
=============================
SORTIERPROZEDUR SORTIERT ZUFAELLIG UMGEKEHRT
-----------------------------------------------------
LINEARES EINFUEGEN 0.018 2.434 4.808 SEKUNDEN.
BINAERES EINFUEGEN 0.067 1.511 2.939 SEKUNDEN.
BUBBLESORT 3.172 8.354 13.406 SEKUNDEN.
SHAKERSORT 0.007 7.714 14.257 SEKUNDEN.
HEAPSORT 0.183 0.173 0.163 SEKUNDEN.
QUICKSORT 0.049 0.124 0.062 SEKUNDEN.
|
Bild 16. Effizienzvergleich der beschriebenen Sortierverfahren in Abhängigkeit vom Zustand des zu sortierenden Feldes
Wie man sieht, ist Quicksort absoluter Spitzenreiter mit einer Durchschnittszeit von 0,079 Sekunden.
Die Prozedur Bubblesort liegt abgeschlagen auf dem letzten Platz, sie braucht im Schnitt über einhundertmal länger als Quicksort.
Die Prozedur Shakersort, die eigentlich doch einen recht vielversprechenden Eindruck machte, eignet sich nur für schon vorsortierte Felder.
Die Prozedur Heapsort, die sich auch gut für ein Sortieren in umgekehrter Reihenfolge eignet, schneidet bei ungeordneten Daten nur wenig schlechter als Quicksort ab.
Abschließend läßt sich sagen, daß Bubblesort und Shakersort recht unbrauchbar sind, daß sich bei wenigen Daten die Mühe nicht lohnt, einen aufwendigen Algorithmus zu verwenden und daß für große Datenmengen Heapsort und Quicksort die besten Algorithmen darstellen.
Suchen
Besonders bei der Textverarbeitung ist neben dem alphabetischen oder numerischen Sortieren das Suchen nach bestimmten Merkmalen ein häufig auftretendes Programmierproblem.
In unserer folgenden Betrachtung versuchen wir, das Suchproblem möglichst allgemeingültig zu betrachten und dadurch zu universell verwendbaren Problemlösungen zu gelangen.
Abbruchbedingungen bei Suchverfahren
Ein Suchvorgang in einer Datenmenge kann aus zwei Gründen beendet werden:
- Das Ende der Datenmenge ist erreicht, ohne daß der gewünschte Schlüssel angetroffen wurde.
- Der gesuchte Schlüssel wurde gefunden.
So kann der Zustand eines Suchalgorithmus in jeder Phase seiner Ausführung durch drei Zustandsbezeichnungen klassifiziert werden:
- suchend
- gefunden
- Datenende = nicht gefunden
In Pascal läßt sich diese Erkenntnis durch die Definition
„TYPE SEARCHSTATUS = (SEARCHING, FOUND, ENDOFDATA);"
sofort in das Programm übertragen.
Der Suchalgorithmus kann dann ganz allgemein aufgestellt werden (Tabelle 7).
| Tabelle 7: Allgemeine Form des Suchalgorithmus |
|
PROCEDURE SEARCH (VAR D : DATA; GESUCHT : INTEGER; VAR STAT :
STATUSTYP; VAR POS : INTEGER);
(* PARAMETER:
D: DAS ALTBEKANNTE DATENFELD
GESUCHT: DER SCHLÜSSEL, NACH DEM GESUCHT WIRD!
(BEACHTEN SIE DEN TYP DES SCHLÜSSELS BEI
ÄNDERUNGEN DER PROZEDUR)
STAT: DER STATUS, DER ZUM ENDE DER PROZEDUR FÜHRTE
(ENTWEDER 'FOUND' ODER 'ENDOFDATA')
POS: FALLS STAT=FOUND DER INDEX DES GESUCHTEN DATEN-
ELEMENTES SONST UNDEFINIERT *)
BEGIN
STAT := SEARCHING;
REPEAT
(* WÄHLE EIN ELEMENT D [POS] AUS *)
IF D [POS].KEY = GESUCHT THEN
STAT := FOUND
ELSE
IF (* ENDBEDINGUNG ERFÜLLT *) THEN
STAT := ENDOFDATA;
UNTIL STAT<>SEARCHING;
END;
|
|
Suchen in ungeordneten Daten
Wenn die zu durchsuchenden Daten nicht sortiert vorliegen, oder wenn es sich bei den Daten um eine sequentielle Datei handelt, bei der immer nur ein Element zugänglich ist, bleibt nichts weiter übrig, als das Datenfeld vom Anfang ausgehend Schritt für Schritt zu durchsuchen.
Der Algorithmus ist dann sehr einfach; die Unterprogramme sind in Bild 17 und Bild 18 aufgelistet.
PROCEDURE LINSEARCH (VAR D : DATA; GESUCHT : INTEGER;
VAR STAT : STATUS; VAR POS : INTEGER);
(* DURCHSUCHEN DES FELDES D NACH DEM SCHLUESSEL 'GESUCHT'.
DIE VARIABLE 'STAT' GIBT AN, OB DIE SUCHE ERFOLGREICH WAR
(STAT = FOUND) ODER NICHT (STAT = ENDOFDATA).
DIE VARIABLE POS GIBT IM ERFOLGSFALL DIE POSITION DES
GEFUNDENEN ELEMENTES (D[POS]) AN.
GLOBALE KONSTANTE : N FELDLAENGE
GLOBALE TYPEN :
ITEM = RECORD KEY : INTEGER; INFO : ... END;
DATA = ARRAY [1..N] OF ITEM;
STATUS = (SEARCHING,FOUND,ENDOFDATA);
WIRD DER TYP YON 'KEY' GEAENDERT, MUSS DER GLEICHE TYP
BEI 'GESUCHT' GENOMMEN WERDEN.
*)
BEGIN
STAT := SEARCHING;
POS := 0;
REPEAT
POS := POS + 1;
IF GESUCHT = D[POS].KEY THEN STAT := FOUND
ELSE
IF POS = N THEN STAT := ENDOFDATA
UNTIL STAT <> SEARCHING;
END;
|
Bild 17. Lineare Suche als Pascal-Prozedur: einfach, aber langsam
70000 REM * * * * * * * * * * LINEARE SUCHE * * * * * * * * * *
70001 REM * SUCHE NACH DEM ELEMENT G IM FELD K.
70002 REM * FALLS E=1 DANN IST DAS GESUCHTE ELEMENT K(P),
70003 REM * FALLS E=0 IST G NICHT IM FELD.
70010 E=0
70015 REM E=0 BEDEUTET NICHT GEFUNDEN
70020 P=0
70025 REM HOCHZAEHLEN VON P
70030 P=P+1
70040 IF G<> K(P) THEN 70060
70050 E=1
70055 REM GEFUNDEN
70060 IF (E=0) AND (P<N) THEN 70030
70070 RETURN
70080 REM * * * * * * * * * * * * * * * *
|
Bild 18. Lineare Suche als Basic-Unterprogram
Da in Basic keine Datendefinitionsmöglichkeit besteht, wird hier eine logische Variable verwendet, die den Erfolg der Suche anzeigt:
E = 0 Suche erfolglos beendet
E = 1 Suche erfolgreich beendet
Eingescanned von
Werner Cirsovius
September 2002
© Franzis' Verlag
![[1. Teil]](../../gif/arrow_left.gif){kind=icon}
![[Inhalt]](../../gif/arrow_up.gif){kind=icon}
![[3. Teil]](../../gif/arrow_right.gif){kind=icon}