CODEWITHSUNDEEP
algorithmpartitioning
Pab
Pab

Reputation: 13

Partitioning element

im trying to understand the below text:

You are given a list and it has just been partitioned using a standard partitioning algorithm. You are to say which element could have been the partitioning element. For example, given the numbers [7, 6, 8, 20, 11, 5, 14], then only 8 could have been the partitioning element and the algorithm will continue sorting [7, 6] and [20, 11, 5, 14].

im trying to understand how 8 is the partitioning element here? Thanks

Upvotes: 0

Views: 73

Answers (1)

Patrice Gahide
Patrice Gahide

Reputation: 3744

At the end of a quicksort iteration, every element to the left of the pivot p (partitioning element) must be lesser than p, and every element to the right must be greater than p. This means that p is now at its final sorted position. The quicksort algorithm proceeds recursively on both resulting subarrays (left and right).

Given a configuration of the array during the quicksort process, you can identify the possible pivots that could have been used on the previous iteration with this simple quadratic procedure:

foreach int m in the array
  if (all int l on the left of m verify l < m)
    AND (all int r on the right of m verify r >= m)
  then
    m was a possible pivot in the previous iteration

You can do better than O(n^2), but this is the basic idea.

Upvotes: 1

Related Questions