# Quicksort元素比较结果是随机的。元素处于某个位置的概率 -- sorting 领域 和 probability-theory 领域 和 quicksort 领域 cs 相关 的问题

## Quicksort where element comparison outcome is random. Probability of element being in a certain position

1

### 问题

` ` Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare);  ` `

` qsort() `通过quicksort排序阵列，其中我们使用最后一个元素 作为枢轴。比较它使用的两个元素` 99887665544332 `，其中 相等的概率（即，无论是1/2），将返回"1.元素更大" 或 "2.元素更大" ，永远不会"两者都是平等的" 。是什么 M8分别出现在0,1或2位置之后的概率 应用` qsort `

So we have this block of pseudocode:

``Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare); ``

`qsort()` sorts the array via quicksort where we use the last element as pivot. To compare two elements it uses `rand_compare`, which, with equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or "2. element is bigger" and never "both are equal". What is the probability that M8 appears in position 0, 1 or 2, respectively, after applying `qsort` ?

I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?

## 回答列表

2

0：（0.5 ^ 7）（0.5 ^ 0）（C（7,7））=（0.5 ^ 7）（1）= .0078125

1：（0.5 ^ 6）（0.5 ^ 1）（c（7,6））=（0.5 ^ 7）（7）= .0546875

2：（0.5 ^ 5）（0.5 ^ 2）（C（7,5））=（0.5 ^ 7）（21）= .1640625

In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625

1

Let us first recall how quicksort works. We start by choosing a pivot xe2x80x94 in your case $$M_8$$. We then partition the array into elements smaller than the pivot and larger than the pivot (breaking ties arbitrarily), and reorder the array in the following way:

elements smaller than the pivot; the pivot; elements larger than the pivot

We then recursively sort the elements smaller than the pivot, and the elements larger than the pivot.

The location of the pivot is the same as the number of elements smaller than the pivot. In your case, each of the elements $$M_1,\ldots,M_7$$ is smaller than the pivot $$M_8$$ with probability $$1/2$$.

You take it from here.

## 相关问题

7  为什么从Quicksort切换到依赖于Quicksort的最佳截止？  ( Why is the optimal cut off for switching from quicksort to insertion sort machin )

0  Quicksort算法的最糟糕的情况场景N / 2  ( Worst case scenario for quicksort algorithm with pivot element n 2 )

0  关于HOARE的分区计划和略微修改的问题  ( Question regarding hoares partitioning scheme and a slight modification to it )

2  是否有排序算法\$ n + k log {k} \$？  ( Is there a sorting algorithm of order n k logk )

1  合并排序优先于快速排序的方案  ( Scenarios where merge sort is preferred over quick sort )

6  哪种测量的分类解释了Quicksort运行时中的阶段过渡？  ( Which measure of sortedness explains the phase transition in quicksorts runtime )

2  如何陈述一种表达最糟糕的态度的复发？  ( How to state a recurrence that expresses the worst case for good pivots )

3  算法查找发生超过n / 10次的所有值  ( Algorithm to find all values that occur more than n 10 times )

1  如果输入集更加递减，Quicksort用于增加订单工作的速度更快？  ( Does quicksort for increasing order work faster if the input set is more decreas )

-2  Quicksort分区的概率创建了一个不平衡的分区  ( Probabilty that quicksort partition creates an imbalanced partition )

3  Quicksort分区成本  ( Cost of partitioning in quicksort )

0  Quicksort的平均案例运行时间分析很好参考  ( Good reference for average case runtime analysis of quicksort )

2  随机Quicksort中较小分区大小的概率界限  ( Probability bounds on size of smaller partition in randomized quicksort )

8  QuickSort Dijkstra 3路分区：为什么额外交换？  ( Quicksort dijkstra 3 way partitioning why the extra swapping )

4  从随机化Quicksort中的随机化  ( From whence the randomization in randomized quicksort )
cormen简要讨论了在Quicksort中挑选随机枢轴的优势。但是，如图所指这里（第4到最后一段）： 使用随机数发生器选择位置相对 昂贵 所以如何挑选实际实施的随机枢轴，以及如何随机？它不能太贵，因为我理解Quicksort的主要优势之一，超过其他\$ cal {o}（n lg n）\$ sorts是小的...

17  我们为什么不使用链接列表中的快速排序？  ( Why dont we use quick sort on a linked list )

-2  Quicksort实现不清楚  ( Quicksort implementation unclear )

100  Quicksort分区：Hoare与Lomuto  ( Quicksort partitioning hoare vs lomuto )
Cormen中提到了两个Quicksort分区方法： （参数 A 是阵列， [p, r] 是inround，handusive，要执行分区。返回的值是索引之后的索引分区。） Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true ...

1  大O：分析\$ O（n log n）\$ - 算法的时间复杂性  ( Big o analyzing the time complexity of an on log n algorithm )

1  Quicksort不变3条件带循环不变  ( Quicksort invariant 3 conditions with loop invariant )

2  可以置换相对较小的随机数子集并重复使用，并保证Quicksort等算法的良好预期运行时间？  ( Can a relatively small subset of random numbers be permuted and reused and still )

3  双枢轴Quicksort参考实施？  ( Dual pivot quicksort reference implementation )

8  不是线性时间o（n）？  ( Isnt linear time on )

2  Quicksort \$ t（n）_ {最佳} = oomega（n log n）\$验证  ( Quicksort tn best omegan log n proof )

1  表明Quicksort的最佳情况复杂性是\$ omega（n log n）\$  ( Show that the best case time complexity of quicksort is omegan log n )