In here, we talk about the implementation of QuickSort in Python – the well-known and standard sorting algorithm that is used today.

It is not so easy to implement except in Python, in a Pythonic way. The quicksort algorithm can be easily illustrated using the following Python recursion function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < = 1:
            return nums
        
        pivot = random.choice(nums)
        lt = [v for v in nums if v < pivot]
        eq = [v for v in nums if v == pivot]
        gt = [v for v in nums if v > pivot]
        return self.sortArray(lt) + eq + self.sortArray(gt)  

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < = 1:
            return nums
        
        pivot = random.choice(nums)
        lt = [v for v in nums if v < pivot]
        eq = [v for v in nums if v == pivot]
        gt = [v for v in nums if v > pivot]
        return self.sortArray(lt) + eq + self.sortArray(gt)  

First, we choose a random pivot, then we partition the input array into three parts, then recursively partition left, and right parts, finally merge into a new list.

The downside of above implementation is it requires additional O(N) space, which can be eliminated using in-place swapping.

Depending on the randomness when choosing a good pivot, the performance of the quicksort may vary. The worst cases would be O(N^2), and average complexity is O(Nlog(N))

This implementation is easy to remember and easy to write on coding whiteboard. And it is code that works rather than pseudo-code.

Recursive Quicksort implementation in Javascript: Javascript Coding Exercise: The QuickSort Implementation in Javascript

--EOF (The Ultimate Computing & Technology Blog) --