Clever Geek Handbook

Quicksort interview quistion

Recent interview question:

Consider an array with n elements, which is divided into three parts:

A[1] .....................................................A[n]
part1(m1)..........part2(m2)......... part3(m3)

Then three times quicksort is done on it like this

QuickSort(A[m1+1.....n])
QuickSort(A[1.....m1+m2])
QuickSort(A[m1+1.....n])

What state is the array sorted in?

a) m1>m2
b) m1<m2
c) m1>=m2
d) m1=m2=m3

My answer was m1>m2

, but now I doubt it is also valid m1>=m2

. Right?

+3


source to share


3 answers


I maintain that it is m1 <= m2

necessary and sufficient.

  • If so, then after the first one we can be sure that the m2

    smallest numbers from the part m1 + 1 ... n

    are inside the prefix 1 ... m1 + m2

    . m2

    > = m1

    , so the m1

    smallest numbers are inside the prefix 1 ... m1 + m2

    . This means that after the second run they will be in the correct position. It doesn't matter what happens in the part m1 + 1 ... n

    , because either way it will be corrected during the last run.

  • If this is not the case, it is easy to construct an example of a counter: {3, 3, 1, 2, 2}, m1 = m3 = 2, m2 = 1.



This means that both b) and d) are correct.

+2


source


Consider the case when

A = 3 3 3 2 2 1

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

If we sort with quicksort (qs) in the ways we get:

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]


End result: 1 2 3 2 3 3 is not sorted.

In this case, the result is not sorted because m2 is smaller than m1, so the minimum values ​​of m1 cannot be carried over from part 3 to part 1 using part 2 as a (sort of) buffer. Therefore, we must have m1 <= m2.

  • a) m1> m2 may not work (as shown).
  • b) m1 <m2 is sufficient since m1 <= m2
  • c) m1> = m2 might not work as m1 might be> m2 in this case, and the example proved it wrong.
  • d) m1 = m2 = m3 satisfies m1 <= m2, which is a sufficient condition for sorting A.
+1


source


The last run will not touch part1

, so part1

should contain the m1

smallest array elements after the second run. If some of them are initially found in part1

that OK; if they are in part2

, the second run will take them to the right place; however, those in part3

must first be translated to part2

. If the array is originally in reverse order, then it m1>=m2>=m3

must be satisfied to bring the m3

smallest elements from the right end of the array to the left. Similary m1<=m2<=m3

seems to be necessary to ensure that the m1

largest elements from part1

are shifted by part3

.

The final answer is d.

0


source






More articles:


All Articles