ENGLISH

Quicksort

By Sedgewick

Book information

Publisher
Dissertations-G
Year
1980
ISBN
9780824044176, 0824044177
LCC
QA76.6 .S44 1980
Open Library ID
OL4426748M
Language
english
Format
DJVU
Filesize
2 MB (2560423 bytes)
Series
Outstanding Dissertations in the Computer Sciences
Edition
1
Pages
353\353
Topic
Computers
Library
Kolxo3
DPI
300
Time added
2009-07-20 03:45:11

Description

A complete study is presented of the best general purpose method for sorting by computer: C. A. R. Hoare's Quicksort algorithm. Special attention is paid to the methods of mathematical analysis which are used to demonstrate the practical utility of the algorithm. The most efficient known form of Quicksort is developed, and exact formulas are derived for the average, best case, and worst case running times. The merits of the many modifications which have been suggested to improve Quicksort are discussed, with an emphasis on their impact upon the analysis. Van Emden's method, samplesort, and the median-of-three modification are discussed in detail, and it is shown that the latter is the most effective improvement to Quicksort for practical sorting applications.

Similar books