The analysis of Quicksort programs

Research output: Contribution to journalArticle

87 Scopus citations

Abstract

The Quicksort sorting algorithm and its best variants are presented and analyzed. Results are derived which make it possible to obtain exact formulas describing the total expected running time of particular implementations on real computers of Quicksort and an improvement called the median-of-three modification. Detailed analysis of the effect of an implementation technique called loop unwrapping is presented. The paper is intended not only to present results of direct practical utility, but also to illustrate the intriguing mathematics which arises in the complete analysis of this important algorithm.

Original languageEnglish (US)
Pages (from-to)327-355
Number of pages29
JournalActa Informatica
Volume7
Issue number4
DOIs
StatePublished - Dec 1 1977
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'The analysis of Quicksort programs'. Together they form a unique fingerprint.

  • Cite this