Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hinweise zu
sortcompetition.c

• Es handelt sich nicht um ein reines C-Programm, daher ist es mit g++ zu übersetzen.

• Beim Übersetzen sollte man durchaus auch den Optimizer des Compilers einschalten -O1 und -O2 (siehe man g++).

• Der Aufruf des Programmes lautet

  ./sortcompetition len type delay

  Dabei ist len die Länge des zu sortierenden Arrays, type die Arte der Folge (0,1= zufällig erzeugt, 2=aufsteigend sortiert, 3 absteigend sortiert, 4 auf/-absteigend sortiert), und delay eine künstliche Verlängerung des compare-Befehls auf Integers um etwa den faktor delay.

• Da einige Sortierprogramme sehr lange laufen (wie Insertionsort), einige auf bestimmten Eingaben lange laufen (wie diverse Quicksorts), und einige zuviel Speicher benötigen (wie Mergesort), werden diese für bestimmte Eingabegrößen nicht mehr aufgerufen. Dies kann man natürlich selber verändern, indem man die Quellen editiert und neu compliliert.

• Man rufe insbesondere Quicksort auf sortierten und den C-Library-Call qsort auf der auf/-absteigend sortierten Folge auf. Insbesondere bei letzterem ist man zutiefst überrascht :o)

• Man vergleiche die einzelnen Sortierverfahren auch für verschiedene delays, dabei ist es wohl nicht mehr realistsich delay größer als 10 zu wählen.

• Natürlich ist man aufgefordert die einzelnen Varianten noch zu tunen, sich selber neue Eingabefolgen zu konstruieren etc.

• Die Erläuterungen zu den Sortierverfahren (wie sie implementiert sind) findet man im Quellcode.