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
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.
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.