Partitioning Schemes

excerpt: A well known problem in computer science consists of partitioning a list. tags: partitioning

Partitioning a list consists of the following steps:

  1. Randomly select a pivot element from the list.
  2. Permute the input list where the first elements are smaller than or equal to the pivot and the last ones are greater than the pivot.

The diagram shows selecting the pivot and permuting the list. This partitioning scheme is used in the quicksort and quickselect algorithms.

Basic Partitioning Scheme

The list is scanned to build:

  1. A new list that contains the elements that are smaller than or equal to the pivot.
  2. Another list formed by the elements that are greater than the pivot.
  3. Concatenate the list together with the pivot element placed in between the two lists.

The inputs to the problem are a list ‘a’ of length n and some value x that plays the role of the pivot. Its size is the length of the list. The base case occurs when the list is empty, we return an empty list. For the recursive case we can decompose the problem by discarding the first element of the list, which reduces its size by a unit.

The recursive diagrams depends on whether the first element of the list is less than or equal to the pivot. If it is, recursive diagram is as shown below:

The first element of the list must be concatenated to the output of the subproblem. If the first element is greater than x, the diagram is as shown below:

In this case, we have to return the solution (list) to the subproblem. The code shows the linear recursive solution that solve both problems.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def get_smaller_than_or_equal_to(a, x)
  if a.empty?
    return []
  end
  
  if a[0] <= x
    return [a[0]] + get_smaller_than_or_equal_to(a[1..-1], x)
  else
    return get_smaller_than_or_equal_to(a[1..-1], x)
  end
end

The get_smaller_than_or_equal_to and get_greater_than are auxiliary methods for partitioning a list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def get_greater_than(a, x)
  if a.empty?
    return a
  end
  
  if a[0] > x
    return [a[0]] + get_greater_than(a[1..-1], x)
  else
    return get_greater_than(a[1..-1], x)
  end
end

In the recursive cases that perform the concatenation, the function call is not the last action of the method. The runtime is linear with respect to n.