CODEWITHSUNDEEP
algorithmsortinglanguage-agnosticquicksort
user3802426
user3802426

Reputation: 33

Quicksort Interview Question: Quicksort run three times

A question I got on recent interview:

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

My answer was m1>m2 but now I am in doubt whether m1>=m2 is also correct. Is this right?

Upvotes: 3

Views: 265

Answers (3)

ryanpattison
ryanpattison

Reputation: 6251

Consider the case where

A = 3 3 3 2 2 1

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

If we sort using quicksort (qs) in the ways given 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]

The final result: 1 2 3 2 3 3 is not sorted.

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

  • a) m1 > m2 may not work (as was shown).
  • b) m1 < m2 is sufficient since m1 <= m2
  • c) m1 >= m2 may not work, since m1 can be > m2 in this case and the example proved it is false.
  • d) m1=m2=m3 satisfies m1 <= m2 so it is a sufficient condition for A to be sorted.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18556

I claim that m1 <= m2 is necessary and sufficient.

  1. If it is the case, after the first we can be sure that m2 smallest numbers from the m1 + 1 ... n part are located inside the 1 ... m1 + m2 prefix. m2 >= m1, thus m1 smallest numbers are inside the 1 ... m1 + m2 prefix. It means that after the second run they will be on their correct positions. It does not matter what's going on in the m1 + 1 ... n part because it will be fixed during the last run anyway.

  2. If it is not the case, it is easy to build a counter example: {3, 3, 1, 2, 2}, m1 = m3 = 2, m2 = 1.

It means that both: b) and d) are correct.

Upvotes: 2

CiaPan
CiaPan

Reputation: 9570

The last run won't touch part1, so part1 must contain m1 smallest items of the array after the second run. If some of them are initially in part1 that's OK; if they are in part2 the second run will bring them to the right place; however those who are in part3 must be shifted to part2 first. If the array is initially in reverse order, then m1>=m2>=m3 must be satisfied to bring m3 least items from the right end of the array to the left one. Similary m1<=m2<=m3 seems necessary to guarantee m1 largest items from part1 will be shifted to part3.

Final answer: d.

Upvotes: 0

Related Questions