Pythonic quick sort

Question

I'm new to the world of python, and wrote this quick sort implementation which was taught to us in an algorithms class. I would like to learn to write code less like C++ and more pythonic. Could you review my code to make it more pythonic and less buggy? (I'm sure a class implementation is better, but if the scope of the review could maintain the original structure that would be great).

def quick_sort(A):
    #here we choose pivot's index
    def choose_pivot(start, end, method='start'):
        if start == end: return 0
        if method == 'random':
            return random.randint(start, end-1)
        elif method == 'start':
            return start

    #we partition the array around the pivot, and return the new pivot
    #which is pivot's rightful index
    #Hoare's algorithm for partitioning
    def partition_array(start, end, pivot_index):
        pivot = A[pivot_index] 
        #move pivot to start of the array, for swap later
        A[start], A[pivot_index] = A[pivot_index], A[start]
        left, right = start + 1, end - 1
        #partition around pivot
        while left < right:
            while left < end and A[left] < pivot:
                left += 1
            while right > start and A[right] >= pivot:
                right -= 1
            if left < right:
                A[left], A[right] = A[right], A[left]
        #swap back the pivot
        A[start], A[right] = A[right], A[start]
        return right

    #Lumoto's algorithm for partitioning
    def partition_array_2(start, end, pivot_index):
        left = right = start + 1
        pivot = A[pivot_index]
        #swap out the pivot to the start of the array
        A[pivot_index], A[start] = A[start], A[pivot_index]
        while right < end:
            if A[right] < pivot:
                A[left], A[right] = A[right], A[left]
                left += 1
            right += 1
        #swap back the pivot to its rightful place
        A[start], A[left-1] = A[left-1], A[start]
        return left-1


    #recursively compute quicksort, with divide and conquer
    #where start <= new partition (actual place of pivot) <= end
    def quick_sort_helper(start, end):
        if end - start <= 0:
            return
        #choose new pivot
        pivot_index = choose_pivot(start, end)
        new_pivot_index = partition_array_2(start, end, pivot_index)

        quick_sort_helper(start, new_pivot_index)
        quick_sort_helper(new_pivot_index+1, end)

    #Main call
    quick_sort_helper(0, len(A))

Answer 1

Focus on the essence of the algorithm, not the exact procedure on texts

In common algorithm texts for C/C++, the description of an algorithm is more suited for implementation in C/C++. Common elements include:

• An array, or an object in general, is assumed to have fixed memory location and fixed size.
• Creating a new array or object is considered bad practice, since it incurs time overhead.
• As a consequence, a part of an array is passed around as start and end indices.

Since you decided to program in Python, you must escape from the C/C++-style algorithms.

---

Now, let's go back to the high-level description of Quicksort:

1. Choose a pivot, be it start or random.
2. Partition the array as "less than pivot", "same as pivot" and "greater than pivot".
3. Recursively apply this algorithm to the subarrays found in step 2.

The very core of the algorithm is step 2, a.k.a. the partitioning step. Your code has Lumoto's and Hoare's algorithm, both of which are designed strictly for C/C++. You have to throw them away entirely, since Python has much more readable (and elegant) way of doing this task:

def partition(list_, pivot):
    less = [x for x in list_ if x < pivot]
    equal = [x for x in list_ if x == pivot]
    greater = [x for x in list_ if x > pivot]
    return (less, equal, greater)

If you understand list comprehension, you won't ever need a single comment to read and understand this code. Otherwise, study more about it on the Internet.

Note that the function accepts and returns entire lists, not the indices. Pivot is also passed as actual value rather than its index. For naming things, I tried to avoid using the term array, since we're using lists here instead.

_{The underscore _ in list_ is to avoid name clash with the built-in function list.}

---

This decision propagates to the other parts of the algorithm. Consider step 1 (pivot selection). We can modify choose_pivot to accept a list and method, and return the selected pivot value:

def choose_pivot(list_, method='start'):
    if method == 'start':
        return list_[0]
    return random.choice(list_)

And then, the main quicksort function doesn't need a helper:

def quicksort(list_):
    if not list_: return list_
    pivot = choose_pivot(list_)
    less, equal, greater = partition(list_, pivot)
    return quicksort(less) + equal + quicksort(greater)

---

Final note: I assumed so far that you're not that interested in running speed. Otherwise, just use list.sort() or sorted() as suggested in the comments. They're much faster as both functions' internals are implemented in C (assuming CPython).