在某些条件下，快速排序中分区中的最小部分？

Question

设0 < a < 0.5为某个常数。我们有一个 n-element 数组作为输入。随机快速排序从数组中随机均匀地选择一个元素作为基准和分区。最小部分大于an的概率是多少。我在笔记中的简短回答是概率 1-2a。任何人都可以说这个概率是如何计算的？

Answer 1

较小分区的大小均匀分布在[0,n/2]范围内，因此小于an的概率为an / (n/2)。所以大于a的概率是1 - an / (n/2)。 an/(n/2) 恰好是 2a，因此概率 1 - 2a。

这是一张图表，希望对您有所帮助：

                     Pivot positions

                a·n    n/2            a·n+n/2   n 
                 v      v                v      v
<---------------------|||||||·---------------------|||||||>
                     /---^---\                    /---^---\
              smaller partition on left   smaller partition on right
                   bigger than a·n              bigger than a·n
                   size: n/2 - a·n           size: n - (a·n + n/2)
                             Total size: n - 2a·n
                              Probability: 1 - 2a

在某些条件下，快速排序中分区中的最小部分？

Smallest part in Partition in Quick Sort with some conditions?

sorting

math

partitioning

probability

quicksort