Comparing two partition functions in Python

Question

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:

1. My version looks certainly more readable than the partition_in_place_with_additional_memory.

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 = []

    read_index = start
    while read_index <= stop:
        item = A[read_index]
        if item < pivot_value:
            items_less_than.append( item )
        else:
            items_greater_than_or_equal.append( item )
        read_index += 1

    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)



def my_partition_adv(A,p_val):
        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)

Answer 1

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

Answer 2

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(n²).

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):
    …