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) --
loading...
Last Post: How to Compute the Clumsy Factorials using Iterative Algorithm?
Next Post: How to Flip Equivalent Binary Trees?