Probabilistic analysis of the time complexity of quicksort

✍ Scribed by Tadashi Mizoi; Shunji Osaki

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 460 KB
• Volume: 79
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/ecjc.4430790304

✦ Synopsis

Abstract

Quicksort is a well‐known sorting algorithm based on the divided control. the array to be sorted is divided into two sets as follows. an element in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value are constructed. Each of those two sets are sorted independently. the procedure is iterated for the divided sets. In other words, the algorithm has a recursive structure. the average time‐complexity of the quicksort (the average number of comparisons) is O(n log n). Depending on the data to be sorted, however, the performance may be deteriorated drastically. In the worst case, the time complexity is O(n^2^).

In this paper, the generating function based on the time complexity of the quicksort is introduced and the mean and the variance of the time complexity is determined analytically using the generating function. Based on the derived mean and the variance, the chi‐square test is applied as to whether or not the distribution of the time complexity can be approximated by the normal distribution. Then, a method is proposed in which the probability R(x) that the time complexity exceeds a certain value x is determined accurately by approximating the distribution of the time complexity of the quicksort by a three‐parameter Weibull distribution. Finally, the selection of the sorting algorithm is discussed.