Quicksort面试题：Quicksort运行了三次

Question

我在最近的面试中遇到的一个问题：

Consider an array with n elements which is divided into three parts:
A[1] .....................................................A[n]
part1(m1)..........part2(m2)......... part3(m3)
Then quick sort is run on it three times as follows:
QuickSort(A[m1+1.....n])
QuickSort(A[1.....m1+m2])
QuickSort(A[m1+1.....n])
Under what condition is the array is sorted?
a) m1>m2
b) m1<m2
c) m1>=m2
d) m1=m2=m3

我的回答是m1>m2，但现在我怀疑m1>=m2是否也是正确的。这样对吗？

Answer 1

考虑

的情况

A = 3 3 3 2 2 1

m1 = 3, m2 = 2, m3 = 1, n = 6

如果我们按照给定的方式使用快速排序 (qs) 进行排序，我们会得到：

qs(A[3+1..6]) ->  3 3 3 [1 2 2]

qs(A[1..2+3]) ->  [1 2 3 3 3] 2

qs(A[3+1..6]) ->  1 2 3 [2 3 3]

最终结果：1 2 3 2 3 3 未排序

在这种情况下，结果未排序，因为 m2 小于 m1，因此最小 m1 值无法使用第 2 部分作为（某种）缓冲区从第 3 部分转移到第 1 部分。所以我们必须有 m1 <= m2.

a) m1 > m2 可能不起作用（如图所示）。
b) m1 < m2 就足够了，因为 m1 <= m2
c) m1 >= m2 可能不起作用，因为在这种情况下 m1 可以 > m2 并且示例证明它是错误的。
d) m1=m2=m3满足m1 <= m2所以是A排序的充分条件

Answer 2

最后一个运行不会触及 part1，因此 part1 必须包含第二个运行之后数组的 m1 个最小项。如果其中一些最初在 part1 中，那没关系；如果他们在 part2 中，第二个运行会将他们带到正确的位置；然而，那些在 part3 的人必须先转移到 part2。如果数组最初是倒序的，则必须满足 m1>=m2>=m3 才能将 m3 最少的项目从数组的右端带到左端。类似地 m1<=m2<=m3 似乎有必要保证 m1 最大的项目从 part1 转移到 part3。

最终答案：d.

Answer 3

我声称m1 <= m2是充分必要的。

如果是这样，在第一个之后我们可以确定 m1 + 1 ... n 部分的最小数字 m2 位于 1 ... m1 + m2 前缀内。 m2 >= m1，因此 m1 最小的数字在 1 ... m1 + m2 前缀内。这意味着在第二个运行之后，他们将处于正确的位置。 m1 + 1 ... n 部分发生了什么并不重要，因为它将在最后运行期间修复。
如果不是这样，很容易建立一个反例：{3, 3, 1, 2, 2}, m1 = m3 = 2, m2 = 1.

表示：b)和d)都正确

Quicksort面试题：Quicksort运行了三次

Quicksort Interview Question: Quicksort run three times

algorithm

sorting

language-agnostic

quicksort