# Comparing two partition functions in Python

I have written a partition function in Python (my_partition_adv). I have written this one after reading a similar function from a website. The version of the partition function from the website is also given below (parititon_inplace).

As I am a beginner in Python, I want to know the following things:

2. Are there any drawbacks for my version in terms of complexity that I am missing?

3. Are there any other drawbacks for my_partition_adv over partition_inplace?

def partition_inplace(A, start, stop, pivot_index):
items_less_than = []
items_greater_than_or_equal = []

if item < pivot_value:
items_less_than.append( item )
else:
items_greater_than_or_equal.append( item )

write_index = start

for item in items_less_than:
A[write_index] = item
write_index += 1

for item in items_greater_than_or_equal:
A[write_index] = item
write_index += 1

return len(items_less_than)

less_than = []
greater_than_or_equal = []

for index, item in enumerate(A):
if item < p_val:
less_than.append(item)
else:
greater_than_or_equal.append(item)

for index,item in enumerate(less_than):
A[index] = less_than[index]

for index,item in enumerate(greater_than_or_equal):
A[len(less_than) + index] = greater_than_or_equal[index]

return len(less_than)


These two functions are doing somewhat different tasks. The first one partitions a subrange of a list; the second one may only partition an entire list.

The use of enumerate is not justified in the first loop (index is not being used at all), and is quite suspicious in the second and third. Slices would achieve the same result more pythonically:

partition_point = len(less_than)
A[:partition_point] = less_than
A[partition_point:] = greater_than
return partition_point


my_partition_adv() makes inefficient use of memory, as it has to allocate temporary arrays less_than and greater_than_or_equal. Furthermore, Python has to guess at how large to make those temporary arrays, since you don't preallocate them. Therefore, if the input array has more elements than expected, it may need to reallocate arrays for you silently, and each reallocation could necessitate copying the intermediate result. Performance might be somewhere between O(n) and O(n2).

Since your function does not allow the start and stop bounds to be specified, you can't really use it, for example, as a part of a quicksort implementation.

You didn't ask for a review of partition_inplace(), but I should mention that its parameters should have been rearranged to facilitate default parameters:

def partition_inplace(arr, pivot_index=0, start=0, stop=None):
…

• I don't understand difference in case of preallocate.Both functions seems to be doing the same thing. i.e appending a new item based on a condition.How is memroy use less efficient in my_partition_adv() May 13, 2014 at 3:55