An analysis of selection sort using recurrence relations

Autores: Francesc Josep Ferri Rabasa , Jesús Albert
Localización: Questiió: Quaderns d'Estadística, Sistemes, Informatica i Investigació Operativa, ISSN 0210-8054, Vol. 20, Nº. 1, 1996, págs. 111-119
Idioma: inglés
Títulos paralelos:
- Análisis de clases de selección usando relaciones de recurrencia
Enlaces
- Texto completo (pdf)
Resumen
- This paper presents a method for obtaining the expected number of data movements executed by the well-known Selection sort algorithm along with its corresponding variance. The approach presented here requires hardly any specific mathematical background. In particular, the average-case cost and variance are represented using recurrence relations whose solutions lead to the desired results. Even though this method is not applicable in general, it serves to conveniently present average-case algorithm analysis in depth in an elementary course on Algorithms