Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 01, 2011, 12:15 pm
Duration: 45 minutes
Location: CAB G51
Speaker: Isabelle Hurbain-Palatin
This paper by Sergi Elizalde and Peter Winkler analyses "homing", a sorting algorithm motivated by the hand-sorting of files. Elements are placed in their proper positions; the sorting is done "in place" by shifting the necessary elements.
Considering the number of steps involved, the following results are proved:
- the best case is fast,
- the worst case is very slow (but the algorithm always terminates),
- there is a super-exponential number of worst cases.
Automatic MiSe System Software Version 1.4803M | admin login