McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
Introduction to Algorithms, 2/e
Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University
Quicksort

Chapter Objectives

[The treatment in the second edition differs from that of the first edition. We use a different partitioning method—known as “Lomuto partitioning”—in the second edition, rather than the “Hoare partitioning” used in the first edition. Using Lomuto partitioning helps simplify the analysis, which uses indicator random variables in the second edition.]

Quicksort
• Worst-case running time: Θ (n2).
• Expected running time: Θ (n lg n).
• Constants hidden in Θ (n lg n) are small.
• Sorts in place.










Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.