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

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


简体版||繁體版
1
vote

问题

中文

所以我们有这个副偶像块:

  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

我真的不确定如何解决这个问题。直观地应为每个位置的1/8。它是否依赖于您使用的Quicksort的实施?

英文原文

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
 
vote
vote
最佳答案
 

在快速排序的情况下,在分区之后,您将每个元素放在小于p下方的Pivot P以及比其面大的每个元素。因此,在分区后,您知道枢轴处于正确的位置,因此它不会再次移动。由于您选择最后一个元素(M8)作为您的枢轴,因此这简化了过程,因为您只需要通过一次迭代。

将每个元素与M8进行比较时,您将随机告知M8更大或者其他元素是"更大" ,每个元素都有1/2个赔率,如果其他元素是"更大的" ,则它将放置到右边的m8。因此,对于M8最终在0,1或2的位置,它必须具有2或更小的元素,该元素被确定为"较小" 而不是M8。我们可以通过几何序列确定此概率:

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
 
vote

让我们首先召回Quicksort的工作原理。我们首先选择一个枢轴 - 在你的情况下 $ m_8 $ 。然后,我们将阵列分成小于枢轴的元素,大于枢轴(任意断开线圈),并以下列方式重新排序:

小于枢轴的元素;枢轴;元素大于枢轴

然后,我们递归地对小于枢轴的元件进行排序,元素大于枢轴。

枢轴的位置与小于枢轴的元素数量相同。在您的情况下,每个元素 $ m_1, ldots,m_7 $ 小于pivot $ m_8 $ 概率 $ 1/2 $

你从这里拿走它。

 

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 ) 
我未能理解为什么切断值将是系统依赖的,而不是常数。 来自普林斯顿大学网站 截止到插入排序。与合并一样,它会转换为 插入阵列的分类。截止值的最佳值是 系统依赖,但5到15之间的任何值都可能工作 在大多数情况下。 假设最佳截止值等于插入排序的最佳设置大小? ...

0  Quicksort算法的最糟糕的情况场景N / 2  ( Worst case scenario for quicksort algorithm with pivot element n 2 ) 
如果我决定始终占用位置上的元素 $ frac {n} {2} $ 作为枢轴元素,则是什么? ? 我知道如果我选择左或最右边的元素作为枢轴,则最坏情况会发生: 阵列已经以相同的顺序排序 数组已按相反顺序排序 所有元素都是相同的 并且那种情况下的复杂性是 $ mathcal {o}({n ^ 2})$ 。 但是,...

0  关于HOARE的分区计划和略微修改的问题  ( Question regarding hoares partitioning scheme and a slight modification to it ) 
这是Wikipedia上的伪代码,用于Hoare的分区方案: algorithm partition(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i...

2  是否有排序算法$ n + k log {k} $?  ( Is there a sorting algorithm of order n k logk ) 
我被赋予一个整数矢量,据说包含许多重复值(总计k个不同的整数),例如 [1, 4, 2, 5, 5, 3, 4, 2, 2, 5] (n = 10, k = 5) 和我被要求找到一个分类算法,其平均值 $ o(n + k log {k})$ 。我得出结论,部分Quicksort(或Quickselsort...

1  合并排序优先于快速排序的方案  ( Scenarios where merge sort is preferred over quick sort ) 
作为合并排序和Quicksort两者都具有$ O的平均时间复杂度(n log(n))$。在排序数据时,在哪个方案将在Quicksort中优先于Quicksore进行排序? ...

6  哪种测量的分类解释了Quicksort运行时中的阶段过渡?  ( Which measure of sortedness explains the phase transition in quicksorts runtime ) 
我目前正在创建一个分析Quicksort病理病例的程序。即,从$ O(n ^ 2)$到$ o(n log n)$的复杂性转换为数据集可减少订购。由于QuickSort是一种基于值的算法,因此枢轴的选择决定了其效率。我们通常(Quicksort 3,并选择一个随机元素),抛开作为阵列中的枢轴的第一个或最后一个元素。因...

2  如何陈述一种表达最糟糕的态度的复发?  ( How to state a recurrence that expresses the worst case for good pivots ) 
问题 考虑随机Quicksort算法,其预期$ theta(nlogn)$的最坏情况运行时间。概率$ FRAC12 $ FRAC12 $所选择的枢轴在$ frac {n} {4} $和$ frac {3n} {4} $(一个好的枢轴)之间。还有概率$ frac12 $ frac12 $的枢轴将在1到$...

3  算法查找发生超过n / 10次的所有值  ( Algorithm to find all values that occur more than n 10 times ) 
我在Coursera上占据了一个allOrytm课程,有一些<强大>可选的学生富集的问题。我无法解决以下任务: 十进制优势。给出了一个带n个键的数组,设计算法,以查找发生超过n / 10次的所有值。预期 算法的运行时间应该是线性的。 和作者证明在提示之后: 提示:使用QuickSelect和Check确定...

1  如果输入集更加递减,Quicksort用于增加订单工作的速度更快?  ( Does quicksort for increasing order work faster if the input set is more decreas ) 
在 Clrs对算法的介绍, 以下过程实现Quicksort: QUICKSORT(A; p; r) 1 if p < r 2 q D PARTITION(A; p; r) 3 QUICKSORT(A; p; q-1) 4 QUICKSORT(A; q+1; r) 对整个阵列A进行排序,初始呼叫是Quick...

-2  Quicksort分区的概率创建了一个不平衡的分区  ( Probabilty that quicksort partition creates an imbalanced partition ) 
我遇到了这个问题: 让0&lt; .5是一些常数(独立于输入阵列长度n)。调用Quicksort算法采用的分区子程序,如讲座中所述。有什么概率:通过随机选择的枢轴元件,分区子程序产生分割,其中两个子阵列中较小的尺寸为≥10倍的原始阵列的尺寸? 答案是1-2 *α。 任何人都可以解释我这个答案如何? ...

3  Quicksort分区成本  ( Cost of partitioning in quicksort ) 
我正在通过Sedgewick&amp阅读"algorithms第四版" ; Wayne和我想知道我是否在书中发现了错误,或者如果我不能将我的头围绕着如此简单。 在谈论Quicksort的复杂性时,这本书说,在比较数量的分区成本等于 N + 1 ,其中 99887665544331 等于到集合中的元素数量排序。我们假设...

0  Quicksort的平均案例运行时间分析很好参考  ( Good reference for average case runtime analysis of quicksort ) 
我是编程中的初级知识,知识技术知识。我被分配到Quicksort的平均案例分析中进行"阅读项目" 。我的意思是我必须在课堂上呈现它。现在,我需要一个很好的来源,我可以阅读它并找到我可以在演示中包含的材料。至于我对算法的现有知识,人们可以假设我几乎不知道,除了"只是代码" ,什么都没有任何关于他们的分析。任何具有严格证...

2  随机Quicksort中较小分区大小的概率界限  ( Probability bounds on size of smaller partition in randomized quicksort ) 
让0美元&lt;一个&lt; 0.5美元是一些常数。我们有一个$ n $ -element数组作为输入。随机化Quicksort随机选择一个元素,作为枢轴和分区。概率1-2A $ 1-2A $最小的部分大于$ $。 我们如何计算这种概率? 尝试72小时后,我达到遵循这意味着有效区域是(1-a)n-an = n(1-2...

8  QuickSort Dijkstra 3路分区:为什么额外交换?  ( Quicksort dijkstra 3 way partitioning why the extra swapping ) 
给出上面的算法(从幻灯片(p.35)在 coursera 情景: i - &gt; "x" ,"x" &gt; "p" 1. swap("X", "Z"), gt--; // the value at i is now "Z", which is still > "P" 2. swap("Z",...

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个部分。 现在,如果我总是选择最后一个元素作为枢轴,那么识别枢轴元素(第1步)需要$ mathcal o(n)$ time。 识别枢轴元件后,我们可以存储其数据并将其与所有其他元素进行比较以识别正确的分区(第2步...

-2  Quicksort实现不清楚  ( Quicksort implementation unclear ) 
此代码从 wikipedia : // left is the index of the leftmost element of the subarray // right is the index of the rightmost element of the subarray (inclusive) ...

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 ) 
为作业,任务是验证Quicksort的时间复杂性。用户昵称建议可以检查在将输入大小加倍时进行的比较数量。如果比较增加了2倍,我们验证了Quicksort中有 $ O(n log n)$ 时间复杂度。 是验证时间复杂性的合法方法吗? ...

1  Quicksort不变3条件带循环不变  ( Quicksort invariant 3 conditions with loop invariant ) 
在研究Quicksort使用本书"简介算法" 中由Cormen,Leserson,Rivest和Stein进行了描述,他们描述了为了显示正确性,不变必须保持循环的3个阶段,初始化,维护和终止循环。 基于以下算法,我不明白下面的属性1和2: 这是我引用的算法: 可能有人帮助我了解条件 1)如果 $ p ...

2  可以置换相对较小的随机数子集并重复使用,并保证Quicksort等算法的良好预期运行时间?  ( Can a relatively small subset of random numbers be permuted and reused and still ) 
所以这是一般问题,但我会将讨论限制为随机化的Quicksort来使其清除。假设生成"真实" 随机位很难,例如,因为它需要在自然界中测量某些东西,这可以被认为是像在每小时数英里记录的某些位置的大数位后的第50位二进制数字一样"随机" 。或许观察到的量子结果可以被认为是真正随机的。任何。所以我们做到以下了:我们通过使用伪...

3  双枢轴Quicksort参考实施?  ( Dual pivot quicksort reference implementation ) 
有某种规范 - 或参考 - 在任何地方发布了双枢轴Quicksort的实施? 我想在分拣算法中包含一个专门需要的算法,但我所看到的Java版本似乎有各种适用于它们的调整,就像使用Insertion排序的小(子句阵列,这使得比较基本面更难。 ...

8  不是线性时间o(n)?  ( Isnt linear time on ) 
在关于Quicksort 幸运地在每个递归呼叫中挑选中位数。 Tim Rocorgarden,演示者,在11:22 分区需要真正的线性时间,不仅仅是 $ o(n)$ 时间。 他在这里是什么意思?我认为线性时间是 $ o(n)$ 。他是否意味着 $ theta(n)$ 或其他东西?我看到Quicksort中的分...

2  Quicksort $ t(n)_ {最佳} = oomega(n log n)$验证  ( Quicksort tn best omegan log n proof ) 
关于Quicksort的证据是$ t(n)_ {最佳} = oomga(n log n)$。 我无法在网上的任何地方找到这个特定的方面,这是奇怪的。我在一本书中经历了一个证据,我不明白一些东西,它表示关于分析递归树中的"成本" ,即: 自Quicksort的复发关系是:$ t_ {最好} = t(i-1)+ ...

1  表明Quicksort的最佳情况复杂性是$ omega(n log n)$  ( Show that the best case time complexity of quicksort is omegan log n ) 
我正在尝试表明最佳案例 Quicksort的时间复杂性是 $ oomega(n log n)$ 。< / p> 以下复发描述了Quicksort的最佳情况 - 时间复杂度: $$ t(n)= min_ {0 le q le n-1}左(t(q)+ t(nq-1)右) + theta(n)。$$ 但...

相关问题

7  为什么从Quicksort切换到依赖于Quicksort的最佳截止? 
0  Quicksort算法的最糟糕的情况场景N / 2 
0  关于HOARE的分区计划和略微修改的问题 
2  是否有排序算法$ n + k log {k} $? 
1  合并排序优先于快速排序的方案 
6  哪种测量的分类解释了Quicksort运行时中的阶段过渡? 
2  如何陈述一种表达最糟糕的态度的复发? 
3  算法查找发生超过n / 10次的所有值 
1  如果输入集更加递减,Quicksort用于增加订单工作的速度更快? 
-2  Quicksort分区的概率创建了一个不平衡的分区 
3  Quicksort分区成本 
0  Quicksort的平均案例运行时间分析很好参考 
2  随机Quicksort中较小分区大小的概率界限 
8  QuickSort Dijkstra 3路分区:为什么额外交换? 
4  从随机化Quicksort中的随机化 
17  我们为什么不使用链接列表中的快速排序? 
-2  Quicksort实现不清楚 
100  Quicksort分区:Hoare与Lomuto 
1  大O:分析$ O(n log n)$ - 算法的时间复杂性 
1  Quicksort不变3条件带循环不变 
2  可以置换相对较小的随机数子集并重复使用,并保证Quicksort等算法的良好预期运行时间? 
3  双枢轴Quicksort参考实施? 
8  不是线性时间o(n)? 
2  Quicksort $ t(n)_ {最佳} = oomega(n log n)$验证 
1  表明Quicksort的最佳情况复杂性是$ omega(n log n)$ 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有