Jeder Mensch, der in einem Lexikon geblaettert, eine Telefonnummer gesucht, Dateiinhaltsverzeichnisse gelesen oder Karten gespielt hat, wird die Uebersichtlichkeit von und die Effizienz des Umganges mit geordnet vorliegenden Objekten bestaetigen koennen. Die Vor- bzw. Aufbereitung von miteinander vergleichbaren Objekten, wird als Ordnen, Auslesen, Gruppieren oder auch Sortieren bezeichnet. Die Objekte werden auch Datensaetze genannt und lassen sich in die fuer die Sortierung relevanten Schluessel und die uebrige Information einteilen. Je nach Aufgabenstellung kann diese Einteilung variieren. Die Schluessel koennen sehr komplex, die Operationen zwischen ihnen somit sehr aufwendig sein. Da die Datenmengen haeufig gross sind und die Sortierung nach der Festlegung einer Vorgehensweise eine mechanische Aufgabe ist, werden Computer insbesondere als Informationssysteme fuer die Verarbeitung von elektronisch erfassten Daten eingesetzt. Der Entwurf von guten Sortieralgorithmen ist so zu einem fundamentalen Problem in der Informatik geworden. Der besondere Reiz der bekannten Verfahren liegt besonders in der Einfachheit der Ideen, die gut erlern-, vermittel- und uebertragbar sind. Desweiteren ermoeglichen sie vielfach eine praezise und beispielhafte Analyse der Effizienz. Demnach werden Sortieralgorithmen in jeder programmiertechnischen Ausbildung bis hin zur Universitaet gelehrt. Die Zeitkomplexitaet (vergl. Wegener(1994)) des Sortierproblems ist mittlerweile sowohl im schlechtesten als auch im mittleren Fall bekannt, d.h. zu den theoretisch ermittelten unteren Grenzen existieren Algorithmen, die die gleiche Wachstumsordnung besitzen. Somit stellt sich die Frage, warum noch an der Weiterentwicklung und Analyse von Sortierverfahren geforscht wird. Auf der Suche nach Gruenden finden sich folgende Punkte: - Jede Verbesserung eines Sortierverfahrens oder der eventuell zugrunde liegenden Datenstruktur fuehrt direkt zur Verbesserung unzaehliger Programme, die einen Zugriff auf sortierte Daten benoetigen. - Je nach intern oder extern vorliegenden Daten, komplexen oder einfachen Schluesseln, grossen oder kleinen Datenmengen, Grad der Vorsortiertheit bzw. Verteilung der Datensaetze, Anforderungen an die Stabilitaet etc. unterscheiden sich die zu empfehlenden Algorithmen enorm. - Sei es die worst-case Analyse von SHELLSORT oder die average-case Analyse von HEAPSORT, viele Probleme beduerfen noch einer genauen Klaerung. - Die Angabe der Effizienz eines Algorithmus in der Lanudau'schen O--Notation verbirgt die Vorfaktoren der zu beschreibenden Funktion. Um das unterschiedliche Laufzeitverhalten von Sortieralgorithmen zu erklaeren, muss die Guete der Approximation verbessert werden. - Fortschritte des sequentiellen Sortieren haben eine enorme Durchschlagskraft in der Fachwelt, die sich seit ihren Anfaengen mit dem Problem beschaeftigt und ueber eine gemeinsame Grundlage verfuegt. In dieser Diplomarbeit wird der Algorithmus WEAK--HEAPSORT vorgestellt und analysiert, der von Ronald D. Dutton 1993 in der Zeitschrift BIT veroeffentlicht wurde. Duttons Ausfuehrungen ist zu wenig Aufmerksamkeit geschenkt worden. Die wichtigsten Merkmale dieses Algorithmus fuehren den Leser an die ausgearbeiten Abschnitte: Sortieren durch Auswaehlen: In dieser HEAPSORT-Variante besteht der Sortiervorgang von $n$ Elementen aus einem Aufbau einer $PriorityQueue$--Datenstruktur (biggest in, first out) namens Weak-Heap mit anschliessendem $n$-maligen Entnehmen eines Elementes (vergl. Kapitel 3). Aufbau: Die Weak-Heap Datenstruktur kann mit optimalen $n-1$ Vergleichen und $O(n)$ uebrigen Operationen aufgebaut werden (vergl. Kapitel 3.2.3) oder ohne Vergleiche aus einem Heap gewonnen werden (vergl. Kapitel 12.2). Das MIN-MAX-Problem kann mit Weak-Heaps optimal geloest werden (vergl. Kapitel 12.1). -Einfachheit der Idee: Da sich die Heap-Anforderung als zu restriktiv erweist, wird sie abgeschwaecht (vergl. Kapitel 3.1). Vergleichskriterien: Der WEAK-HEAPSORT-Algorithmus erfuellt alle 7 Kriterien an einen Sortieralgorithmus (vergl. Kapitel 2). -Performance: Die Laufzeitbestimmungen des best- und worst-cases sind einfach: Mit $k = \lceil \log n \rceil$ benoetigt der Algorithmus mindestens $nk - 2^k + 1 \ge n \log n - n$ und hoechstens $nk - 2^k + n - k \le (n-1) \log n + 0.1n$ Vergleiche (vergl. Kapitel 3.2). Insbesondere sind die ermittelten Grenzen {\em scharf} (vergl. Kapitel 5 und 6.4), d.h. es gibt Beispiele, bei denen diese Grenzen auch angenommen werden. Die empirisch ermittelten praktischen Vergleiche zu bekannten Sortierverfahren bestaerken die ausserordentliche Geschwindigkeit des Algorithmus (vergl. Kapitel 13). Verbesserung: Der worst-case laesst sich mindestens um den Summanden $\log n$ entschaerfen (vergl. Kapitel 4). Binaerer Baum: Die generierten und als binaere Baeume aufgefassten Weak-Heaps lassen sich in einen Allgemeinen Heap einbetten, sind untereinander gleichverteilt, und die Anzahl ist damit leicht zu bestimmen (vergl. Kapitel 3.1 und 7.2). Rueckwaertsbetrachtung: Der Algorithmus l"asst sich sowohl in der Aufbau- als auch Auswahlphase rueckwaertig studieren und ermoeglicht so, Aussagen ueber die Struktur, Anzahl und Verteilung von Weak-Heaps zu machen (vergl. Kapitel 8 und 9). Diese Betrachtung bietet vielversprechende Ansaetze zur average-case Analyse (vergl. Kapitel 11.2). Letztendlich koennen alle Weak-Heaps auch rueckwaertig aus dem einzigen Weak-Heap der Groesse 1 generiert werden (vergl. Kapitel 11.3). Datenstruktur: Der Weak-Heap bietet als $PriorityQueue$ auch im allgemeinen Fall effiziente Operationen an. Das Einfuegen ist in ungefaehr $(\log n)/2$, das Loeschen in exakt $\lceil \log(n+1) \rceil - 1$ Schritten m"oglich (vergl. Kapitel 12.3). Den Staerken des Algorithmus steht eine zu diskutierende Schw"ache entgegen. Pro Schluessel ist ein Zusatz- bzw. Informationsbit fuer den Algorithmus unabdingbar. Da allgemeine Schluesselvergleichsverfahren erst fuer das Sortieren komplexer Schluessel (reelle Zahlen, viele Entititaeten) zu empfehlen sind, wird die Zeit fuer den Vergleich als auch den Tausch zweier Objekte als gross angesehen. Der Tausch von zwei Datensaetzen bzw. deren Schluessel kann jedoch durch den Tausch von Zeigern auf die entsprechenden Stellen simuliert werden. So ist die Anzahl der Vergleiche in der Theorie zum Massstab der Analyse geworden: Ein Zeiger und damit insbesondere ein Bit sind demnach klein gegenueber der Schluesselgroesse. Vielfach wird der volle zu Verfuegung stehende Wertebereich der auftretenden Schluessel nicht ausgeschoepft und das Zusatzbit kann haeufig effektiv, z.B. als Vorzeichenbit, integriert und verarbeitet werden. Praktisch wird somit kein zusaetzlicher Speicherplatz verbraucht. Auch der zur Sortierung am haeufigsten verwendete QUICKSORT Algorithmus benoetigt Zusatzspeicher in Form eines Rekursionsstacks mindestens logarithmischer Groesse, indem die lokalen Indexvariablen und die Ruecksprungadressen abgelegt werden muessen. Die meisten Implementierungen benoetigen jedoch aus zwei Gruenden einen Stack linearer Groesse: aus einer naheliegenden - jedoch ungeschickten - Abarbeitung der aufgeteilten Objektmenge (der kleinere Teil muss vor dem groesseren abgearbeitet werden), als auch durch die Unfaehigkeit vieler gaengiger Interpreter bzw. Compiler, End- bzw. tail-Rekursionen zu erkennen (vergl. Abelson und Sussman (1984)). Die Anforderung, innerhalb der gegebenen Datenarraystruktur ohne grossen Speicheraufwand sortieren zu koennen, erscheint trotz der Notwendigkeit von linear vielen Zusatzbits erfuellt. Demnach sollte der WEAK-HEAPSORT Algorithmus sowohl in programmiertechnischen Ausbildungen als auch an der Universitaet neben den anderen Verfahren gleichberechtigt gelehrt werden. Literaturverweise zu Saetzen oder Hilfssaetzen befinden sich durchgehend hinter dem Wort 'Beweis'. Wesentliche Veraenderungen zu den referierten Originalarbeiten werden durch Fussnoten hervorgehoben. In erster Linie danke ich Herrn Univ. Prof. Dr. Ingo Wegener fuer die ausgezeichnete fachliche und persoenliche Betreuung meiner Diplomarbeit. Weiterhin gilt mein Dank Erik Doernenburg und Frank Rettberg, die mich bei der Implementierung der Algorithmen fuer das in Kapitel 13 beschriebene Programm Sorting in Action unterstuetzten. Erik Doernenburg und Armin M. Warda haben mir ausserdem einige wertvolle Hinweise bei den abschliessenden Korrekturen der Arbeit gegeben. Ich moechte diese Diplomarbeit Dr. John Kelly widmen, dessen sprachfussnotenreiche Vorlesungen am University College Dublin ich waehrend meines Auslandaufenthaltes geniessen durfte und der Anfang dieses Jahres verstarb. Trotz oder gerade aufgrund der von mir geteilten mathematischen Leidenschaft beschaeftigte er sich mit der Grenze menschlicher und kuenstlicher Intelligenz (Kelly (1993)), dessen Essenz ich gerne abschliessend sinngemae"s zitieren moechte und somit eine Absage der "Ubertragung von Vergleichbarkeiten menschlichen und maschinellen Sortierens auf die der Intelligenz erteile: - Die Natur menschlicher Intelligenz ist schwer erfassbar und laesst keine fuegsame Formalisierung oder effektive Charakterisierung zu. - Soweit heutzutage verstanden und mittels konzeptioneller Analyse enthuellt, existiert eine grosse Divergenz zwischen der Ontologie (Lehre des Seins) der Maschine und des Menschen. - Computer werden irrtuemlicherweise als Symbolprozessoren charakterisiert. In ihnen selbst sind sie bloss Signalprozessoren. - Computer-Systeme, sowohl die traditionelle Hardware oder Software oder die modernen neuronalen Netze, koennen am besten als Texte verstanden werden. - Computer haben keine Moeglichkeit, in einem tiefen Sinn des Wortes zu {\em handeln}. Sie {\em tun} nichts. - Falsche Konzepte ueber die Moeglichkeiten von Computern und Fehlinterpretationen der Computerrechenleistung entstehen aus: -- uebertriebener Vermenschlichung von Maschinen, -- dem Zauber eines existentiellen Irrtums oder dem Trugschluss falschplazierter Korrektheit, -- der Abhaengigkeit von einer einfachen Liste, die eine notwendige Einheit darbieten soll, -- unangemessene Einstellung zur Staerke der Wissenschaft[...], dem Glauben an die Zulaessigkeit von Sprache. Die Abhaengigkeit der Computer von der menschlichen Sprache zeigt die Grenzen ihrer Moeglichkeiten auf, da menschliche Erkenntnis, sogar sprach-verbundene Erkenntnis, ultimativ in Unaussprechlichkeit wurzelt.