I've covered a few sorting algorithms in Python that I have learned and analyzed in my computer science and algorithms classes: Insertion Sort Using Python, Selection Sort in Python, and Merge Sort in Python Using Pythonista 3 on iPad Pro. Today, in one of my algorithms design and analysis classes I learned about Quicksort. My instructor was particularly enthusiastic about Quicksort, because he thinks it is a very elegant and practical algorithm. Much like Merge Sort, it is a divide and conquer sorting algorithm that sorts the items in O(nlogn).

Quicksort in Python

As with all new learnings, I like to practice writing the algorithms in Python, which I am also currently learning. Here is today's version of Quicksort in Python.

import random


def quicksort(items):

    def sort(lst, l, r):
        # base case
        if r <= l:
            return

        # choose random pivot
        pivot_index = random.randint(l, r)

        # move pivot to first index
        lst[l], lst[pivot_index] = lst[pivot_index], lst[l]

        # partition
        i = l
        for j in xrange(l+1, r+1):
            if lst[j] < lst[l]:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]

        # place pivot in proper position
        lst[i], lst[l] = lst[l], lst[i]

        # sort left and right partitions
        sort(lst, l, i-1)
        sort(lst, i+1, r)

    if items is None or len(items) < 2:
        return

    sort(items, 0, len(items) - 1)

Quicksort is an in-place sorting algorithm. Therefore, when you pass it an array of integers, for example, it will mutate that array and sort it in increasing order. The fact that Quicksort doesn't use a lot of additional memory like Merge Sort makes it very practical and desirable. One can sort a list of integers using the following Python script and my quicksort function.

numbers = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print 'unsorted: ', numbers
quicksort(numbers)
print 'sorted:   ', numbers

unsorted:  [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
sorted:    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

This is my first time working with Quicksort and it is solely based on what I learned today in my algorithms class. A couple of things are worth noting, because I plan to do further investigation on them in the near future. The first is the use of a random pivot, and the second is the placement of my pivot at the front of the list.

Choosing a Good Pivot is Critical

My instructor was quite adamant about the importance of choosing a good pivot. In class we discussed choosing the pivot randomly, which doesn't sound intuitive, but actually has good results when looked at mathematically. On average, a randomly chosen pivot will provide O(nlogn) and worst case O(n2). The worst case is apparently highly unprobable, which means a randomly chosen pivot is on average "good enough." If O(n2) is unacceptable even by chance, there is a median of medians alternative to choosing the pivot that was discussed later in the lecture.

I will stick with a random pivot, and therefore in my code above, I used the randint function to randomly choose the index of the next pivot.

# choose random pivot
pivot_index = random.randint(l, r)

Pivot Moved to Beginning of List

I'm not sure why this strikes me as interesting, but I wonder about the need to move the pivot to the beginning of the list. It seems necessary and practical to keep track of the pivot, but also seems out of place in the code. I move the pivot to the beginning of the list, because in class we always chose the first item as the pivot for simplicity, but I want to randomize the choice of the pivot in my code. To keep my thinking straight with what I learned in class, I move the pivot to the beginning of the list. It makes it really easy to track the location of the pivot and maintain the partitions, but I'm wondering if this is actually done in other implementations.

# move pivot to first index
lst[l], lst[pivot_index] = lst[pivot_index], lst[l]

I did a small amount of investigation on this, and found that in the partition function psuedocode for quickselect on Wikipedia there is mention of moving the pivot to the end of the list.

function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     ...

That makes me feel somewhat at ease, but I want to research that further.

Conclusion

I'm sure I will be changing this code as I learn more about Quicksort. You will soon see similar code when I mention Quickselect, which is something we also just covered in my algorithms class.

If you're learning Quicksort, I hope this code helps!

You can find me on twitter as @KoderDojo!

P.S. Check out the Quickselect Algorithm, which is a selection algorithm based on Quicksort.

Posted by Koder Dojo

Hi! I am a freelance C#, ASP.NET MVC Developer learning Python, computer science, algorithms, cryptography, and data science while developing web application in ASP.NET MVC. I am journaling my new knowledge on this website to share and inspire others. Writing also helps me reinforce and retain my knowledge. If you are learning these new subjects as well, I hope to meet you on twitter! I am @KoderDojo.

Related Posts: