| Summary: | C.A.R. Hoare's quicksort algorithm has become a very popular sorting algorithm due to the average performance of θ(n log n), limited use of extra storage (typically θ(logn) recursive calls) and better performance on average compared to heapsort (another θ(n log n) sorting algorithm). It may be found in several standard libraries supporting C, C++, and Java. The major drawback in the quicksort algorithm is the θ(n²) worse case performance. Unfortunately, this performance is exhibited for some rather common initial permutations. The author intends to look into this performance of the quicksort algorithm, and in particular potential modifications to minimize the probability that the worst-case performance will be exhibited.
|
|---|