Digitale Pioniere (37): Tony Hoare: Meister der Ordnung

Aller Ehren wert

Ordnung muss sein – auch in der Datenverarbeitung. Rund ein Viertel der kommerziellen Rechenzeit wird für Sortieraufgaben benötigt (Telefonbücher, Kundenlisten, etc.). Tony Hoare hat mit dem Quicksort-Algorithmus ein effektives Werkzeug dafür geschaffen.

Zur Person

Tony Hoare wurde 1934 in Colombo (Sri Lanka) geboren. In Oxford absolvierte er ein humanistisches Studium, wechselte dann aber zur Statistik. Als Gaststudent ging er nach Moskau, um computerunterstützte Sprachübersetzung zu erforschen. Seine Russischkenntnisse hatte er zuvor während des Militärdienstes in der Royal Navy erworben.

Bald wurde der junge Informatiker auf das Problem der Sortierung aufmerksam. Diese ist wichtig, um in langen Listen bestimmte Einträge schnell zu finden. Um 1960 entwickelte Hoare „Quicksort“, einen Algorithmus, der das sehr schnell erledigen kann. Quicksort arbeitet rekursiv, das heißt er teilt die zu sortierende Liste in zwei möglichst gleiche Teile, sortiert diese einzeln und kann durch anschließendes Zusammenführen eine sortierte Gesamtliste erzeugen. Für das Sortieren der Teile wiederum wird einfach dasselbe Prinzip der Aufteilung benutzt. So müssen am Ende nur ganz kurze Listen tatsächlich sortiert werden.

Weiterhin stammt das „Hoare-Kalkül“ von ihm, mit dem sich dank einiger logischer Regeln überprüfen lässt, ob ein Algorithmus korrekt ist.

1968 wurde Hoare Professor für Computerwissenschaften an der Queen’s-Universität in Belfast. Neun Jahre später kehrte er zurück nach Oxford, wo er – bis zu seiner Emeritierung – die Arbeitsgruppe für Programmierung leitete.

1980 wurde der Informatiker mit dem Turing-Preis geehrt. In seiner Dankesrede merkte er süffisant an: „Es gibt zwei Wege, ein Software-Design zu erstellen. Entweder so einfach, dass es offensichtlich keine Schwächen hat, oder so kompliziert, dass es keine offensichtlichen Schwächen hat. Die erste Methode ist weitaus schwieriger.“

Gut zu wissen

Wenig Rechenzeit und wenig Speicherbedarf, so lauten die Vorgaben in der Informatik. Gemäß diesem Ziel wird Quicksort ständig weiter entwickelt.

Vor 75 Jahren stellte Konrad Zuse den ersten funktionsfähigen Computer Z3 in Berlin vor. Aus diesem Anlass blicken das Zuse-Institut Berlin und der Tagesspiegel am 11. Mai auf einer internationalen Konferenz in die digitale Zukunft: „The Digital Future – 75 Years Zuse Z3 and the Digital Revolution.“  75 Folgen über die wichtigsten Wegbereiter des digitalen Zeitalters zeigen, was bisher geschah. Mehr zur Veranstaltung: www.science-match.info